답안 #97064 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
97064	2019-02-13T16:26:33 Z	fefe	철인 이종 경기 (APIO18_duathlon)	C++17	8 / 100	215 ms	29504 KB

count_triplets

#include<bits/stdc++.h>
#define MAX_N 100005
#define MAX_M 200005
#define pb push_back
#define mp make_pair
#define all(V) (V).begin(),(V).end()
#define reset(V) (V).clear();(V).resize(0);
#define sq(x) ((x)*(x))
#define abs(x) ((x)>0?(x):(-(x)))
#define fi first
#define se second
#define LL_inf (1LL<<60)
#define full_inf 0x7fffffff
#define half_inf 0x3fffffff
#define inf 0x3fffffff
#define MOD 1000000007LL
#define cpx_mod(x) (((LD)(((LL)x.real())%MOD)),((LD)(((LL)x.imag())%MOD)))
using namespace std;
typedef long long LL;
typedef long double LD;
typedef pair<int,int> pii;
typedef pair<LL,LL> pil;
typedef pair<LL,string> pls;
typedef complex<LD> Complex;
typedef long double LD;
int n,m,ln,dep[MAX_N],loc[MAX_N],val[MAX_N];
LL ans;
bool vis[MAX_N];
vector<int> E[MAX_N],L,lst[MAX_N];
vector<pii> bcc[MAX_N];
void merge(int x,int y){
	int p,q;
	p=loc[x];
	q=loc[y];
	if(bcc[p].size()<bcc[q].size())	swap(p,q);
	loc[x]=p;
	while(bcc[q].size()){
		bcc[p].pb(bcc[q].back());		
		bcc[q].pop_back();
	}
}
int make_bcc(int x){
	int z=dep[x]-1,k;
	m++;
	loc[x]=ln++;
	bcc[loc[x]].pb({x,0});
	for(int y:E[x]){
		if(dep[y]){
			z=min(z,dep[y]);
			continue;
		}
		dep[y]=dep[x]+1;
		k=make_bcc(y);
		z=min(z,k);
		if(k==dep[x]){
			bcc[loc[y]].pb({x,0});
			L.pb(loc[y]);
			continue;
		}
		merge(x,y);
	}
	return z;
}
int dfs(int x,int y){
	int sum=0;
	vis[x]=true;
	for(pii &p:bcc[x]){
		p.se++;
		if(p.fi==y)	continue;
		for(int q:lst[p.fi]){
			if(vis[q])	continue;
			p.se+=dfs(q,p.fi)-1;
		}
	}
	for(pii p:bcc[x])	sum+=p.se;
	for(pii &p:bcc[x]){
		if(p.fi==y)	p.se=m-sum+1;
		ans+=((LL)(bcc[x].size()-2))*(LL)p.se*((LL)(m-p.se));
		ans+=2*((LL)val[p.fi])*((LL)(p.se-1));
		val[p.fi]+=(p.se-1);
	}
	return sum;
}
int main(){
	int i,x,y;
	scanf("%d %d",&n,&m);
	for(i=0;i<m;i++){
		scanf("%d %d",&x,&y);
		E[x].pb(y);
		E[y].pb(x);
	}
	for(i=1;i<=n;i++){
		if(dep[i])	continue;
		L.clear();
		L.resize(0);
		dep[i]=1;
		m=0;
		make_bcc(i);
		if(m<2)	continue;
		for(int p:L){
			for(pii z:bcc[p]){
				lst[z.fi].pb(p);
			}
		}
		x=bcc[L[0]][0].fi;
		for(int q:lst[x]){
			dfs(q,x);
		}
	}
	
	
	
	for(i=1;i<=n;i++)	dep[i]=0;	//dep --> count node under me
	
	printf("%lld\n",ans);
	return 0;
}

Compilation message

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:86:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
count_triplets.cpp:88:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&x,&y);
   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	7552 KB	Output is correct
2	Correct	10 ms	7424 KB	Output is correct
3	Correct	11 ms	7424 KB	Output is correct
4	Correct	10 ms	7424 KB	Output is correct
5	Correct	10 ms	7424 KB	Output is correct
6	Correct	10 ms	7424 KB	Output is correct
7	Incorrect	10 ms	7424 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #2
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	7552 KB	Output is correct
2	Correct	10 ms	7424 KB	Output is correct
3	Correct	11 ms	7424 KB	Output is correct
4	Correct	10 ms	7424 KB	Output is correct
5	Correct	10 ms	7424 KB	Output is correct
6	Correct	10 ms	7424 KB	Output is correct
7	Incorrect	10 ms	7424 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #3
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	161 ms	29400 KB	Output is correct
2	Correct	195 ms	29504 KB	Output is correct
3	Correct	189 ms	24564 KB	Output is correct
4	Correct	164 ms	26984 KB	Output is correct
5	Correct	207 ms	23272 KB	Output is correct
6	Correct	214 ms	24180 KB	Output is correct
7	Correct	210 ms	21496 KB	Output is correct
8	Correct	204 ms	22772 KB	Output is correct
9	Correct	194 ms	20600 KB	Output is correct
10	Correct	200 ms	21496 KB	Output is correct
11	Correct	148 ms	19388 KB	Output is correct
12	Correct	136 ms	19192 KB	Output is correct
13	Correct	145 ms	19092 KB	Output is correct
14	Correct	150 ms	18680 KB	Output is correct
15	Correct	130 ms	17828 KB	Output is correct
16	Correct	103 ms	17528 KB	Output is correct
17	Correct	20 ms	11776 KB	Output is correct
18	Correct	23 ms	11776 KB	Output is correct
19	Correct	20 ms	11768 KB	Output is correct
20	Correct	20 ms	11904 KB	Output is correct
21	Correct	23 ms	11776 KB	Output is correct
22	Correct	19 ms	11648 KB	Output is correct

Subtask #4
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	12 ms	7424 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	161 ms	19952 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	13 ms	7680 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #7
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	215 ms	19972 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	7552 KB	Output is correct
2	Correct	10 ms	7424 KB	Output is correct
3	Correct	11 ms	7424 KB	Output is correct
4	Correct	10 ms	7424 KB	Output is correct
5	Correct	10 ms	7424 KB	Output is correct
6	Correct	10 ms	7424 KB	Output is correct
7	Incorrect	10 ms	7424 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	7552 KB	Output is correct
2	Correct	10 ms	7424 KB	Output is correct
3	Correct	11 ms	7424 KB	Output is correct
4	Correct	10 ms	7424 KB	Output is correct
5	Correct	10 ms	7424 KB	Output is correct
6	Correct	10 ms	7424 KB	Output is correct
7	Incorrect	10 ms	7424 KB	Output isn't correct
8	Halted	0 ms	0 KB	-