Submission #42427

#TimeUsernameProblemLanguageResultExecution timeMemory
42427dqhungdl우호 조약 체결 (JOI14_friends)C++14
0 / 100
92 ms11240 KiB
#include <bits/stdc++.h> using namespace std; int64_t n,m,res=0,P[100005],Size[100005]; bool Free[100005]; vector<int64_t> V,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]; } void DFS(int64_t u) { Free[u]=true; for(int64_t i=0;i<g[u].size();i++) { V.push_back(g[u][i]); if(Free[g[u][i]]==false) DFS(g[u][i]); } } 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(Free[i]==false&&g[i].size()>=2) { V.clear(); DFS(i); for(int64_t j=1;j<V.size();j++) { int64_t u=Find(V[0]); int64_t v=Find(V[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 'void DFS(int64_t)':
friends.cpp:26:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int64_t i=0;i<g[u].size();i++)
                      ^
friends.cpp: In function 'int main()':
friends.cpp:55:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int64_t j=1;j<V.size();j++)
                              ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...