oj.uz

Submission #209735

# Submission time Handle Problem Language Result Execution time Memory
209735 2020-03-15T12:55:33 Z ruler Zagrade (COI17_zagrade) C++14
40 / 100
 730 ms 50552 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 = 4e5 + 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 12 ms 9848 KB Output is correct
2 Correct 12 ms 9848 KB Output is correct
3 Correct 12 ms 9848 KB Output is correct
4 Correct 12 ms 9848 KB Output is correct
5 Correct 12 ms 9848 KB Output is correct
6 Correct 12 ms 9848 KB Output is correct
7 Correct 12 ms 9848 KB Output is correct
8 Correct 12 ms 9848 KB Output is correct
9 Correct 12 ms 9848 KB Output is correct
10 Correct 11 ms 9844 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 696 ms 43948 KB Output is correct
2 Correct 703 ms 44024 KB Output is correct
3 Correct 692 ms 43896 KB Output is correct
4 Correct 730 ms 44024 KB Output is correct
5 Correct 724 ms 44048 KB Output is correct
6 Correct 717 ms 43512 KB Output is correct
7 Correct 706 ms 42616 KB Output is correct
8 Correct 702 ms 42616 KB Output is correct
9 Correct 693 ms 42616 KB Output is correct
10 Correct 700 ms 42616 KB Output is correct
11 Correct 685 ms 42664 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9848 KB Output is correct
2 Correct 12 ms 9848 KB Output is correct
3 Correct 12 ms 9848 KB Output is correct
4 Correct 12 ms 9848 KB Output is correct
5 Correct 12 ms 9848 KB Output is correct
6 Correct 12 ms 9848 KB Output is correct
7 Correct 12 ms 9848 KB Output is correct
8 Correct 12 ms 9848 KB Output is correct
9 Correct 12 ms 9848 KB Output is correct
10 Correct 11 ms 9844 KB Output is correct
11 Correct 696 ms 43948 KB Output is correct
12 Correct 703 ms 44024 KB Output is correct
13 Correct 692 ms 43896 KB Output is correct
14 Correct 730 ms 44024 KB Output is correct
15 Correct 724 ms 44048 KB Output is correct
16 Correct 717 ms 43512 KB Output is correct
17 Correct 706 ms 42616 KB Output is correct
18 Correct 702 ms 42616 KB Output is correct
19 Correct 693 ms 42616 KB Output is correct
20 Correct 700 ms 42616 KB Output is correct
21 Correct 685 ms 42664 KB Output is correct
22 Runtime error 388 ms 50552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Halted 0 ms 0 KB -