oj.uz

Submission #51120

# Submission time Handle Problem Language Result Execution time Memory
51120 2018-06-16T06:02:44 Z Utaha Duathlon (APIO18_duathlon) C++14
31 / 100
 319 ms 49576 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -