제출 #232868

#제출 시각아이디문제언어결과실행 시간메모리
232868Ruxandra985철인 이종 경기 (APIO18_duathlon)C++14
0 / 100
146 ms35192 KiB
#include <bits/stdc++.h> #define DIMN 100005 #define DIMM 200005 using namespace std; long long low[DIMN] , bicnx , lvl[DIMN] , taken[DIMN] , f[DIMN] , two[DIMN] , under[DIMN]; stack <long long> st; vector <long long> v[DIMN] , w[2 * DIMN]; set <long long> sol[DIMN]; long long x , n , val; void dfs_bic (long long nod,long long tt){ long long i,vecin; low[nod]=lvl[nod]; st.push(nod); for (i=0;i<v[nod].size();i++){ vecin=v[nod][i]; if (vecin==tt) continue; if (lvl[vecin]==0){ lvl[vecin]=1+lvl[nod]; dfs_bic(vecin,nod); low[nod]=min(low[nod],low[vecin]); if (low[vecin]>=lvl[nod]){ /// nod e un nod critic bicnx++; do{ x=st.top(); taken[x]++; st.pop(); sol[bicnx].insert(x); } while (x!=vecin); sol[bicnx].insert(nod); taken[nod]++; /// am scos din stiva muchiile care sunt in subarborele nod->vecin } } else low[nod]=min(low[nod],lvl[vecin]); } } void dfs (long long nod){ long long sum , i , vecin , tata=0; //prlong longf ("%lld ",nod); f[nod] = 1; sum = 0; if (nod > n){ /// nod under[nod] = 1; two[nod] = 0; } else { /// componenta under[nod] = sol[bicnx - nod + 1].size(); x = sol[bicnx - nod + 1].size(); two[nod] = x * (x - 1); } for (i = 0 ; i < w[nod].size() ; i++){ vecin = w[nod][i]; if (!f[vecin]){ dfs(vecin); under[nod] += under[vecin] - 1; sum += under[vecin]; two[nod] += two[vecin]; } else tata = vecin; } two[nod] = under[nod] * (under[nod] - 1)/2; //if (nod == 1) // printf ("a"); if (nod > n){ /// nod sum = under[nod]; for (i = 0 ; i < w[nod].size() ; i++){ vecin = w[nod][i]; if (vecin != tata){ val = val + 2 * (under[vecin] - 1) * (sum - under[vecin]); //val = val + two[vecin] - under[vecin] + 1; } } } else { /// componenta if (sol[bicnx - nod + 1].size() >= 3){ x = sol[bicnx - nod + 1].size(); val = val + x * (x - 1) * (x - 2); /// iei 3 din aceeasi comp, CU noduri critice!!! } x = sol[bicnx - nod + 1].size(); for (i = 0 ; i < w[nod].size() ; i++){ vecin = w[nod][i]; if (vecin != tata){ /// din subarborele lui vecin iau 2, din alt subarbore iau unul val = val + 2 * (sum - under[vecin]) * two[vecin]; val = val + 2 * x * ( two[vecin] - under[vecin] ); if (x >= 2){ val = val + 2 * x * (x - 1) * ( under[vecin] - 1 ); } } } } //printf ("%lld %lld\n" , nod , val); } int main() { FILE *fin=stdin; FILE *fout=stdout; long long m , i , x , y , nod; fscanf (fin,"%lld%lld",&n,&m); for (i=1;i<=m;i++){ fscanf (fin,"%lld%lld",&x,&y); v[x].push_back(y); v[y].push_back(x); } for (i = 1 ; i <= n ; i++){ if (!lvl[i]){ lvl[i] = 1; dfs_bic (i , 0); } } /// taken[nod] > 1 => nod critic for (i = 1 ; i <= bicnx ; i++){ for (set <long long> :: iterator it = sol[i].begin() ; it != sol[i].end() ; it++){ nod = *it; nod += n; if (taken[nod - n] > 1){ w[nod].push_back(bicnx - i + 1); w[bicnx - i + 1].push_back(nod); } } } /// w e arborele componentelor biconexe /// sau sunt mai multi arbori daca graful nu era conex for (i = 1 ; i <= bicnx ; i++){ if (!f[i]){ dfs (i); } } fprintf (fout,"%lld",val); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

count_triplets.cpp: In function 'void dfs_bic(long long int, long long int)':
count_triplets.cpp:14:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[nod].size();i++){
              ~^~~~~~~~~~~~~~
count_triplets.cpp: In function 'void dfs(long long int)':
count_triplets.cpp:61:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0 ; i < w[nod].size() ; i++){
                  ~~^~~~~~~~~~~~~~~
count_triplets.cpp:84:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0 ; i < w[nod].size() ; i++){
                      ~~^~~~~~~~~~~~~~~
count_triplets.cpp:110:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0 ; i < w[nod].size() ; i++){
                      ~~^~~~~~~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:139:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%lld%lld",&n,&m);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
count_triplets.cpp:141:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%lld%lld",&x,&y);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...