oj.uz

Submission #50343

# Submission time Handle Problem Language Result Execution time Memory
50343 2018-06-10T12:06:24 Z zscoder Duathlon (APIO18_duathlon) C++17
31 / 100
 265 ms 46500 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 += max(0LL,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 19 ms 17780 KB Output is correct
2 Correct 15 ms 17892 KB Output is correct
3 Correct 20 ms 17968 KB Output is correct
4 Correct 19 ms 18044 KB Output is correct
5 Correct 17 ms 18080 KB Output is correct
6 Correct 18 ms 18128 KB Output is correct
7 Correct 20 ms 18156 KB Output is correct
8 Correct 17 ms 18156 KB Output is correct
9 Correct 20 ms 18156 KB Output is correct
10 Correct 18 ms 18156 KB Output is correct
11 Incorrect 17 ms 18156 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 17780 KB Output is correct
2 Correct 15 ms 17892 KB Output is correct
3 Correct 20 ms 17968 KB Output is correct
4 Correct 19 ms 18044 KB Output is correct
5 Correct 17 ms 18080 KB Output is correct
6 Correct 18 ms 18128 KB Output is correct
7 Correct 20 ms 18156 KB Output is correct
8 Correct 17 ms 18156 KB Output is correct
9 Correct 20 ms 18156 KB Output is correct
10 Correct 18 ms 18156 KB Output is correct
11 Incorrect 17 ms 18156 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 155 ms 40476 KB Output is correct
2 Correct 166 ms 40476 KB Output is correct
3 Correct 188 ms 40476 KB Output is correct
4 Correct 186 ms 40476 KB Output is correct
5 Correct 180 ms 40476 KB Output is correct
6 Correct 235 ms 40476 KB Output is correct
7 Correct 207 ms 40476 KB Output is correct
8 Correct 265 ms 40476 KB Output is correct
9 Correct 192 ms 40476 KB Output is correct
10 Correct 190 ms 40476 KB Output is correct
11 Correct 151 ms 40476 KB Output is correct
12 Correct 164 ms 40476 KB Output is correct
13 Correct 149 ms 40476 KB Output is correct
14 Correct 147 ms 40476 KB Output is correct
15 Correct 128 ms 40476 KB Output is correct
16 Correct 93 ms 40476 KB Output is correct
17 Correct 21 ms 40476 KB Output is correct
18 Correct 23 ms 40476 KB Output is correct
19 Correct 24 ms 40476 KB Output is correct
20 Correct 24 ms 40476 KB Output is correct
21 Correct 21 ms 40476 KB Output is correct
22 Correct 21 ms 40476 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 40476 KB Output is correct
2 Correct 183 ms 40476 KB Output is correct
3 Correct 207 ms 40476 KB Output is correct
4 Correct 179 ms 40476 KB Output is correct
5 Correct 180 ms 40476 KB Output is correct
6 Correct 225 ms 46500 KB Output is correct
7 Correct 203 ms 46500 KB Output is correct
8 Correct 248 ms 46500 KB Output is correct
9 Correct 207 ms 46500 KB Output is correct
10 Correct 224 ms 46500 KB Output is correct
11 Correct 221 ms 46500 KB Output is correct
12 Correct 185 ms 46500 KB Output is correct
13 Correct 191 ms 46500 KB Output is correct
14 Correct 179 ms 46500 KB Output is correct
15 Correct 140 ms 46500 KB Output is correct
16 Correct 95 ms 46500 KB Output is correct
17 Correct 112 ms 46500 KB Output is correct
18 Correct 115 ms 46500 KB Output is correct
19 Correct 109 ms 46500 KB Output is correct
20 Correct 117 ms 46500 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

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

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 17780 KB Output is correct
2 Correct 15 ms 17892 KB Output is correct
3 Correct 20 ms 17968 KB Output is correct
4 Correct 19 ms 18044 KB Output is correct
5 Correct 17 ms 18080 KB Output is correct
6 Correct 18 ms 18128 KB Output is correct
7 Correct 20 ms 18156 KB Output is correct
8 Correct 17 ms 18156 KB Output is correct
9 Correct 20 ms 18156 KB Output is correct
10 Correct 18 ms 18156 KB Output is correct
11 Incorrect 17 ms 18156 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 17780 KB Output is correct
2 Correct 15 ms 17892 KB Output is correct
3 Correct 20 ms 17968 KB Output is correct
4 Correct 19 ms 18044 KB Output is correct
5 Correct 17 ms 18080 KB Output is correct
6 Correct 18 ms 18128 KB Output is correct
7 Correct 20 ms 18156 KB Output is correct
8 Correct 17 ms 18156 KB Output is correct
9 Correct 20 ms 18156 KB Output is correct
10 Correct 18 ms 18156 KB Output is correct
11 Incorrect 17 ms 18156 KB Output isn't correct
12 Halted 0 ms 0 KB -