답안 #51120 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
51120	2018-06-16T06:02:44 Z	Utaha	철인 이종 경기 (APIO18_duathlon)	C++14	31 / 100	319 ms	49576 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 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;
	low[u]=u;
	h[u]=H;
	for(int v:child[u]) if(v!=p){
		q.pb(MP(u,v));
		if(vis[v]){
			if(h[low[u]]>h[v]) low[u]=v;
		}
		else{
			dfs(v,t+1,u,H+1);
			if(h[low[v]]>=h[u]){
				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++;
			}
			if(h[low[u]]>h[low[v]]) low[u]=low[v];
		}
	}
}
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
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	14456 KB	Output is correct
2	Correct	15 ms	14564 KB	Output is correct
3	Correct	15 ms	14564 KB	Output is correct
4	Correct	14 ms	14564 KB	Output is correct
5	Correct	15 ms	14564 KB	Output is correct
6	Correct	16 ms	14676 KB	Output is correct
7	Correct	17 ms	14676 KB	Output is correct
8	Incorrect	14 ms	14676 KB	Output isn't correct
9	Halted	0 ms	0 KB	-

Subtask #2
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	14456 KB	Output is correct
2	Correct	15 ms	14564 KB	Output is correct
3	Correct	15 ms	14564 KB	Output is correct
4	Correct	14 ms	14564 KB	Output is correct
5	Correct	15 ms	14564 KB	Output is correct
6	Correct	16 ms	14676 KB	Output is correct
7	Correct	17 ms	14676 KB	Output is correct
8	Incorrect	14 ms	14676 KB	Output isn't correct
9	Halted	0 ms	0 KB	-

Subtask #3
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	208 ms	36180 KB	Output is correct
2	Correct	197 ms	36248 KB	Output is correct
3	Correct	292 ms	36388 KB	Output is correct
4	Correct	215 ms	36388 KB	Output is correct
5	Correct	212 ms	36388 KB	Output is correct
6	Correct	261 ms	37368 KB	Output is correct
7	Correct	217 ms	37368 KB	Output is correct
8	Correct	220 ms	37368 KB	Output is correct
9	Correct	199 ms	37368 KB	Output is correct
10	Correct	198 ms	37368 KB	Output is correct
11	Correct	161 ms	37368 KB	Output is correct
12	Correct	158 ms	37368 KB	Output is correct
13	Correct	139 ms	37368 KB	Output is correct
14	Correct	146 ms	37368 KB	Output is correct
15	Correct	106 ms	37368 KB	Output is correct
16	Correct	138 ms	37368 KB	Output is correct
17	Correct	23 ms	37368 KB	Output is correct
18	Correct	23 ms	37368 KB	Output is correct
19	Correct	19 ms	37368 KB	Output is correct
20	Correct	16 ms	37368 KB	Output is correct
21	Correct	22 ms	37368 KB	Output is correct
22	Correct	18 ms	37368 KB	Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	241 ms	37368 KB	Output is correct
2	Correct	215 ms	37368 KB	Output is correct
3	Correct	303 ms	37368 KB	Output is correct
4	Correct	277 ms	37368 KB	Output is correct
5	Correct	267 ms	37368 KB	Output is correct
6	Correct	245 ms	49576 KB	Output is correct
7	Correct	317 ms	49576 KB	Output is correct
8	Correct	272 ms	49576 KB	Output is correct
9	Correct	287 ms	49576 KB	Output is correct
10	Correct	253 ms	49576 KB	Output is correct
11	Correct	252 ms	49576 KB	Output is correct
12	Correct	319 ms	49576 KB	Output is correct
13	Correct	223 ms	49576 KB	Output is correct
14	Correct	166 ms	49576 KB	Output is correct
15	Correct	152 ms	49576 KB	Output is correct
16	Correct	139 ms	49576 KB	Output is correct
17	Correct	156 ms	49576 KB	Output is correct
18	Correct	216 ms	49576 KB	Output is correct
19	Correct	208 ms	49576 KB	Output is correct
20	Correct	150 ms	49576 KB	Output is correct

Subtask #6
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	49576 KB	Output is correct
2	Correct	14 ms	49576 KB	Output is correct
3	Correct	15 ms	49576 KB	Output is correct
4	Correct	15 ms	49576 KB	Output is correct
5	Correct	14 ms	49576 KB	Output is correct
6	Incorrect	14 ms	49576 KB	Output isn't correct
7	Halted	0 ms	0 KB	-

Subtask #7
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	247 ms	49576 KB	Output is correct
2	Correct	272 ms	49576 KB	Output is correct
3	Correct	268 ms	49576 KB	Output is correct
4	Correct	275 ms	49576 KB	Output is correct
5	Incorrect	276 ms	49576 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #8
0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	14456 KB	Output is correct
2	Correct	15 ms	14564 KB	Output is correct
3	Correct	15 ms	14564 KB	Output is correct
4	Correct	14 ms	14564 KB	Output is correct
5	Correct	15 ms	14564 KB	Output is correct
6	Correct	16 ms	14676 KB	Output is correct
7	Correct	17 ms	14676 KB	Output is correct
8	Incorrect	14 ms	14676 KB	Output isn't correct
9	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	14456 KB	Output is correct
2	Correct	15 ms	14564 KB	Output is correct
3	Correct	15 ms	14564 KB	Output is correct
4	Correct	14 ms	14564 KB	Output is correct
5	Correct	15 ms	14564 KB	Output is correct
6	Correct	16 ms	14676 KB	Output is correct
7	Correct	17 ms	14676 KB	Output is correct
8	Incorrect	14 ms	14676 KB	Output isn't correct
9	Halted	0 ms	0 KB	-

답안 #51120

Compilation message