oj.uz

Submission #50697

# Submission time Handle Problem Language Result Execution time Memory
50697 2018-06-12T17:23:00 Z win11905 Duathlon (APIO18_duathlon) C++11
0 / 100
 491 ms 30668 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(::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 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 2 ms 488 KB Output is correct
5 Correct 2 ms 488 KB Output is correct
6 Correct 2 ms 572 KB Output is correct
7 Correct 2 ms 572 KB Output is correct
8 Correct 2 ms 572 KB Output is correct
9 Correct 2 ms 572 KB Output is correct
10 Correct 2 ms 688 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 692 KB Output is correct
14 Correct 2 ms 692 KB Output is correct
15 Correct 2 ms 692 KB Output is correct
16 Correct 2 ms 692 KB Output is correct
17 Correct 2 ms 692 KB Output is correct
18 Correct 2 ms 692 KB Output is correct
19 Runtime error 3 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 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 2 ms 488 KB Output is correct
5 Correct 2 ms 488 KB Output is correct
6 Correct 2 ms 572 KB Output is correct
7 Correct 2 ms 572 KB Output is correct
8 Correct 2 ms 572 KB Output is correct
9 Correct 2 ms 572 KB Output is correct
10 Correct 2 ms 688 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 692 KB Output is correct
14 Correct 2 ms 692 KB Output is correct
15 Correct 2 ms 692 KB Output is correct
16 Correct 2 ms 692 KB Output is correct
17 Correct 2 ms 692 KB Output is correct
18 Correct 2 ms 692 KB Output is correct
19 Runtime error 3 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 103 ms 19296 KB Output is correct
2 Correct 94 ms 19296 KB Output is correct
3 Incorrect 80 ms 19296 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 19296 KB Output is correct
2 Correct 3 ms 19296 KB Output is correct
3 Correct 3 ms 19296 KB Output is correct
4 Correct 4 ms 19296 KB Output is correct
5 Correct 5 ms 19296 KB Output is correct
6 Correct 5 ms 19296 KB Output is correct
7 Correct 4 ms 19296 KB Output is correct
8 Correct 4 ms 19296 KB Output is correct
9 Correct 3 ms 19296 KB Output is correct
10 Incorrect 2 ms 19296 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 271 ms 19296 KB Output is correct
2 Correct 269 ms 19296 KB Output is correct
3 Correct 280 ms 19296 KB Output is correct
4 Correct 291 ms 19296 KB Output is correct
5 Correct 262 ms 19296 KB Output is correct
6 Correct 491 ms 30668 KB Output is correct
7 Correct 448 ms 30668 KB Output is correct
8 Correct 446 ms 30668 KB Output is correct
9 Correct 444 ms 30668 KB Output is correct
10 Incorrect 163 ms 30668 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 30668 KB Output is correct
2 Correct 3 ms 30668 KB Output is correct
3 Correct 3 ms 30668 KB Output is correct
4 Correct 3 ms 30668 KB Output is correct
5 Correct 3 ms 30668 KB Output is correct
6 Correct 3 ms 30668 KB Output is correct
7 Correct 3 ms 30668 KB Output is correct
8 Correct 2 ms 30668 KB Output is correct
9 Correct 2 ms 30668 KB Output is correct
10 Correct 2 ms 30668 KB Output is correct
11 Correct 3 ms 30668 KB Output is correct
12 Correct 3 ms 30668 KB Output is correct
13 Correct 3 ms 30668 KB Output is correct
14 Correct 3 ms 30668 KB Output is correct
15 Correct 3 ms 30668 KB Output is correct
16 Incorrect 2 ms 30668 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 30668 KB Output is correct
2 Correct 296 ms 30668 KB Output is correct
3 Correct 279 ms 30668 KB Output is correct
4 Correct 213 ms 30668 KB Output is correct
5 Correct 159 ms 30668 KB Output is correct
6 Correct 130 ms 30668 KB Output is correct
7 Correct 122 ms 30668 KB Output is correct
8 Correct 185 ms 30668 KB Output is correct
9 Correct 102 ms 30668 KB Output is correct
10 Correct 99 ms 30668 KB Output is correct
11 Correct 94 ms 30668 KB Output is correct
12 Correct 90 ms 30668 KB Output is correct
13 Correct 132 ms 30668 KB Output is correct
14 Correct 114 ms 30668 KB Output is correct
15 Correct 471 ms 30668 KB Output is correct
16 Correct 430 ms 30668 KB Output is correct
17 Correct 374 ms 30668 KB Output is correct
18 Correct 362 ms 30668 KB Output is correct
19 Incorrect 240 ms 30668 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 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 2 ms 488 KB Output is correct
5 Correct 2 ms 488 KB Output is correct
6 Correct 2 ms 572 KB Output is correct
7 Correct 2 ms 572 KB Output is correct
8 Correct 2 ms 572 KB Output is correct
9 Correct 2 ms 572 KB Output is correct
10 Correct 2 ms 688 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 692 KB Output is correct
14 Correct 2 ms 692 KB Output is correct
15 Correct 2 ms 692 KB Output is correct
16 Correct 2 ms 692 KB Output is correct
17 Correct 2 ms 692 KB Output is correct
18 Correct 2 ms 692 KB Output is correct
19 Runtime error 3 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 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 2 ms 488 KB Output is correct
5 Correct 2 ms 488 KB Output is correct
6 Correct 2 ms 572 KB Output is correct
7 Correct 2 ms 572 KB Output is correct
8 Correct 2 ms 572 KB Output is correct
9 Correct 2 ms 572 KB Output is correct
10 Correct 2 ms 688 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 692 KB Output is correct
14 Correct 2 ms 692 KB Output is correct
15 Correct 2 ms 692 KB Output is correct
16 Correct 2 ms 692 KB Output is correct
17 Correct 2 ms 692 KB Output is correct
18 Correct 2 ms 692 KB Output is correct
19 Runtime error 3 ms 740 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -