oj.uz

Submission #50696

# Submission time Handle Problem Language Result Execution time Memory
50696 2018-06-12T17:21:54 Z win11905 Duathlon (APIO18_duathlon) C++11
0 / 100
 594 ms 30820 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] and ::sz[u] > 2) 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 376 KB Output is correct
3 Correct 2 ms 436 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 2 ms 640 KB Output is correct
9 Correct 2 ms 692 KB Output is correct
10 Correct 2 ms 692 KB Output is correct
11 Correct 2 ms 692 KB Output is correct
12 Correct 2 ms 692 KB Output is correct
13 Correct 2 ms 748 KB Output is correct
14 Correct 2 ms 748 KB Output is correct
15 Correct 2 ms 748 KB Output is correct
16 Correct 2 ms 748 KB Output is correct
17 Correct 2 ms 748 KB Output is correct
18 Correct 2 ms 748 KB Output is correct
19 Runtime error 2 ms 748 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 436 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 2 ms 640 KB Output is correct
9 Correct 2 ms 692 KB Output is correct
10 Correct 2 ms 692 KB Output is correct
11 Correct 2 ms 692 KB Output is correct
12 Correct 2 ms 692 KB Output is correct
13 Correct 2 ms 748 KB Output is correct
14 Correct 2 ms 748 KB Output is correct
15 Correct 2 ms 748 KB Output is correct
16 Correct 2 ms 748 KB Output is correct
17 Correct 2 ms 748 KB Output is correct
18 Correct 2 ms 748 KB Output is correct
19 Runtime error 2 ms 748 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 100 ms 19264 KB Output is correct
2 Correct 108 ms 19264 KB Output is correct
3 Incorrect 82 ms 19264 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 19264 KB Output is correct
2 Correct 4 ms 19264 KB Output is correct
3 Correct 3 ms 19264 KB Output is correct
4 Correct 4 ms 19264 KB Output is correct
5 Correct 4 ms 19264 KB Output is correct
6 Correct 4 ms 19264 KB Output is correct
7 Correct 4 ms 19264 KB Output is correct
8 Correct 4 ms 19264 KB Output is correct
9 Correct 4 ms 19264 KB Output is correct
10 Incorrect 3 ms 19264 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 19264 KB Output is correct
2 Correct 334 ms 19264 KB Output is correct
3 Correct 302 ms 19264 KB Output is correct
4 Correct 324 ms 19264 KB Output is correct
5 Correct 289 ms 19264 KB Output is correct
6 Correct 594 ms 30820 KB Output is correct
7 Correct 562 ms 30820 KB Output is correct
8 Correct 533 ms 30820 KB Output is correct
9 Correct 526 ms 30820 KB Output is correct
10 Incorrect 184 ms 30820 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 30820 KB Output is correct
2 Correct 3 ms 30820 KB Output is correct
3 Correct 3 ms 30820 KB Output is correct
4 Correct 3 ms 30820 KB Output is correct
5 Correct 3 ms 30820 KB Output is correct
6 Correct 5 ms 30820 KB Output is correct
7 Correct 3 ms 30820 KB Output is correct
8 Correct 3 ms 30820 KB Output is correct
9 Correct 4 ms 30820 KB Output is correct
10 Correct 2 ms 30820 KB Output is correct
11 Correct 2 ms 30820 KB Output is correct
12 Correct 4 ms 30820 KB Output is correct
13 Correct 4 ms 30820 KB Output is correct
14 Correct 5 ms 30820 KB Output is correct
15 Correct 4 ms 30820 KB Output is correct
16 Incorrect 3 ms 30820 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 30820 KB Output is correct
2 Correct 366 ms 30820 KB Output is correct
3 Correct 289 ms 30820 KB Output is correct
4 Correct 216 ms 30820 KB Output is correct
5 Correct 179 ms 30820 KB Output is correct
6 Correct 139 ms 30820 KB Output is correct
7 Correct 128 ms 30820 KB Output is correct
8 Correct 132 ms 30820 KB Output is correct
9 Correct 109 ms 30820 KB Output is correct
10 Correct 102 ms 30820 KB Output is correct
11 Correct 96 ms 30820 KB Output is correct
12 Correct 94 ms 30820 KB Output is correct
13 Correct 108 ms 30820 KB Output is correct
14 Correct 99 ms 30820 KB Output is correct
15 Correct 516 ms 30820 KB Output is correct
16 Correct 441 ms 30820 KB Output is correct
17 Correct 466 ms 30820 KB Output is correct
18 Correct 360 ms 30820 KB Output is correct
19 Incorrect 214 ms 30820 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 436 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 2 ms 640 KB Output is correct
9 Correct 2 ms 692 KB Output is correct
10 Correct 2 ms 692 KB Output is correct
11 Correct 2 ms 692 KB Output is correct
12 Correct 2 ms 692 KB Output is correct
13 Correct 2 ms 748 KB Output is correct
14 Correct 2 ms 748 KB Output is correct
15 Correct 2 ms 748 KB Output is correct
16 Correct 2 ms 748 KB Output is correct
17 Correct 2 ms 748 KB Output is correct
18 Correct 2 ms 748 KB Output is correct
19 Runtime error 2 ms 748 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 436 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 2 ms 640 KB Output is correct
9 Correct 2 ms 692 KB Output is correct
10 Correct 2 ms 692 KB Output is correct
11 Correct 2 ms 692 KB Output is correct
12 Correct 2 ms 692 KB Output is correct
13 Correct 2 ms 748 KB Output is correct
14 Correct 2 ms 748 KB Output is correct
15 Correct 2 ms 748 KB Output is correct
16 Correct 2 ms 748 KB Output is correct
17 Correct 2 ms 748 KB Output is correct
18 Correct 2 ms 748 KB Output is correct
19 Runtime error 2 ms 748 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -