oj.uz

Submission #50694

# Submission time Handle Problem Language Result Execution time Memory
50694 2018-06-12T17:18:23 Z win11905 Duathlon (APIO18_duathlon) C++11
0 / 100
 627 ms 31608 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, bool &have, int &wanna) {
	if(st) { if(have) ans += rsize[u] * (ret + wanna * (val - idart[u]));
	} else {
		if(rsize[u]) have = true;
		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, have, 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;
	bool have = rsize[u];
	int wanna = rsize[u];
	for(auto v : g[u]) if(!chk[v]) {
		fill_son(v, u, val, get(v), true, have, wanna), 
		fill_son(v, u, val, get(v) + get(u), false, have, 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:106: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:109: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 376 KB Output is correct
3 Correct 2 ms 416 KB Output is correct
4 Correct 2 ms 436 KB Output is correct
5 Correct 2 ms 436 KB Output is correct
6 Correct 2 ms 496 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 2 ms 568 KB Output is correct
10 Correct 2 ms 568 KB Output is correct
11 Correct 2 ms 588 KB Output is correct
12 Correct 2 ms 588 KB Output is correct
13 Correct 2 ms 588 KB Output is correct
14 Correct 2 ms 588 KB Output is correct
15 Correct 2 ms 588 KB Output is correct
16 Correct 2 ms 588 KB Output is correct
17 Correct 2 ms 588 KB Output is correct
18 Correct 2 ms 676 KB Output is correct
19 Runtime error 2 ms 764 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 376 KB Output is correct
3 Correct 2 ms 416 KB Output is correct
4 Correct 2 ms 436 KB Output is correct
5 Correct 2 ms 436 KB Output is correct
6 Correct 2 ms 496 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 2 ms 568 KB Output is correct
10 Correct 2 ms 568 KB Output is correct
11 Correct 2 ms 588 KB Output is correct
12 Correct 2 ms 588 KB Output is correct
13 Correct 2 ms 588 KB Output is correct
14 Correct 2 ms 588 KB Output is correct
15 Correct 2 ms 588 KB Output is correct
16 Correct 2 ms 588 KB Output is correct
17 Correct 2 ms 588 KB Output is correct
18 Correct 2 ms 676 KB Output is correct
19 Runtime error 2 ms 764 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 106 ms 19276 KB Output is correct
2 Correct 110 ms 19276 KB Output is correct
3 Incorrect 84 ms 19276 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 19276 KB Output is correct
2 Correct 274 ms 19276 KB Output is correct
3 Correct 319 ms 19276 KB Output is correct
4 Correct 295 ms 19276 KB Output is correct
5 Correct 283 ms 19276 KB Output is correct
6 Correct 610 ms 31608 KB Output is correct
7 Correct 569 ms 31608 KB Output is correct
8 Correct 536 ms 31608 KB Output is correct
9 Correct 627 ms 31608 KB Output is correct
10 Incorrect 191 ms 31608 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 31608 KB Output is correct
2 Correct 5 ms 31608 KB Output is correct
3 Correct 3 ms 31608 KB Output is correct
4 Correct 3 ms 31608 KB Output is correct
5 Correct 3 ms 31608 KB Output is correct
6 Correct 3 ms 31608 KB Output is correct
7 Correct 4 ms 31608 KB Output is correct
8 Correct 3 ms 31608 KB Output is correct
9 Correct 3 ms 31608 KB Output is correct
10 Correct 2 ms 31608 KB Output is correct
11 Correct 3 ms 31608 KB Output is correct
12 Correct 4 ms 31608 KB Output is correct
13 Correct 5 ms 31608 KB Output is correct
14 Correct 4 ms 31608 KB Output is correct
15 Correct 5 ms 31608 KB Output is correct
16 Incorrect 2 ms 31608 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 363 ms 31608 KB Output is correct
2 Correct 319 ms 31608 KB Output is correct
3 Correct 279 ms 31608 KB Output is correct
4 Correct 232 ms 31608 KB Output is correct
5 Correct 177 ms 31608 KB Output is correct
6 Correct 152 ms 31608 KB Output is correct
7 Correct 144 ms 31608 KB Output is correct
8 Correct 145 ms 31608 KB Output is correct
9 Correct 127 ms 31608 KB Output is correct
10 Correct 96 ms 31608 KB Output is correct
11 Correct 82 ms 31608 KB Output is correct
12 Correct 79 ms 31608 KB Output is correct
13 Correct 116 ms 31608 KB Output is correct
14 Correct 118 ms 31608 KB Output is correct
15 Correct 517 ms 31608 KB Output is correct
16 Correct 480 ms 31608 KB Output is correct
17 Correct 461 ms 31608 KB Output is correct
18 Correct 351 ms 31608 KB Output is correct
19 Incorrect 279 ms 31608 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 376 KB Output is correct
3 Correct 2 ms 416 KB Output is correct
4 Correct 2 ms 436 KB Output is correct
5 Correct 2 ms 436 KB Output is correct
6 Correct 2 ms 496 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 2 ms 568 KB Output is correct
10 Correct 2 ms 568 KB Output is correct
11 Correct 2 ms 588 KB Output is correct
12 Correct 2 ms 588 KB Output is correct
13 Correct 2 ms 588 KB Output is correct
14 Correct 2 ms 588 KB Output is correct
15 Correct 2 ms 588 KB Output is correct
16 Correct 2 ms 588 KB Output is correct
17 Correct 2 ms 588 KB Output is correct
18 Correct 2 ms 676 KB Output is correct
19 Runtime error 2 ms 764 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 376 KB Output is correct
3 Correct 2 ms 416 KB Output is correct
4 Correct 2 ms 436 KB Output is correct
5 Correct 2 ms 436 KB Output is correct
6 Correct 2 ms 496 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 2 ms 568 KB Output is correct
10 Correct 2 ms 568 KB Output is correct
11 Correct 2 ms 588 KB Output is correct
12 Correct 2 ms 588 KB Output is correct
13 Correct 2 ms 588 KB Output is correct
14 Correct 2 ms 588 KB Output is correct
15 Correct 2 ms 588 KB Output is correct
16 Correct 2 ms 588 KB Output is correct
17 Correct 2 ms 588 KB Output is correct
18 Correct 2 ms 676 KB Output is correct
19 Runtime error 2 ms 764 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -