oj.uz

Submission #50342

# Submission time Handle Problem Language Result Execution time Memory
50342 2018-06-10T12:01:16 Z zscoder Duathlon (APIO18_duathlon) C++17
31 / 100
 273 ms 46508 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

vi adj[233113];
int disc[233113];
int low[233113];
vector<vector<ii> > bicon;
int timer;
stack<ii> st;
bool isconn[233113];
bool isart[233113];
int siz[510511];
vi tree[510511];
int n,m; 

void dfs(int u, int p)
{
	disc[u]=++timer; int child=0; low[u]=disc[u];
	for(int v:adj[u])
	{
		if(v==p) continue;
		if(!disc[v])
		{
			child++;
			st.push(mp(u,v));
			dfs(v,u);
			low[u] = min(low[u], low[v]);
			if((p==-1&&child>1)||(p!=-1&&low[v]>=disc[u]))
			{
				isart[u] = 1; bicon.pb(vector<ii>());
				while(!st.empty()&&st.top()!=mp(u,v))
				{
					bicon.back().pb(st.top()); st.pop();
				}
				bicon.back().pb(st.top()); st.pop();
			}
		}
		else if(disc[v]<disc[u])
		{
			low[u] = min(low[u], disc[v]);
			st.push(mp(u,v));
		}
	}
}

int dp[511211];
int vis[511511];
int cc; vi C;
int tot[511511];
int par[515115];
void prep_tree(int u, int p)
{
	C.pb(u); cc+=siz[u]; par[u]=p;
	dp[u] = siz[u]; vis[u]=1;
	for(int v:tree[u])
	{
		if(v==p) continue;
		prep_tree(v,u);
		dp[u]+=dp[v];
	}
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin>>n>>m; //do for each cc
	for(int i=0;i<m;i++)
	{
		int u,v; cin>>u>>v; u--; v--;
		adj[u].pb(v); adj[v].pb(u);
	}
	timer=1;
	for(int i=0;i<n;i++)
	{
		if(!disc[i]) 
		{
			dfs(i,-1);
			if(!st.empty())
			{
				bicon.pb(vector<ii>());
				while(!st.empty())
				{
					bicon.back().pb(st.top()); st.pop();
				}
			}
		}
	}
	for(int i=0;i<bicon.size();i++)
	{
		set<int> S; set<int> ss;
		for(ii v:bicon[i])
		{
			if(!isart[v.fi]) S.insert(v.fi);
			else ss.insert(v.fi);
			if(!isart[v.se]) S.insert(v.se);
			else ss.insert(v.se);
		}
		for(int j:ss) 
		{
			tree[j].pb(n+i); tree[n+i].pb(j);
			//cerr<<"ADD EDGE "<<j<<' '<<n+i<<'\n';
		}
		//cerr<<"BICON "<<n+i<<' '<<S.size()<<'\n';
		siz[n+i] = int(S.size()); //if cycle then alrdy +1
	}
	for(int i=0;i<n;i++)
	{
		siz[i]=1;
	}
	for(int i=0;i<n+bicon.size();i++)
	{
		if(!vis[i])
		{
			C.clear(); cc=0;
			prep_tree(i,-1);
			for(int v:C)
			{
				tot[v] = cc;
			}
		}
	}
	ll ans = 0;
	for(int i=0;i<n+bicon.size();i++)
	{
		if(i<n)
		{
			vi vec;
			for(int j:tree[i])
			{
				int v=dp[j];
				if(j==par[i])
				{
					v=tot[i]-dp[i];
				}
				vec.pb(v);
			}
			ll sos = 0; ll sum = 0;
			for(auto x:vec)
			{
				sos+=ll(x)*x;
				sum+=x;
			}
			ll res=0;
			res += sum*sum - sos;
			for(int j:tree[i])
			{
				res += siz[j]*(siz[j]-1);
			}
			ans+=res;
			//cerr<<"ANS "<<i<<' '<<res<<'\n';
		}
		else
		{
			ll sz = siz[i]; ll res=0;
			res += sz*(sz-1)*(sz-2); //all 3 from here
			res += 2LL*sz*(sz-1)*(tot[i]-sz); //here-here-out
			vi vec; int sm=0;
			int neigh=0;
			for(int j:tree[i])
			{
				neigh++;
				int v=dp[j];
				if(j==par[i])
				{
					v=tot[i]-dp[i];
				}
				//cerr<<v<<' ';
				vec.pb(v);
				sm+=v;
			}
			//cerr<<'\n';
			assert(sm==tot[i]-sz);
			ll sos = 0; ll sum = 0;
			for(auto x:vec)
			{
				sos+=ll(x)*x;
				sum+=x;
			}
			res += sz*(sum*sum-sos);//out-here-out
			res += ll(neigh-2)*(sum*sum-sos);
			for(int j:tree[i])
			{
				res += sz*siz[j]*(siz[j]-1);
			}
			//cerr<<"ANS "<<i<<' '<<res<<'\n';
			ans+=res;
		}
	}
	cout<<ans<<'\n';
}

Compilation message

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:98:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<bicon.size();i++)
              ~^~~~~~~~~~~~~
count_triplets.cpp:120:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<n+bicon.size();i++)
              ~^~~~~~~~~~~~~~~
count_triplets.cpp:133:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<n+bicon.size();i++)
              ~^~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 17912 KB Output is correct
2 Correct 15 ms 18028 KB Output is correct
3 Correct 15 ms 18028 KB Output is correct
4 Correct 16 ms 18028 KB Output is correct
5 Correct 16 ms 18028 KB Output is correct
6 Correct 17 ms 18028 KB Output is correct
7 Correct 16 ms 18028 KB Output is correct
8 Correct 15 ms 18028 KB Output is correct
9 Correct 15 ms 18028 KB Output is correct
10 Correct 16 ms 18028 KB Output is correct
11 Incorrect 16 ms 18028 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 17912 KB Output is correct
2 Correct 15 ms 18028 KB Output is correct
3 Correct 15 ms 18028 KB Output is correct
4 Correct 16 ms 18028 KB Output is correct
5 Correct 16 ms 18028 KB Output is correct
6 Correct 17 ms 18028 KB Output is correct
7 Correct 16 ms 18028 KB Output is correct
8 Correct 15 ms 18028 KB Output is correct
9 Correct 15 ms 18028 KB Output is correct
10 Correct 16 ms 18028 KB Output is correct
11 Incorrect 16 ms 18028 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 40296 KB Output is correct
2 Correct 155 ms 40536 KB Output is correct
3 Correct 164 ms 40536 KB Output is correct
4 Correct 202 ms 40536 KB Output is correct
5 Correct 142 ms 40536 KB Output is correct
6 Correct 196 ms 40536 KB Output is correct
7 Correct 177 ms 40536 KB Output is correct
8 Correct 182 ms 40536 KB Output is correct
9 Correct 171 ms 40536 KB Output is correct
10 Correct 205 ms 40536 KB Output is correct
11 Correct 115 ms 40536 KB Output is correct
12 Correct 109 ms 40536 KB Output is correct
13 Correct 170 ms 40536 KB Output is correct
14 Correct 140 ms 40536 KB Output is correct
15 Correct 75 ms 40536 KB Output is correct
16 Correct 103 ms 40536 KB Output is correct
17 Correct 20 ms 40536 KB Output is correct
18 Correct 20 ms 40536 KB Output is correct
19 Correct 20 ms 40536 KB Output is correct
20 Correct 21 ms 40536 KB Output is correct
21 Correct 21 ms 40536 KB Output is correct
22 Correct 21 ms 40536 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 40536 KB Output is correct
2 Correct 22 ms 40536 KB Output is correct
3 Correct 22 ms 40536 KB Output is correct
4 Correct 16 ms 40536 KB Output is correct
5 Correct 22 ms 40536 KB Output is correct
6 Correct 19 ms 40536 KB Output is correct
7 Correct 17 ms 40536 KB Output is correct
8 Correct 17 ms 40536 KB Output is correct
9 Correct 20 ms 40536 KB Output is correct
10 Correct 17 ms 40536 KB Output is correct
11 Correct 16 ms 40536 KB Output is correct
12 Correct 16 ms 40536 KB Output is correct
13 Correct 19 ms 40536 KB Output is correct
14 Correct 16 ms 40536 KB Output is correct
15 Correct 16 ms 40536 KB Output is correct
16 Correct 20 ms 40536 KB Output is correct
17 Correct 19 ms 40536 KB Output is correct
18 Correct 16 ms 40536 KB Output is correct
19 Correct 18 ms 40536 KB Output is correct
20 Correct 16 ms 40536 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 40536 KB Output is correct
2 Correct 179 ms 40536 KB Output is correct
3 Correct 184 ms 40536 KB Output is correct
4 Correct 195 ms 40536 KB Output is correct
5 Correct 189 ms 40536 KB Output is correct
6 Correct 273 ms 46508 KB Output is correct
7 Correct 264 ms 46508 KB Output is correct
8 Correct 246 ms 46508 KB Output is correct
9 Correct 185 ms 46508 KB Output is correct
10 Correct 173 ms 46508 KB Output is correct
11 Correct 164 ms 46508 KB Output is correct
12 Correct 175 ms 46508 KB Output is correct
13 Correct 164 ms 46508 KB Output is correct
14 Correct 152 ms 46508 KB Output is correct
15 Correct 162 ms 46508 KB Output is correct
16 Correct 93 ms 46508 KB Output is correct
17 Correct 104 ms 46508 KB Output is correct
18 Correct 116 ms 46508 KB Output is correct
19 Correct 109 ms 46508 KB Output is correct
20 Correct 110 ms 46508 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 46508 KB Output is correct
2 Correct 16 ms 46508 KB Output is correct
3 Incorrect 18 ms 46508 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 46508 KB Output is correct
2 Correct 246 ms 46508 KB Output is correct
3 Incorrect 187 ms 46508 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 17912 KB Output is correct
2 Correct 15 ms 18028 KB Output is correct
3 Correct 15 ms 18028 KB Output is correct
4 Correct 16 ms 18028 KB Output is correct
5 Correct 16 ms 18028 KB Output is correct
6 Correct 17 ms 18028 KB Output is correct
7 Correct 16 ms 18028 KB Output is correct
8 Correct 15 ms 18028 KB Output is correct
9 Correct 15 ms 18028 KB Output is correct
10 Correct 16 ms 18028 KB Output is correct
11 Incorrect 16 ms 18028 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 17912 KB Output is correct
2 Correct 15 ms 18028 KB Output is correct
3 Correct 15 ms 18028 KB Output is correct
4 Correct 16 ms 18028 KB Output is correct
5 Correct 16 ms 18028 KB Output is correct
6 Correct 17 ms 18028 KB Output is correct
7 Correct 16 ms 18028 KB Output is correct
8 Correct 15 ms 18028 KB Output is correct
9 Correct 15 ms 18028 KB Output is correct
10 Correct 16 ms 18028 KB Output is correct
11 Incorrect 16 ms 18028 KB Output isn't correct
12 Halted 0 ms 0 KB -