답안 #51116 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
51116	2018-06-16T05:44:42 Z	Utaha	철인 이종 경기 (APIO18_duathlon)	C++14	31 / 100	305 ms	49392 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];

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

void dfs(int u,int t,int p){
	comp.pb(u);
	vis[u]=1;
	tg[u]=t;
	low[u]=u;
	for(int v:child[u]) if(v!=p){
		if(vis[v]){
			if(tg[low[u]]>tg[v]) low[u]=v;
			q.pb(MP(u,v));
		}
		else{
			q.pb(MP(u,v));
			dfs(v,t+1,u);
			if(tg[low[u]]>tg[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);

		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	14460 KB	Output is correct
2	Correct	13 ms	14460 KB	Output is correct
3	Correct	12 ms	14508 KB	Output is correct
4	Correct	13 ms	14552 KB	Output is correct
5	Correct	13 ms	14656 KB	Output is correct
6	Correct	13 ms	14656 KB	Output is correct
7	Correct	13 ms	14692 KB	Output is correct
8	Incorrect	14 ms	14704 KB	Output isn't correct
9	Halted	0 ms	0 KB	-

Subtask #2
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	14460 KB	Output is correct
2	Correct	13 ms	14460 KB	Output is correct
3	Correct	12 ms	14508 KB	Output is correct
4	Correct	13 ms	14552 KB	Output is correct
5	Correct	13 ms	14656 KB	Output is correct
6	Correct	13 ms	14656 KB	Output is correct
7	Correct	13 ms	14692 KB	Output is correct
8	Incorrect	14 ms	14704 KB	Output isn't correct
9	Halted	0 ms	0 KB	-

Subtask #3
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	195 ms	36332 KB	Output is correct
2	Correct	222 ms	36332 KB	Output is correct
3	Correct	238 ms	36332 KB	Output is correct
4	Correct	200 ms	36332 KB	Output is correct
5	Correct	223 ms	36332 KB	Output is correct
6	Correct	224 ms	37436 KB	Output is correct
7	Correct	227 ms	37436 KB	Output is correct
8	Correct	216 ms	37436 KB	Output is correct
9	Correct	202 ms	37436 KB	Output is correct
10	Correct	197 ms	37436 KB	Output is correct
11	Correct	156 ms	37436 KB	Output is correct
12	Correct	151 ms	37436 KB	Output is correct
13	Correct	199 ms	37436 KB	Output is correct
14	Correct	142 ms	37436 KB	Output is correct
15	Correct	115 ms	37436 KB	Output is correct
16	Correct	121 ms	37436 KB	Output is correct
17	Correct	19 ms	37436 KB	Output is correct
18	Correct	17 ms	37436 KB	Output is correct
19	Correct	17 ms	37436 KB	Output is correct
20	Correct	16 ms	37436 KB	Output is correct
21	Correct	16 ms	37436 KB	Output is correct
22	Correct	17 ms	37436 KB	Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	222 ms	37436 KB	Output is correct
2	Correct	223 ms	37436 KB	Output is correct
3	Correct	221 ms	37436 KB	Output is correct
4	Correct	215 ms	37436 KB	Output is correct
5	Correct	210 ms	37436 KB	Output is correct
6	Correct	292 ms	49392 KB	Output is correct
7	Correct	259 ms	49392 KB	Output is correct
8	Correct	268 ms	49392 KB	Output is correct
9	Correct	239 ms	49392 KB	Output is correct
10	Correct	209 ms	49392 KB	Output is correct
11	Correct	211 ms	49392 KB	Output is correct
12	Correct	210 ms	49392 KB	Output is correct
13	Correct	278 ms	49392 KB	Output is correct
14	Correct	195 ms	49392 KB	Output is correct
15	Correct	173 ms	49392 KB	Output is correct
16	Correct	101 ms	49392 KB	Output is correct
17	Correct	165 ms	49392 KB	Output is correct
18	Correct	163 ms	49392 KB	Output is correct
19	Correct	161 ms	49392 KB	Output is correct
20	Correct	159 ms	49392 KB	Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	230 ms	49392 KB	Output is correct
2	Correct	207 ms	49392 KB	Output is correct
3	Correct	237 ms	49392 KB	Output is correct
4	Correct	305 ms	49392 KB	Output is correct
5	Incorrect	278 ms	49392 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #8
0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	14460 KB	Output is correct
2	Correct	13 ms	14460 KB	Output is correct
3	Correct	12 ms	14508 KB	Output is correct
4	Correct	13 ms	14552 KB	Output is correct
5	Correct	13 ms	14656 KB	Output is correct
6	Correct	13 ms	14656 KB	Output is correct
7	Correct	13 ms	14692 KB	Output is correct
8	Incorrect	14 ms	14704 KB	Output isn't correct
9	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	14460 KB	Output is correct
2	Correct	13 ms	14460 KB	Output is correct
3	Correct	12 ms	14508 KB	Output is correct
4	Correct	13 ms	14552 KB	Output is correct
5	Correct	13 ms	14656 KB	Output is correct
6	Correct	13 ms	14656 KB	Output is correct
7	Correct	13 ms	14692 KB	Output is correct
8	Incorrect	14 ms	14704 KB	Output isn't correct
9	Halted	0 ms	0 KB	-

답안 #51116

Compilation message