Submission #42423

#TimeUsernameProblemLanguageResultExecution timeMemory
42423dqhungdl우호 조약 체결 (JOI14_friends)C++14
0 / 100
80 ms12164 KiB
#include <bits/stdc++.h> using namespace std; int64_t n,m,res=0,P[100005],Size[100005]; vector<int64_t> g[100005]; int64_t Find(int64_t u) { if(u==P[u]) return u; return P[u]=Find(P[u]); } void Union(int64_t u,int64_t v) { if(Size[u]<Size[v]) swap(u,v); P[v]=u; Size[u]+=Size[v]; } int main() { ios_base::sync_with_stdio(false); //freopen("TEST.INP","r",stdin); cin>>n>>m; int64_t u,v; while(m--) { cin>>u>>v; g[u].push_back(v); } for(int64_t i=1;i<=n;i++) { P[i]=i; Size[i]=1; } for(int64_t i=1;i<=n;i++) if(g[i].size()>=2) for(int64_t j=1;j<g[i].size();j++) { int64_t u=Find(g[i][0]); int64_t v=Find(g[i][j]); if(u!=v) Union(u,v); } for(int64_t i=1;i<=n;i++) if(P[i]==i) { if(Size[i]>1) res+=Size[i]*(Size[i]-1); else res+=g[i].size(); } cout<<res; }

Compilation message (stderr)

friends.cpp: In function 'int main()':
friends.cpp:40:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int64_t j=1;j<g[i].size();j++)
                              ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...