oj.uz

Submission #43269

# Submission time Handle Problem Language Result Execution time Memory
43269 2018-03-12T12:41:06 Z ffresh 우호 조약 체결 (JOI14_friends) C++14
35 / 100
 125 ms 8128 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5+15;

int par[N],sz[N],esz[N];

vector<int> adj[N];

int f(int a){
	if(a==par[a])return a;
	return par[a]= f(par[a]);
}
void merge(int a,int b){
	a= f(a),b= f(b);
	if(a!=b){
		par[b]= a;
		sz[a]+=sz[b];
		esz[a]+=esz[b];
	}
	++esz[a];
}
bool vis[N];

void dfs(int root){
	vis[root]= 1;
	for(int i=0;i<adj[root].size();++i){
		int u = adj[root][i];
		if(!vis[u]){
			dfs(u);
		}
		merge(u,root);
	}
}


int main(){
	//freopen("input.txt","r",stdin);
	int n,m,a,b;
	scanf("%d%d",&n,&m);

	for(int i=0;i<m;++i){
		scanf("%d%d",&a,&b);
		adj[a].push_back(b);
	}
	for(int i=1;i<=n;++i)
		par[i] =i,sz[i]= 1;
	for(int i=1;i<=n;++i){
		
		if(adj[i].size()>1){
			int cur = adj[i][0],v;
			for(int j=0;j<adj[i].size();++j){
				int u = adj[i][j];
				if(!vis[u])
					dfs(u);
				if(f(u)!=f(cur)){
					v = f(cur),u = f(u);
					par[u] = v;
					esz[v]+=esz[u];
					sz[v] += sz[u];
				}
			}
		}
	}
	long long ret=0;

	for(int i=1;i<=n;++i){
		if(f(i)==i){
			ret += (long long)(sz[i]*(sz[i]-1));
			ret -= esz[i];
		}
	}

	ret+=m;
	cout<<ret<<endl;
}

Compilation message

friends.cpp: In function 'void dfs(int)':
friends.cpp:28:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<adj[root].size();++i){
               ^
friends.cpp: In function 'int main()':
friends.cpp:53:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<adj[i].size();++j){
                 ^
friends.cpp:41:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
                     ^
friends.cpp:44:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&a,&b);
                      ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2680 KB Output is correct
2 Correct 3 ms 2680 KB Output is correct
3 Correct 3 ms 2728 KB Output is correct
4 Correct 3 ms 2800 KB Output is correct
5 Correct 3 ms 2872 KB Output is correct
6 Correct 3 ms 2904 KB Output is correct
7 Correct 3 ms 2976 KB Output is correct
8 Correct 4 ms 2976 KB Output is correct
9 Correct 3 ms 2976 KB Output is correct
10 Correct 3 ms 2976 KB Output is correct
11 Correct 4 ms 2976 KB Output is correct
12 Correct 3 ms 2976 KB Output is correct
13 Correct 3 ms 2976 KB Output is correct
14 Correct 4 ms 2976 KB Output is correct
15 Correct 3 ms 2976 KB Output is correct
16 Correct 4 ms 2976 KB Output is correct
17 Correct 3 ms 3052 KB Output is correct
18 Correct 3 ms 3052 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3052 KB Output is correct
2 Correct 4 ms 3052 KB Output is correct
3 Correct 11 ms 3308 KB Output is correct
4 Correct 45 ms 4204 KB Output is correct
5 Correct 38 ms 4204 KB Output is correct
6 Correct 61 ms 4588 KB Output is correct
7 Correct 4 ms 4588 KB Output is correct
8 Correct 6 ms 4588 KB Output is correct
9 Correct 11 ms 4588 KB Output is correct
10 Correct 20 ms 4588 KB Output is correct
11 Correct 68 ms 4716 KB Output is correct
12 Correct 9 ms 4716 KB Output is correct
13 Correct 5 ms 4716 KB Output is correct
14 Correct 5 ms 4716 KB Output is correct
15 Correct 8 ms 4716 KB Output is correct
16 Correct 15 ms 4716 KB Output is correct
17 Correct 62 ms 4716 KB Output is correct
18 Correct 5 ms 4716 KB Output is correct
19 Correct 5 ms 4716 KB Output is correct
20 Correct 68 ms 4716 KB Output is correct
21 Correct 5 ms 4716 KB Output is correct
22 Correct 5 ms 4716 KB Output is correct
23 Correct 9 ms 4716 KB Output is correct
24 Correct 5 ms 4716 KB Output is correct
25 Correct 6 ms 4716 KB Output is correct
26 Correct 5 ms 4716 KB Output is correct
27 Correct 5 ms 4716 KB Output is correct
28 Correct 5 ms 4716 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 4716 KB Output is correct
2 Incorrect 125 ms 8128 KB Output isn't correct
3 Halted 0 ms 0 KB -