oj.uz

Submission #209731

# Submission time Handle Problem Language Result Execution time Memory
209731 2020-03-15T12:48:46 Z ruler Zagrade (COI17_zagrade) C++14
40 / 100
 775 ms 49752 KB 
// IOI 2021
#include <bits/stdc++.h>
using namespace std;
 
#define endl '\n'
#define ends ' '
#define die(x) return cout << x << endl, 0
#define all(v) v.begin(), v.end()
#define sz(x) (int)(x.size())
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cerr << ends << H; debug_out(T...); }
#define debug(...) cerr << "{" << #__VA_ARGS__ << "}:", debug_out(__VA_ARGS__)
typedef long long ll;
typedef pair<int, int> pii;
const ll INF = 1e9;
const ll MOD = 1e9 + 7;
 
////////////////////////////////////////////////////////////////////

const int N = 3e5 + 2;

int n, A[N], SZ[N];
bool M[N];
vector<int> G[N];
ll ans;

void DFSZ(int v, int p = 0) {
	SZ[v] = 1;
	for (int u : G[v])
		if (u != p && !M[u])
			DFSZ(u, v), SZ[v] += SZ[u];
}
int GetCentroid(int v, int p = 0, int m = 0) {
	if (!p) DFSZ(v), m = SZ[v];
	for (int u : G[v])
		if (u != p && !M[u] && SZ[u] * 2 > m)
			return GetCentroid(u, v, m);
	return v;
}
void DFS(int v, vector<int> &c, bool r, int x, int p = 0, int s = 0, int m = 0) {
	s += A[v], m += A[v];
	if (r) s *= -1, m *= -1;
	m = min(m, 0);
	if (m >= 0 && s >= 0) c[s] += x;
	if (r) s *= -1, m *= -1;
	for (int u : G[v])
		if (u != p && !M[u])
			DFS(u, c, r, x, v, s, m);
}
void Solve(int v) {
	vector<int> up(SZ[v] + 1, 0), dw(SZ[v] + 1, 0);
	DFS(v, up, 1, + 1), DFS(v, dw, 0, + 1);	
	for (int u : G[v]) if (!M[u]) {
		DFS(u, up, 1, - 1, v, A[v]), DFS(u, dw, 0, - 1, v, A[v]);	
		vector<int> cup(SZ[u] + 1, 0), cdw(SZ[u] + 1, 0);
		DFS(u, cup, 1, + 1, v), DFS(u, cdw, 0, + 1, v);
		for (int i = 0; i <= SZ[u]; i++) ans += 1LL * cup[i] * dw[i] + 1LL * cdw[i] * up[i];
	}
}
void Decompose(int v) {
	v = GetCentroid(v), M[v] = 1, Solve(v);
	for (int u : G[v]) if (!M[u]) Decompose(u);
}

int main() {

	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	mt19937 Rnd(time(0));

	cin >> n;
	for (int i = 0; i < n; i++) {
		char c; cin >> c;
		if (c == '(') A[i + 1] = + 1;
		else A[i + 1] = - 1;
	}
	for (int i = 1; i < n; i++) {
		int v, u; cin >> v >> u;
		G[v].push_back(u);
		G[u].push_back(v);
	}
	Decompose(1);
	cout << ans << endl;

	return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 678 ms 40244 KB Output is correct
2 Correct 729 ms 43768 KB Output is correct
3 Correct 672 ms 43768 KB Output is correct
4 Correct 715 ms 43768 KB Output is correct
5 Correct 701 ms 43768 KB Output is correct
6 Correct 772 ms 43744 KB Output is correct
7 Correct 734 ms 44384 KB Output is correct
8 Correct 775 ms 44412 KB Output is correct
9 Correct 744 ms 44408 KB Output is correct
10 Correct 730 ms 44408 KB Output is correct
11 Correct 734 ms 44536 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7416 KB Output is correct
2 Correct 10 ms 7416 KB Output is correct
3 Correct 10 ms 7416 KB Output is correct
4 Correct 10 ms 7416 KB Output is correct
5 Correct 10 ms 7416 KB Output is correct
6 Correct 10 ms 7416 KB Output is correct
7 Correct 11 ms 7420 KB Output is correct
8 Correct 10 ms 7416 KB Output is correct
9 Correct 10 ms 7416 KB Output is correct
10 Correct 9 ms 7416 KB Output is correct
11 Correct 678 ms 40244 KB Output is correct
12 Correct 729 ms 43768 KB Output is correct
13 Correct 672 ms 43768 KB Output is correct
14 Correct 715 ms 43768 KB Output is correct
15 Correct 701 ms 43768 KB Output is correct
16 Correct 772 ms 43744 KB Output is correct
17 Correct 734 ms 44384 KB Output is correct
18 Correct 775 ms 44412 KB Output is correct
19 Correct 744 ms 44408 KB Output is correct
20 Correct 730 ms 44408 KB Output is correct
21 Correct 734 ms 44536 KB Output is correct
22 Runtime error 399 ms 49752 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Halted 0 ms 0 KB -