oj.uz

Submission #50693

# Submission time Handle Problem Language Result Execution time Memory
50693 2018-06-12T17:16:18 Z win11905 Duathlon (APIO18_duathlon) C++11
0 / 100
 700 ms 31428 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 = 2e5+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 436 KB Output is correct
4 Correct 2 ms 448 KB Output is correct
5 Correct 3 ms 500 KB Output is correct
6 Correct 3 ms 532 KB Output is correct
7 Correct 2 ms 532 KB Output is correct
8 Correct 2 ms 532 KB Output is correct
9 Correct 2 ms 532 KB Output is correct
10 Correct 3 ms 660 KB Output is correct
11 Correct 2 ms 660 KB Output is correct
12 Correct 2 ms 660 KB Output is correct
13 Correct 2 ms 660 KB Output is correct
14 Correct 2 ms 660 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 760 KB Output is correct
18 Correct 2 ms 760 KB Output is correct
19 Runtime error 3 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 436 KB Output is correct
4 Correct 2 ms 448 KB Output is correct
5 Correct 3 ms 500 KB Output is correct
6 Correct 3 ms 532 KB Output is correct
7 Correct 2 ms 532 KB Output is correct
8 Correct 2 ms 532 KB Output is correct
9 Correct 2 ms 532 KB Output is correct
10 Correct 3 ms 660 KB Output is correct
11 Correct 2 ms 660 KB Output is correct
12 Correct 2 ms 660 KB Output is correct
13 Correct 2 ms 660 KB Output is correct
14 Correct 2 ms 660 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 760 KB Output is correct
18 Correct 2 ms 760 KB Output is correct
19 Runtime error 3 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 108 ms 19264 KB Output is correct
2 Correct 99 ms 19264 KB Output is correct
3 Incorrect 100 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 3 ms 19264 KB Output is correct
2 Correct 3 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 5 ms 19264 KB Output is correct
6 Correct 4 ms 19264 KB Output is correct
7 Correct 5 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 2 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 283 ms 19264 KB Output is correct
2 Correct 299 ms 19264 KB Output is correct
3 Correct 293 ms 19264 KB Output is correct
4 Correct 312 ms 19264 KB Output is correct
5 Correct 353 ms 19264 KB Output is correct
6 Correct 700 ms 31428 KB Output is correct
7 Correct 540 ms 31428 KB Output is correct
8 Correct 511 ms 31428 KB Output is correct
9 Correct 631 ms 31428 KB Output is correct
10 Incorrect 217 ms 31428 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 31428 KB Output is correct
2 Correct 4 ms 31428 KB Output is correct
3 Correct 3 ms 31428 KB Output is correct
4 Correct 3 ms 31428 KB Output is correct
5 Correct 3 ms 31428 KB Output is correct
6 Correct 3 ms 31428 KB Output is correct
7 Correct 3 ms 31428 KB Output is correct
8 Correct 2 ms 31428 KB Output is correct
9 Correct 3 ms 31428 KB Output is correct
10 Correct 3 ms 31428 KB Output is correct
11 Correct 3 ms 31428 KB Output is correct
12 Correct 4 ms 31428 KB Output is correct
13 Correct 4 ms 31428 KB Output is correct
14 Correct 5 ms 31428 KB Output is correct
15 Correct 4 ms 31428 KB Output is correct
16 Incorrect 3 ms 31428 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 31428 KB Output is correct
2 Correct 345 ms 31428 KB Output is correct
3 Correct 267 ms 31428 KB Output is correct
4 Correct 275 ms 31428 KB Output is correct
5 Correct 213 ms 31428 KB Output is correct
6 Correct 132 ms 31428 KB Output is correct
7 Correct 116 ms 31428 KB Output is correct
8 Correct 133 ms 31428 KB Output is correct
9 Correct 187 ms 31428 KB Output is correct
10 Correct 89 ms 31428 KB Output is correct
11 Correct 114 ms 31428 KB Output is correct
12 Correct 103 ms 31428 KB Output is correct
13 Correct 121 ms 31428 KB Output is correct
14 Correct 98 ms 31428 KB Output is correct
15 Correct 528 ms 31428 KB Output is correct
16 Correct 428 ms 31428 KB Output is correct
17 Correct 349 ms 31428 KB Output is correct
18 Correct 339 ms 31428 KB Output is correct
19 Incorrect 198 ms 31428 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 2 ms 448 KB Output is correct
5 Correct 3 ms 500 KB Output is correct
6 Correct 3 ms 532 KB Output is correct
7 Correct 2 ms 532 KB Output is correct
8 Correct 2 ms 532 KB Output is correct
9 Correct 2 ms 532 KB Output is correct
10 Correct 3 ms 660 KB Output is correct
11 Correct 2 ms 660 KB Output is correct
12 Correct 2 ms 660 KB Output is correct
13 Correct 2 ms 660 KB Output is correct
14 Correct 2 ms 660 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 760 KB Output is correct
18 Correct 2 ms 760 KB Output is correct
19 Runtime error 3 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 436 KB Output is correct
4 Correct 2 ms 448 KB Output is correct
5 Correct 3 ms 500 KB Output is correct
6 Correct 3 ms 532 KB Output is correct
7 Correct 2 ms 532 KB Output is correct
8 Correct 2 ms 532 KB Output is correct
9 Correct 2 ms 532 KB Output is correct
10 Correct 3 ms 660 KB Output is correct
11 Correct 2 ms 660 KB Output is correct
12 Correct 2 ms 660 KB Output is correct
13 Correct 2 ms 660 KB Output is correct
14 Correct 2 ms 660 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 760 KB Output is correct
18 Correct 2 ms 760 KB Output is correct
19 Runtime error 3 ms 764 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -