답안 #51117 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
51117	2018-06-16T05:46:18 Z	Utaha	철인 이종 경기 (APIO18_duathlon)	C++14	71 / 100	374 ms	50032 KB

count_triplets

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define F first
#define S second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define pb push_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#ifdef leowang
#define debug(...) do{\
	fprintf(stderr,"%s - %d : (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
	_DO(__VA_ARGS__);\
}while(0)
template<typename I> void _DO(I&&x){cerr<<x<<endl;}
template<typename I,typename...T> void _DO(I&&x,T&&...tail){cerr<<x<<", ";_DO(tail...);}
#else
#define debug(...)
#endif
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
	out<<'('<<P.F<<','<<P.S<<')';
	return out;
}
//}}}
const ll maxn=200005;
const ll maxlg=__lg(maxn)+2;
const ll INF64=8000000000000000000LL;
const int INF=0x3f3f3f3f;
const ll MOD=ll(1e9+7);
const double PI=acos(-1);
//const ll p=880301;
//const ll P=31;

ll mypow(ll a,ll b){
	ll res=1LL;
	while(b){
		if(b&1) res=res*a%MOD;
		a=a*a%MOD;
		b>>=1;
	}
	return res;
}
vector<int> comp;
vector<int> child[maxn];
bool vis[maxn];

int tg[maxn];
int low[maxn];
int h[maxn];

vector<int> id[maxn];
int BCCpt=0;
vector<pii> q;
vector<int> curBCC;
ll sz[maxn];

void dfs(int u,int t,int p,int H){
	comp.pb(u);
	vis[u]=1;
	tg[u]=t;
	low[u]=u;
	h[u]=H;
	for(int v:child[u]) if(v!=p){
		if(vis[v]){
			if(h[low[u]]>h[v]) low[u]=v;
		}
		else{
			q.pb(MP(u,v));
			dfs(v,t+1,u,H+1);
			if(h[low[u]]>h[low[v]]) low[u]=low[v];
			else{
				curBCC.clear();
				while(SZ(q)){
					pii tmp=q.back();
					curBCC.pb(tmp.F);
					curBCC.pb(tmp.S);
					q.pop_back();
					if(tmp==MP(u,v)) break;
				}
				SORT_UNIQUE(curBCC);
				for(int i:curBCC) id[i].pb(BCCpt);
				BCCpt++;
			}
		}
	}
}
vector<int> G[maxn];
ll ans=0;
bool bis[maxn];
ll dfs(int u,bool isthin){
	bis[u]=1;
	ll rem=SZ(comp)-sz[u];
	ll tt=(ll)rem*rem;
	ll sq=0;
	ll cnt=0;
	for(int v:G[u]) if(!bis[v]){
		ll tmp=dfs(v,!isthin);
		cnt++;
		rem-=tmp;
		tt-=(ll)tmp*tmp;
		sq+=(ll)tmp*tmp;
	}
	tt-=(ll) rem*rem;
	ans+=tt*sz[u];

	ans+=(ll)sz[u]*(sz[u]-1)*(SZ(comp)-sz[u])*2;
	ans+=(ll)sz[u]*(sz[u]-1)*(sz[u]-2);

	if(rem!=0){
		cnt++;
		sq+=(ll) rem*rem;
	}

	if(isthin){
		ll tmp=(ll)cnt*SZ(comp)*SZ(comp)-(ll)cnt*sq+2LL*sq-2LL*SZ(comp)*(SZ(comp)-sz[u])-(ll)cnt*sz[u];
		//cout<<u<<' '<<tmp<<'\n';
		ans+=tmp;
	}
	//cout<<u<<' '<<ans<<'\n';
	return SZ(comp)-rem;
}

int main()
{
	//IOS;
	int n;
	int m;
	cin>>n>>m;
	REP(i,m){
		int u,v;
		cin>>u>>v;
		u--;v--;
		child[u].pb(v);
		child[v].pb(u);
	}
	REP(x,n) if(!vis[x]){
		comp.clear();
		dfs(x,0,-1,0);

		REP(i,BCCpt) sz[i]=0;
		for(int i:comp){	
			if(SZ(id[i])==1){
				sz[id[i][0]]++;
			}
			else{
				int u=BCCpt++;
				for(int v:id[i]){
					G[u].pb(v);
					G[v].pb(u);
				}
				sz[u]=1;
			}
		}
		
		dfs(0,1);
		REP(i,BCCpt){
			bis[i]=0;
			G[i].clear();
		}
		BCCpt=0;
	}
	cout<<ans;
	return 0;
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	14420 KB	Output is correct
2	Correct	14 ms	14532 KB	Output is correct
3	Correct	17 ms	14644 KB	Output is correct
4	Correct	17 ms	14708 KB	Output is correct
5	Correct	13 ms	14708 KB	Output is correct
6	Correct	13 ms	14708 KB	Output is correct
7	Correct	14 ms	14708 KB	Output is correct
8	Correct	17 ms	14708 KB	Output is correct
9	Correct	15 ms	14784 KB	Output is correct
10	Correct	14 ms	14784 KB	Output is correct
11	Correct	15 ms	14784 KB	Output is correct
12	Correct	15 ms	14816 KB	Output is correct
13	Correct	13 ms	14816 KB	Output is correct
14	Correct	14 ms	14816 KB	Output is correct
15	Correct	14 ms	14816 KB	Output is correct
16	Correct	14 ms	14816 KB	Output is correct
17	Correct	14 ms	14816 KB	Output is correct
18	Correct	14 ms	14840 KB	Output is correct
19	Correct	15 ms	14840 KB	Output is correct
20	Correct	15 ms	14840 KB	Output is correct
21	Correct	14 ms	14840 KB	Output is correct
22	Correct	16 ms	14840 KB	Output is correct
23	Correct	15 ms	14840 KB	Output is correct
24	Correct	14 ms	14840 KB	Output is correct
25	Correct	17 ms	14840 KB	Output is correct
26	Correct	15 ms	14840 KB	Output is correct
27	Correct	15 ms	14840 KB	Output is correct
28	Correct	13 ms	14840 KB	Output is correct
29	Correct	15 ms	14840 KB	Output is correct
30	Correct	14 ms	14840 KB	Output is correct
31	Correct	15 ms	14840 KB	Output is correct
32	Correct	15 ms	14840 KB	Output is correct
33	Correct	16 ms	14840 KB	Output is correct
34	Correct	17 ms	14840 KB	Output is correct
35	Correct	15 ms	14840 KB	Output is correct

Subtask #2
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	14420 KB	Output is correct
2	Correct	14 ms	14532 KB	Output is correct
3	Correct	17 ms	14644 KB	Output is correct
4	Correct	17 ms	14708 KB	Output is correct
5	Correct	13 ms	14708 KB	Output is correct
6	Correct	13 ms	14708 KB	Output is correct
7	Correct	14 ms	14708 KB	Output is correct
8	Correct	17 ms	14708 KB	Output is correct
9	Correct	15 ms	14784 KB	Output is correct
10	Correct	14 ms	14784 KB	Output is correct
11	Correct	15 ms	14784 KB	Output is correct
12	Correct	15 ms	14816 KB	Output is correct
13	Correct	13 ms	14816 KB	Output is correct
14	Correct	14 ms	14816 KB	Output is correct
15	Correct	14 ms	14816 KB	Output is correct
16	Correct	14 ms	14816 KB	Output is correct
17	Correct	14 ms	14816 KB	Output is correct
18	Correct	14 ms	14840 KB	Output is correct
19	Correct	15 ms	14840 KB	Output is correct
20	Correct	15 ms	14840 KB	Output is correct
21	Correct	14 ms	14840 KB	Output is correct
22	Correct	16 ms	14840 KB	Output is correct
23	Correct	15 ms	14840 KB	Output is correct
24	Correct	14 ms	14840 KB	Output is correct
25	Correct	17 ms	14840 KB	Output is correct
26	Correct	15 ms	14840 KB	Output is correct
27	Correct	15 ms	14840 KB	Output is correct
28	Correct	13 ms	14840 KB	Output is correct
29	Correct	15 ms	14840 KB	Output is correct
30	Correct	14 ms	14840 KB	Output is correct
31	Correct	15 ms	14840 KB	Output is correct
32	Correct	15 ms	14840 KB	Output is correct
33	Correct	16 ms	14840 KB	Output is correct
34	Correct	17 ms	14840 KB	Output is correct
35	Correct	15 ms	14840 KB	Output is correct
36	Correct	14 ms	14840 KB	Output is correct
37	Correct	15 ms	14840 KB	Output is correct
38	Incorrect	15 ms	14840 KB	Output isn't correct
39	Halted	0 ms	0 KB	-

Subtask #3
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	236 ms	36744 KB	Output is correct
2	Correct	254 ms	36884 KB	Output is correct
3	Correct	277 ms	36884 KB	Output is correct
4	Correct	215 ms	36884 KB	Output is correct
5	Correct	222 ms	36884 KB	Output is correct
6	Correct	316 ms	37876 KB	Output is correct
7	Correct	234 ms	37876 KB	Output is correct
8	Correct	239 ms	37876 KB	Output is correct
9	Correct	268 ms	37876 KB	Output is correct
10	Correct	215 ms	37876 KB	Output is correct
11	Correct	167 ms	37876 KB	Output is correct
12	Correct	180 ms	37876 KB	Output is correct
13	Correct	164 ms	37876 KB	Output is correct
14	Correct	160 ms	37876 KB	Output is correct
15	Correct	143 ms	37876 KB	Output is correct
16	Correct	134 ms	37876 KB	Output is correct
17	Correct	20 ms	37876 KB	Output is correct
18	Correct	20 ms	37876 KB	Output is correct
19	Correct	18 ms	37876 KB	Output is correct
20	Correct	20 ms	37876 KB	Output is correct
21	Correct	17 ms	37876 KB	Output is correct
22	Correct	18 ms	37876 KB	Output is correct

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	15 ms	37876 KB	Output is correct
2	Correct	15 ms	37876 KB	Output is correct
3	Correct	16 ms	37876 KB	Output is correct
4	Correct	20 ms	37876 KB	Output is correct
5	Correct	17 ms	37876 KB	Output is correct
6	Correct	17 ms	37876 KB	Output is correct
7	Correct	16 ms	37876 KB	Output is correct
8	Correct	16 ms	37876 KB	Output is correct
9	Correct	17 ms	37876 KB	Output is correct
10	Correct	20 ms	37876 KB	Output is correct
11	Correct	16 ms	37876 KB	Output is correct
12	Correct	15 ms	37876 KB	Output is correct
13	Correct	17 ms	37876 KB	Output is correct
14	Correct	18 ms	37876 KB	Output is correct
15	Correct	15 ms	37876 KB	Output is correct
16	Correct	15 ms	37876 KB	Output is correct
17	Correct	17 ms	37876 KB	Output is correct
18	Correct	15 ms	37876 KB	Output is correct
19	Correct	14 ms	37876 KB	Output is correct
20	Correct	18 ms	37876 KB	Output is correct

Subtask #5
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	269 ms	37876 KB	Output is correct
2	Correct	222 ms	37876 KB	Output is correct
3	Correct	241 ms	37876 KB	Output is correct
4	Correct	227 ms	37876 KB	Output is correct
5	Correct	245 ms	37876 KB	Output is correct
6	Correct	276 ms	50032 KB	Output is correct
7	Correct	265 ms	50032 KB	Output is correct
8	Correct	263 ms	50032 KB	Output is correct
9	Correct	263 ms	50032 KB	Output is correct
10	Correct	362 ms	50032 KB	Output is correct
11	Correct	240 ms	50032 KB	Output is correct
12	Correct	252 ms	50032 KB	Output is correct
13	Correct	260 ms	50032 KB	Output is correct
14	Correct	208 ms	50032 KB	Output is correct
15	Correct	189 ms	50032 KB	Output is correct
16	Correct	136 ms	50032 KB	Output is correct
17	Correct	174 ms	50032 KB	Output is correct
18	Correct	200 ms	50032 KB	Output is correct
19	Correct	172 ms	50032 KB	Output is correct
20	Correct	186 ms	50032 KB	Output is correct

Subtask #6
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	14 ms	50032 KB	Output is correct
2	Correct	17 ms	50032 KB	Output is correct
3	Correct	15 ms	50032 KB	Output is correct
4	Correct	16 ms	50032 KB	Output is correct
5	Correct	16 ms	50032 KB	Output is correct
6	Correct	15 ms	50032 KB	Output is correct
7	Correct	14 ms	50032 KB	Output is correct
8	Correct	17 ms	50032 KB	Output is correct
9	Correct	17 ms	50032 KB	Output is correct
10	Correct	15 ms	50032 KB	Output is correct
11	Correct	18 ms	50032 KB	Output is correct
12	Correct	19 ms	50032 KB	Output is correct
13	Correct	16 ms	50032 KB	Output is correct
14	Correct	15 ms	50032 KB	Output is correct
15	Correct	17 ms	50032 KB	Output is correct
16	Correct	16 ms	50032 KB	Output is correct
17	Correct	16 ms	50032 KB	Output is correct
18	Correct	17 ms	50032 KB	Output is correct
19	Correct	16 ms	50032 KB	Output is correct
20	Correct	16 ms	50032 KB	Output is correct
21	Correct	16 ms	50032 KB	Output is correct
22	Correct	19 ms	50032 KB	Output is correct
23	Correct	16 ms	50032 KB	Output is correct
24	Correct	18 ms	50032 KB	Output is correct
25	Correct	15 ms	50032 KB	Output is correct
26	Correct	16 ms	50032 KB	Output is correct
27	Correct	16 ms	50032 KB	Output is correct

Subtask #7
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	241 ms	50032 KB	Output is correct
2	Correct	254 ms	50032 KB	Output is correct
3	Correct	300 ms	50032 KB	Output is correct
4	Correct	244 ms	50032 KB	Output is correct
5	Correct	248 ms	50032 KB	Output is correct
6	Correct	298 ms	50032 KB	Output is correct
7	Correct	223 ms	50032 KB	Output is correct
8	Correct	204 ms	50032 KB	Output is correct
9	Correct	214 ms	50032 KB	Output is correct
10	Correct	201 ms	50032 KB	Output is correct
11	Correct	239 ms	50032 KB	Output is correct
12	Correct	221 ms	50032 KB	Output is correct
13	Correct	191 ms	50032 KB	Output is correct
14	Correct	199 ms	50032 KB	Output is correct
15	Correct	261 ms	50032 KB	Output is correct
16	Correct	268 ms	50032 KB	Output is correct
17	Correct	374 ms	50032 KB	Output is correct
18	Correct	328 ms	50032 KB	Output is correct
19	Correct	256 ms	50032 KB	Output is correct
20	Correct	255 ms	50032 KB	Output is correct
21	Correct	244 ms	50032 KB	Output is correct
22	Correct	212 ms	50032 KB	Output is correct
23	Correct	223 ms	50032 KB	Output is correct
24	Correct	209 ms	50032 KB	Output is correct
25	Correct	215 ms	50032 KB	Output is correct
26	Correct	233 ms	50032 KB	Output is correct
27	Correct	260 ms	50032 KB	Output is correct

Subtask #8
0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	14420 KB	Output is correct
2	Correct	14 ms	14532 KB	Output is correct
3	Correct	17 ms	14644 KB	Output is correct
4	Correct	17 ms	14708 KB	Output is correct
5	Correct	13 ms	14708 KB	Output is correct
6	Correct	13 ms	14708 KB	Output is correct
7	Correct	14 ms	14708 KB	Output is correct
8	Correct	17 ms	14708 KB	Output is correct
9	Correct	15 ms	14784 KB	Output is correct
10	Correct	14 ms	14784 KB	Output is correct
11	Correct	15 ms	14784 KB	Output is correct
12	Correct	15 ms	14816 KB	Output is correct
13	Correct	13 ms	14816 KB	Output is correct
14	Correct	14 ms	14816 KB	Output is correct
15	Correct	14 ms	14816 KB	Output is correct
16	Correct	14 ms	14816 KB	Output is correct
17	Correct	14 ms	14816 KB	Output is correct
18	Correct	14 ms	14840 KB	Output is correct
19	Correct	15 ms	14840 KB	Output is correct
20	Correct	15 ms	14840 KB	Output is correct
21	Correct	14 ms	14840 KB	Output is correct
22	Correct	16 ms	14840 KB	Output is correct
23	Correct	15 ms	14840 KB	Output is correct
24	Correct	14 ms	14840 KB	Output is correct
25	Correct	17 ms	14840 KB	Output is correct
26	Correct	15 ms	14840 KB	Output is correct
27	Correct	15 ms	14840 KB	Output is correct
28	Correct	13 ms	14840 KB	Output is correct
29	Correct	15 ms	14840 KB	Output is correct
30	Correct	14 ms	14840 KB	Output is correct
31	Correct	15 ms	14840 KB	Output is correct
32	Correct	15 ms	14840 KB	Output is correct
33	Correct	16 ms	14840 KB	Output is correct
34	Correct	17 ms	14840 KB	Output is correct
35	Correct	15 ms	14840 KB	Output is correct
36	Correct	14 ms	14840 KB	Output is correct
37	Correct	15 ms	14840 KB	Output is correct
38	Incorrect	15 ms	14840 KB	Output isn't correct
39	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	14420 KB	Output is correct
2	Correct	14 ms	14532 KB	Output is correct
3	Correct	17 ms	14644 KB	Output is correct
4	Correct	17 ms	14708 KB	Output is correct
5	Correct	13 ms	14708 KB	Output is correct
6	Correct	13 ms	14708 KB	Output is correct
7	Correct	14 ms	14708 KB	Output is correct
8	Correct	17 ms	14708 KB	Output is correct
9	Correct	15 ms	14784 KB	Output is correct
10	Correct	14 ms	14784 KB	Output is correct
11	Correct	15 ms	14784 KB	Output is correct
12	Correct	15 ms	14816 KB	Output is correct
13	Correct	13 ms	14816 KB	Output is correct
14	Correct	14 ms	14816 KB	Output is correct
15	Correct	14 ms	14816 KB	Output is correct
16	Correct	14 ms	14816 KB	Output is correct
17	Correct	14 ms	14816 KB	Output is correct
18	Correct	14 ms	14840 KB	Output is correct
19	Correct	15 ms	14840 KB	Output is correct
20	Correct	15 ms	14840 KB	Output is correct
21	Correct	14 ms	14840 KB	Output is correct
22	Correct	16 ms	14840 KB	Output is correct
23	Correct	15 ms	14840 KB	Output is correct
24	Correct	14 ms	14840 KB	Output is correct
25	Correct	17 ms	14840 KB	Output is correct
26	Correct	15 ms	14840 KB	Output is correct
27	Correct	15 ms	14840 KB	Output is correct
28	Correct	13 ms	14840 KB	Output is correct
29	Correct	15 ms	14840 KB	Output is correct
30	Correct	14 ms	14840 KB	Output is correct
31	Correct	15 ms	14840 KB	Output is correct
32	Correct	15 ms	14840 KB	Output is correct
33	Correct	16 ms	14840 KB	Output is correct
34	Correct	17 ms	14840 KB	Output is correct
35	Correct	15 ms	14840 KB	Output is correct
36	Correct	14 ms	14840 KB	Output is correct
37	Correct	15 ms	14840 KB	Output is correct
38	Incorrect	15 ms	14840 KB	Output isn't correct
39	Halted	0 ms	0 KB	-

답안 #51117

Compilation message