이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define DIMN 100005
#define DIMM 200005
using namespace std;
int low[DIMN] , bicnx , lvl[DIMN] , taken[DIMN] , f[DIMN] , two[DIMN] , under[DIMN];
stack <int> st;
vector <int> v[DIMN] , w[2 * DIMN];
set <int> sol[DIMN];
int x , n , val;
void dfs_bic (int nod,int tt){
int 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 (int nod){
int sum , i , vecin , tata=0;
//printf ("%d ",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 ("%d %d\n" , nod , val);
}
int main()
{
FILE *fin = stdin;
FILE *fout = stdout;
int m , i , x , y , nod;
fscanf (fin,"%d%d",&n,&m);
for (i=1;i<=m;i++){
fscanf (fin,"%d%d",&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 <int> :: 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,"%d",val);
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
count_triplets.cpp: In function 'void dfs_bic(int, 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(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,"%d%d",&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,"%d%d",&x,&y);
~~~~~~~^~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |