oj.uz

Submission #785211

# Submission time Handle Problem Language Result Execution time Memory
785211 2023-07-17T07:13:28 Z 박영우(#10025) Zagrade (COI17_zagrade) C++17
100 / 100
 746 ms 33564 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 303030
#define MAXS 22
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
int A[MAX];
vector<int> adj[MAX];
int num[MAX];
int vis[MAX];
void make_num(int x, int p = 0) {
	num[x] = 1;
	for (auto v : adj[x]) if (v != p) {
		if (vis[v]) continue;
		make_num(v, x);
		num[x] += num[v];
	}
}
int cnt[2][MAX];
int mx;
ll ans;
void dfs(int x, int c, int low, int sum, int p = 0) {
	sum += A[x] * (2 * c - 1);
	low = min(low, sum);
	if (low == sum) cnt[c][-low]++;
	mx = max(mx, -low);
	for (auto v : adj[x]) {
		if (vis[v]) continue;
		if (v == p) continue;
		dfs(v, c, low, sum, x);
	}
}
void make_tree(int x) {
	make_num(x);
	int c = x;
	int n = num[x];
	while (1) {
		bool changed = 0;
		for (auto v : adj[c]) {
			if (vis[v]) continue;
			if (num[c] < num[v]) continue;
			if (num[v] > n / 2) {
				changed = 1;
				c = v;
				break;
			}
		}
		if (!changed) break;
	}
	int i;
	mx = 0;
	for (auto v : adj[c]) {
		if (vis[v]) continue;
		mx = 0;
		dfs(v, 0, 0, 0, c);
		dfs(v, 1, 0, 0, c);
		if (A[c] > 0) {
			for (i = 0; i <= mx; i++) ans -= 1ll * cnt[0][i] * cnt[1][i + 1];
		}
		else {
			for (i = 0; i <= mx; i++) ans -= 1ll * cnt[0][i + 1] * cnt[1][i];
		}
		for (i = 0; i <= mx; i++) cnt[0][i] = cnt[1][i] = 0;
	}
	mx = 0;
	for (auto v : adj[c]) {
		if (vis[v]) continue;
		dfs(v, 0, 0, 0, c);
		dfs(v, 1, 0, 0, c);
	}
	if (A[c] > 0) {
		for (i = 0; i <= mx; i++) ans += 1ll * cnt[0][i] * cnt[1][i + 1];
		ans += cnt[1][1];
	}
	else {
		for (i = 0; i <= mx; i++) ans += 1ll * cnt[0][i + 1] * cnt[1][i];
		ans += cnt[0][1];
	}
	for (i = 0; i <= mx; i++) cnt[0][i] = cnt[1][i] = 0;
	vis[c] = 1;
	for (auto v : adj[c]) if (!vis[v]) make_tree(v);
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N;
	cin >> N;
	string s;
	cin >> s;
	int i, a, b;
	for (i = 1; i <= N; i++) A[i] = s[i - 1] == '(' ? 1 : -1;
	for (i = 1; i < N; i++) {
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	make_tree(1);
	cout << ans << ln;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7508 KB Output is correct
2 Correct 5 ms 7380 KB Output is correct
3 Correct 4 ms 7508 KB Output is correct
4 Correct 4 ms 7508 KB Output is correct
5 Correct 4 ms 7508 KB Output is correct
6 Correct 4 ms 7508 KB Output is correct
7 Correct 4 ms 7508 KB Output is correct
8 Correct 4 ms 7508 KB Output is correct
9 Correct 4 ms 7508 KB Output is correct
10 Correct 4 ms 7508 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 32300 KB Output is correct
2 Correct 328 ms 32888 KB Output is correct
3 Correct 311 ms 32288 KB Output is correct
4 Correct 353 ms 32628 KB Output is correct
5 Correct 366 ms 32400 KB Output is correct
6 Correct 328 ms 32596 KB Output is correct
7 Correct 332 ms 32296 KB Output is correct
8 Correct 319 ms 32556 KB Output is correct
9 Correct 331 ms 32368 KB Output is correct
10 Correct 298 ms 33560 KB Output is correct
11 Correct 334 ms 32288 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7508 KB Output is correct
2 Correct 5 ms 7380 KB Output is correct
3 Correct 4 ms 7508 KB Output is correct
4 Correct 4 ms 7508 KB Output is correct
5 Correct 4 ms 7508 KB Output is correct
6 Correct 4 ms 7508 KB Output is correct
7 Correct 4 ms 7508 KB Output is correct
8 Correct 4 ms 7508 KB Output is correct
9 Correct 4 ms 7508 KB Output is correct
10 Correct 4 ms 7508 KB Output is correct
11 Correct 319 ms 32300 KB Output is correct
12 Correct 328 ms 32888 KB Output is correct
13 Correct 311 ms 32288 KB Output is correct
14 Correct 353 ms 32628 KB Output is correct
15 Correct 366 ms 32400 KB Output is correct
16 Correct 328 ms 32596 KB Output is correct
17 Correct 332 ms 32296 KB Output is correct
18 Correct 319 ms 32556 KB Output is correct
19 Correct 331 ms 32368 KB Output is correct
20 Correct 298 ms 33560 KB Output is correct
21 Correct 334 ms 32288 KB Output is correct
22 Correct 730 ms 20972 KB Output is correct
23 Correct 732 ms 21088 KB Output is correct
24 Correct 693 ms 20972 KB Output is correct
25 Correct 746 ms 20968 KB Output is correct
26 Correct 444 ms 24604 KB Output is correct
27 Correct 417 ms 22856 KB Output is correct
28 Correct 447 ms 22456 KB Output is correct
29 Correct 299 ms 33564 KB Output is correct
30 Correct 320 ms 33544 KB Output is correct
31 Correct 73 ms 21808 KB Output is correct
32 Correct 301 ms 32380 KB Output is correct