oj.uz

Submission #57773

# Submission time Handle Problem Language Result Execution time Memory
57773 2018-07-16T04:13:53 Z Crown Duathlon (APIO18_duathlon) C++14
31 / 100
 390 ms 54348 KB 
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 1e5+5;
const int maxm = 2e5+5;

int n, m; 

vector< ii > adj[maxn];
int U[maxm], V[maxm];
int num[maxn], low[maxn];
int now = 1;
bool instack[maxm];
stack<int> s;
int compno;
int col[maxm];

vector<int> tree[2*(maxn+maxm)];
int cnt[2*(maxn+maxm)];

void tarjan(int u, int p)
{
	num[u] = low[u] = now;
	now++;
	for(auto earn : adj[u])
	{
		int v = earn.X, id = earn.Y;
		if(!num[v])
		{
			if(!instack[id])
			{
				s.push(id);
				instack[id] = true;
			}
			tarjan(v, u);
			low[u] = min(low[u], low[v]);
			if(low[v]>= num[u])
			{
				// u is an articulation point
				compno++;
				while(!s.empty())
				{
					int x = s.top(); s.pop();
					col[x] = compno;
					if(x == id) break;
				}
			}
		}
		else if(v != p)
		{
			if(!instack[id])
			{
				s.push(id);
				instack[id] = true;
			}
			low[u] = min(low[u], num[v]);
		}
	}
}

ll res;

void dfs(int u, int p)
{
	cnt[u] = u>compno;
	for(auto v : tree[u])
	{
		if(v == p) continue;
		dfs(v, u);
		cnt[u] += cnt[v];
	}
}

void solve(int u, int p, int par_cnt)
{
	//printf("%d (%d)\n", u, par_cnt);
	if(u> compno)
	{
		ll tot = 0;
		ll sq = 0;
		for(auto v : tree[u])
		{
			if(v == p) continue;
			tot += cnt[v];
			sq += 1LL*cnt[v]*cnt[v];
		}
		res += tot*tot-sq;
	}
	else
	{
		ll tot = 0;
		ll sq = 0;
		vector<int> ne;
		for(auto v : tree[u])
		{
			if(v == p) continue;
			if(!cnt[v]) continue;
			ne.pb(cnt[v]);
			tot += cnt[v];
			sq += 1LL*cnt[v]*cnt[v];
		}
		//printf("tot is %lld sq is %lld\n", tot, sq);
		if(par_cnt)
		{
			tot += par_cnt; sq += 1LL*par_cnt*par_cnt;
		}
		for(auto x : ne)
		{
			res += (tot-1)*(tot-1) - (sq - (2LL*x - 1) );
		}
	}
	//printf("res is now %lld\n", res);
	int tot = u> compno;
	for(auto v : tree[u])
	{
		if(v == p) continue;
		tot += cnt[v];
	}
	for(auto v : tree[u])
	{
		if(v == p) continue;
		solve(v, u, par_cnt+tot-cnt[v]);
	}
}

int main()
{
	scanf("%d %d", &n, &m);
	for(int i = 1; i<= m; i++)
	{
		int u, v; scanf("%d %d", &u, &v);
		U[i] = u; V[i] = v;
		adj[u].pb(ii(v, i));
		adj[v].pb(ii(u, i));
	}
	for(int i = 1; i<= n; i++)
	{
		if(num[i]) continue;
		tarjan(i, 0);
		if(!s.empty())
		{
			compno++;
			while(!s.empty())
			{
				int x = s.top(); s.pop();
				col[x] = compno;
			}
		}
	}
	for(int i = 1; i<= m; i++)
	{
		int x = col[i];
		int u = U[i], v = V[i];
		tree[compno+u].pb(x);
		tree[x].pb(compno+u);
		tree[compno+v].pb(x);
		tree[x].pb(compno+v);
	}
	for(int i = 1; i<= compno+n; i++)
	{
		sort(tree[i].begin(), tree[i].end());
		tree[i].resize(unique(tree[i].begin(), tree[i].end())-tree[i].begin());
	}
	for(int i = 1; i<= compno+n; i++)
	{
		if(cnt[i]) continue;
		dfs(i, 0);
		solve(i, 0, 0);
	}
	printf("%lld\n", res);
}

Compilation message

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:133:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
count_triplets.cpp:136:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u, v; scanf("%d %d", &u, &v);
             ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 16760 KB Output is correct
2 Correct 19 ms 17004 KB Output is correct
3 Correct 19 ms 17004 KB Output is correct
4 Correct 19 ms 17004 KB Output is correct
5 Correct 21 ms 17004 KB Output is correct
6 Correct 20 ms 17012 KB Output is correct
7 Incorrect 19 ms 17012 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 16760 KB Output is correct
2 Correct 19 ms 17004 KB Output is correct
3 Correct 19 ms 17004 KB Output is correct
4 Correct 19 ms 17004 KB Output is correct
5 Correct 21 ms 17004 KB Output is correct
6 Correct 20 ms 17012 KB Output is correct
7 Incorrect 19 ms 17012 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 36768 KB Output is correct
2 Correct 229 ms 36924 KB Output is correct
3 Correct 180 ms 40604 KB Output is correct
4 Correct 192 ms 40604 KB Output is correct
5 Correct 252 ms 40604 KB Output is correct
6 Correct 228 ms 42080 KB Output is correct
7 Correct 352 ms 42080 KB Output is correct
8 Correct 315 ms 42080 KB Output is correct
9 Correct 270 ms 42080 KB Output is correct
10 Correct 181 ms 42080 KB Output is correct
11 Correct 205 ms 42080 KB Output is correct
12 Correct 170 ms 42080 KB Output is correct
13 Correct 233 ms 42080 KB Output is correct
14 Correct 236 ms 42080 KB Output is correct
15 Correct 121 ms 42080 KB Output is correct
16 Correct 162 ms 42080 KB Output is correct
17 Correct 20 ms 42080 KB Output is correct
18 Correct 23 ms 42080 KB Output is correct
19 Correct 22 ms 42080 KB Output is correct
20 Correct 22 ms 42080 KB Output is correct
21 Correct 21 ms 42080 KB Output is correct
22 Correct 23 ms 42080 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 42080 KB Output is correct
2 Correct 302 ms 42080 KB Output is correct
3 Correct 349 ms 42080 KB Output is correct
4 Correct 324 ms 42080 KB Output is correct
5 Correct 303 ms 42080 KB Output is correct
6 Correct 386 ms 54348 KB Output is correct
7 Correct 390 ms 54348 KB Output is correct
8 Correct 348 ms 54348 KB Output is correct
9 Correct 274 ms 54348 KB Output is correct
10 Correct 267 ms 54348 KB Output is correct
11 Correct 280 ms 54348 KB Output is correct
12 Correct 342 ms 54348 KB Output is correct
13 Correct 312 ms 54348 KB Output is correct
14 Correct 253 ms 54348 KB Output is correct
15 Correct 218 ms 54348 KB Output is correct
16 Correct 159 ms 54348 KB Output is correct
17 Correct 164 ms 54348 KB Output is correct
18 Correct 133 ms 54348 KB Output is correct
19 Correct 178 ms 54348 KB Output is correct
20 Correct 137 ms 54348 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 54348 KB Output is correct
2 Correct 304 ms 54348 KB Output is correct
3 Incorrect 322 ms 54348 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 16760 KB Output is correct
2 Correct 19 ms 17004 KB Output is correct
3 Correct 19 ms 17004 KB Output is correct
4 Correct 19 ms 17004 KB Output is correct
5 Correct 21 ms 17004 KB Output is correct
6 Correct 20 ms 17012 KB Output is correct
7 Incorrect 19 ms 17012 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 16760 KB Output is correct
2 Correct 19 ms 17004 KB Output is correct
3 Correct 19 ms 17004 KB Output is correct
4 Correct 19 ms 17004 KB Output is correct
5 Correct 21 ms 17004 KB Output is correct
6 Correct 20 ms 17012 KB Output is correct
7 Incorrect 19 ms 17012 KB Output isn't correct
8 Halted 0 ms 0 KB -