oj.uz

Submission #50695

# Submission time Handle Problem Language Result Execution time Memory
50695 2018-06-12T17:21:10 Z win11905 Duathlon (APIO18_duathlon) C++11
0 / 100
 595 ms 30988 KB 
#include <bits/stdc++.h>
#define vi vector<int>
#define long long long 
#define pii pair<int, int>
#define x first
#define y second
using namespace std;

const int N = 3e5+5;

long ans;
int n, m;
vector<vi> g, ccs;

int id[N], low[N], pre[N];
bitset<N> mark, art;
vi sz;

void find_component(int u, int p) {
	static int idx = 0;
	static stack<int> S;
	pre[u] = low[u] = ++idx;
	mark[u] = true;
	int cnt = 0;
	S.emplace(u);
	for(auto v : g[u]) if(!mark[v]) {
		++cnt;
		find_component(v, u);
		low[u] = min(low[u], low[v]);
		if(!p && cnt > 1 || p && low[v] >= pre[u]) art[u] = true;
		if(low[v] >= pre[u]) {
			ccs.emplace_back(vi());
			ccs.back().emplace_back(u);
			while(ccs.back().back() != v) ccs.back().emplace_back(S.top()), S.pop();
		}
	} else if(v != p) low[u] = min(low[u], pre[v]);
}

bitset<N> idart;

void gen_bctree() {
	g.clear();
	g.emplace_back(vi());
	sz.emplace_back(0);
	for(int i = 1; i <= n; ++i) if(art[i]) {
		idart[id[i] = g.size()] = true;
		g.emplace_back(vi());
		sz.emplace_back(1);
	}
	for(auto &cc : ccs) {
		g.emplace_back(vi());
		sz.emplace_back(cc.size());
		for(auto v : cc) {
			if(art[v]) g[id[v]].emplace_back(g.size()-1), g.back().emplace_back(id[v]);
			else id[v] = g.size()-1;
		}
	}
}

bitset<N> chk, have;
int dp[N];

int find_centroid(int u, int p, int sz, pii &ret) {
	int mx = 0; dp[u] = 1;
	for(auto v : g[u]) if(v != p and !chk[v]) {
		dp[u] += find_centroid(v, u, sz, ret);
		mx = max(mx, dp[v]);
	}
	mx = max(mx, sz - dp[u]);
	if(ret.x > mx) ret = pii(mx, u);
	return dp[u];
}

int rsize[N];

long get(int u) {
	return sz[u] - 2 * (idart[u] ? 0 : 1);
} 

void fill_son(int u, int p, long &ret, long val, bool st, int &wanna) {
	if(st) ans += rsize[u] * (ret + wanna * (val - idart[u]));
	else {
		ret += rsize[u] * (val - idart[u]);
		wanna += rsize[u];
	}
	for(auto v : g[u]) if(v != p and !chk[v]) fill_son(v, u, ret, val + get(v), st, wanna);
}

void centroid_decompos(int u, int sz) {
	pii ret(sz, -1);
	find_centroid(u, 0, sz, ret); 
	chk[u = ret.y] = true;
	long val = (get(u) - idart[u]) * rsize[u];
	if(!idart[u]) ans += (::sz[u] - 2ll) * (rsize[u]) * (rsize[u]-1ll) / 2;
	int wanna = rsize[u];
	for(auto v : g[u]) if(!chk[v]) {
		fill_son(v, u, val, get(v), true, wanna), 
		fill_son(v, u, val, get(v) + get(u), false, wanna);
	}
	for(auto v : g[u]) if(!chk[v]) centroid_decompos(v, dp[v] < dp[u] ? dp[v] : sz - dp[u]);
}

int main() {
	scanf("%d %d", &n, &m);
	g.resize(n+1);
	for(int i = 0, u, v; i < m; ++i) {
		scanf("%d %d", &u, &v);
		g[u].emplace_back(v), g[v].emplace_back(u);
	}
	find_component(1, 0);
	gen_bctree();
	for(int i = 1; i <= n; ++i) rsize[id[i]]++;
	centroid_decompos(1, g.size()-1);
	printf("%lld\n", ans << 1);
}

Compilation message

count_triplets.cpp: In function 'void find_component(int, int)':
count_triplets.cpp:30:9: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   if(!p && cnt > 1 || p && low[v] >= pre[u]) art[u] = true;
      ~~~^~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:104: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:107:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 2 ms 484 KB Output is correct
4 Correct 2 ms 484 KB Output is correct
5 Correct 2 ms 508 KB Output is correct
6 Correct 2 ms 508 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 636 KB Output is correct
9 Correct 2 ms 636 KB Output is correct
10 Correct 2 ms 636 KB Output is correct
11 Correct 2 ms 636 KB Output is correct
12 Correct 2 ms 636 KB Output is correct
13 Correct 2 ms 636 KB Output is correct
14 Correct 2 ms 636 KB Output is correct
15 Correct 2 ms 636 KB Output is correct
16 Correct 2 ms 636 KB Output is correct
17 Correct 2 ms 636 KB Output is correct
18 Correct 2 ms 636 KB Output is correct
19 Runtime error 2 ms 740 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 2 ms 484 KB Output is correct
4 Correct 2 ms 484 KB Output is correct
5 Correct 2 ms 508 KB Output is correct
6 Correct 2 ms 508 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 636 KB Output is correct
9 Correct 2 ms 636 KB Output is correct
10 Correct 2 ms 636 KB Output is correct
11 Correct 2 ms 636 KB Output is correct
12 Correct 2 ms 636 KB Output is correct
13 Correct 2 ms 636 KB Output is correct
14 Correct 2 ms 636 KB Output is correct
15 Correct 2 ms 636 KB Output is correct
16 Correct 2 ms 636 KB Output is correct
17 Correct 2 ms 636 KB Output is correct
18 Correct 2 ms 636 KB Output is correct
19 Runtime error 2 ms 740 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 19156 KB Output is correct
2 Correct 97 ms 19176 KB Output is correct
3 Incorrect 114 ms 19176 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19176 KB Output is correct
2 Correct 3 ms 19176 KB Output is correct
3 Correct 4 ms 19176 KB Output is correct
4 Correct 5 ms 19176 KB Output is correct
5 Correct 5 ms 19176 KB Output is correct
6 Correct 5 ms 19176 KB Output is correct
7 Correct 4 ms 19176 KB Output is correct
8 Correct 4 ms 19176 KB Output is correct
9 Correct 4 ms 19176 KB Output is correct
10 Incorrect 2 ms 19176 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 19176 KB Output is correct
2 Correct 269 ms 19176 KB Output is correct
3 Correct 283 ms 19176 KB Output is correct
4 Correct 278 ms 19176 KB Output is correct
5 Correct 266 ms 19176 KB Output is correct
6 Correct 559 ms 30988 KB Output is correct
7 Correct 490 ms 30988 KB Output is correct
8 Correct 541 ms 30988 KB Output is correct
9 Correct 567 ms 30988 KB Output is correct
10 Incorrect 162 ms 30988 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 30988 KB Output is correct
2 Correct 362 ms 30988 KB Output is correct
3 Correct 324 ms 30988 KB Output is correct
4 Correct 275 ms 30988 KB Output is correct
5 Correct 157 ms 30988 KB Output is correct
6 Correct 153 ms 30988 KB Output is correct
7 Correct 117 ms 30988 KB Output is correct
8 Correct 107 ms 30988 KB Output is correct
9 Correct 108 ms 30988 KB Output is correct
10 Correct 145 ms 30988 KB Output is correct
11 Correct 127 ms 30988 KB Output is correct
12 Correct 114 ms 30988 KB Output is correct
13 Correct 88 ms 30988 KB Output is correct
14 Correct 112 ms 30988 KB Output is correct
15 Correct 595 ms 30988 KB Output is correct
16 Correct 420 ms 30988 KB Output is correct
17 Correct 399 ms 30988 KB Output is correct
18 Correct 351 ms 30988 KB Output is correct
19 Incorrect 240 ms 30988 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 2 ms 484 KB Output is correct
4 Correct 2 ms 484 KB Output is correct
5 Correct 2 ms 508 KB Output is correct
6 Correct 2 ms 508 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 636 KB Output is correct
9 Correct 2 ms 636 KB Output is correct
10 Correct 2 ms 636 KB Output is correct
11 Correct 2 ms 636 KB Output is correct
12 Correct 2 ms 636 KB Output is correct
13 Correct 2 ms 636 KB Output is correct
14 Correct 2 ms 636 KB Output is correct
15 Correct 2 ms 636 KB Output is correct
16 Correct 2 ms 636 KB Output is correct
17 Correct 2 ms 636 KB Output is correct
18 Correct 2 ms 636 KB Output is correct
19 Runtime error 2 ms 740 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 2 ms 484 KB Output is correct
4 Correct 2 ms 484 KB Output is correct
5 Correct 2 ms 508 KB Output is correct
6 Correct 2 ms 508 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 636 KB Output is correct
9 Correct 2 ms 636 KB Output is correct
10 Correct 2 ms 636 KB Output is correct
11 Correct 2 ms 636 KB Output is correct
12 Correct 2 ms 636 KB Output is correct
13 Correct 2 ms 636 KB Output is correct
14 Correct 2 ms 636 KB Output is correct
15 Correct 2 ms 636 KB Output is correct
16 Correct 2 ms 636 KB Output is correct
17 Correct 2 ms 636 KB Output is correct
18 Correct 2 ms 636 KB Output is correct
19 Runtime error 2 ms 740 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -