Submission #43271

#	Time	Username	Problem	Language	Result	Execution time	Memory
43271		ffresh	우호 조약 체결 (JOI14_friends)	C++14	100 / 100	154 ms	12416 KiB

friends

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5+15;

long long 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);
	assert(n<=1e5);
	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((int)adj[i].size()>=2){
			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 (stderr)

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:52: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 / 5
• Subtask 2: 30 / 30
• Subtask 3: 65 / 65