Submission #6066

#TimeUsernameProblemLanguageResultExecution timeMemory
6066ainta우호 조약 체결 (JOI14_friends)C++98
0 / 100
60 ms10584 KiB
#include<stdio.h> #include<algorithm> #include<vector> #define N_ 100010 using namespace std; int n, m, C[N_], par[N_]; long long C2[N_]; vector<int>E[N_], F[N_]; bool v[N_]; int SCC[N_], ord[N_], cnt; int find(int a) { if(a==par[a])return a; return par[a] = find(par[a]); } void DFS(int a) { v[a] = true; int i; for(i=0;i<E[a].size();i++){ if(!v[E[a][i]]){ DFS(E[a][i]); } } ord[++cnt] = a; } void DFS2(int a) { int i; C[a]++; SCC[a] = cnt; for(i=0;i<F[a].size();i++){ if(!SCC[F[a][i]]){ DFS2(F[a][i]); } } } void Merge(int a, int b){ int x = find(a), y = find(b); if(x != y){ par[y] = x; C[x] += C[y]; C2[x] = (long long)C[x]*(C[x]-1); } } int main() { int i, j, a, b; scanf("%d%d",&n,&m); while(m--){ scanf("%d%d",&a,&b); E[a].push_back(b); F[b].push_back(a); } for(i=1;i<=n;i++){ if(!v[i]){ DFS(i); } } cnt = 0; for(i=n;i>=1;i--){ if(!SCC[ord[i]]){ cnt++; DFS2(ord[i]); } } for(i=1;i<=n;i++)F[i].clear(); for(i=1;i<=n;i++){ for(j=0;j<E[i].size();j++){ if(SCC[i] != SCC[E[i][j]]){ F[SCC[i]].push_back(SCC[E[i][j]]); } else{ C2[SCC[i]]++; } } } for(i=1;i<=cnt;i++)par[i]=i; long long Res = 0; for(i=1;i<=cnt;i++){ a=find(i); if(C[a] <C2[a])C2[a] = (long long)C[a]*(C[a]-1); for(j=0;j<F[i].size();j++){ if(C[a] == 1 && j){ Merge(F[a][j-1],F[a][j]); } if(C[a] == 1) Res++; if(C[a] != 1) Merge(a,F[a][j]); } } for(i=1;i<=cnt;i++){ if(i == find(i)){ Res += C2[i]; } } printf("%lld\n",Res); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...