oj.uz

Submission #209728

# Submission time Handle Problem Language Result Execution time Memory
209728 2020-03-15T12:45:36 Z ruler Zagrade (COI17_zagrade) C++14
10 / 100
 3000 ms 46164 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(n + 1, 0), dw(n + 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(n + 1, 0), cdw(n + 1, 0);
		DFS(u, cup, 1, + 1, v), DFS(u, cdw, 0, + 1, v);
		for (int i = 0; i < n + 1; 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 13 ms 7416 KB Output is correct
2 Correct 13 ms 7416 KB Output is correct
3 Correct 13 ms 7416 KB Output is correct
4 Correct 14 ms 7416 KB Output is correct
5 Correct 13 ms 7416 KB Output is correct
6 Correct 14 ms 7416 KB Output is correct
7 Correct 13 ms 7416 KB Output is correct
8 Correct 13 ms 7416 KB Output is correct
9 Correct 13 ms 7416 KB Output is correct
10 Correct 13 ms 7416 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3071 ms 46164 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 7416 KB Output is correct
2 Correct 13 ms 7416 KB Output is correct
3 Correct 13 ms 7416 KB Output is correct
4 Correct 14 ms 7416 KB Output is correct
5 Correct 13 ms 7416 KB Output is correct
6 Correct 14 ms 7416 KB Output is correct
7 Correct 13 ms 7416 KB Output is correct
8 Correct 13 ms 7416 KB Output is correct
9 Correct 13 ms 7416 KB Output is correct
10 Correct 13 ms 7416 KB Output is correct
11 Execution timed out 3071 ms 46164 KB Time limit exceeded
12 Halted 0 ms 0 KB -