100 Accepted
time_space_table: /1703/ranking1.in:AC mem=2328k time=4ms /1703/ranking10.in:AC mem=2460k time=30ms /1703/ranking2.in:AC mem=2460k time=3ms /1703/ranking3.in:AC mem=2460k time=4ms /1703/ranking4.in:AC mem=2460k time=5ms /1703/ranking5.in:AC mem=2460k time=13ms /1703/ranking6.in:AC mem=2460k time=4ms /1703/ranking7.in:AC mem=2460k time=25ms /1703/ranking8.in:AC mem=2460k time=25ms /1703/ranking9.in:AC mem=2460k time=18ms
代码
#include<bits/stdc++.h>
using namespace std;
bitset<1001>b[1001];
vector<int>e[1001];
bool vis[1001];
inline void dfs(int now)
{
vis[now]=true;
for(auto it: e[now])
{
if(vis[it])
continue;
dfs(it);
b[now]|=b[it];
}
}
int main(){
int n,m;
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++)
{
int u,v;
scanf("%d %d",&u,&v);
e[u].push_back(v);
b[u][v]=1;
}
for(int i=1;i<=n;i++)
{
memset(vis,0,sizeof(vis));
dfs(i);
}
int ans=n*(n-1)/2;
for(int i=1;i<=n;i++)
ans-=b[i].count();
printf("%d\n",ans);
return 0;
}
信息
- 递交者
- 题目
- P1703 [Usaco2007 Mar]Ranking the Cows 奶牛排名
- 语言
- C++
- 代码长度
- 583 Bytes
- 递交时间
- 2022-12-3 21:48:36
- 评测时间
- 2023-12-17 23:47:33
- 分数
- 100
- 总耗时
- 131ms
- 峰值内存
- 2.4 MiB