oj.uz

Submission #547639

# Submission time Handle Problem Language Result Execution time Memory
547639 2022-04-11T06:41:57 Z ngpin04 Zagrade (COI17_zagrade) C++14
100 / 100
 877 ms 43628 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define ALL(x) (x).begin(), (x).end() 
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}
const int N = 3e5 + 5; 
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);

vector <int> adj[N];

long long ans;

int cnt[N];
int sz[N];
int a[N];
int n;

bool bk[N];

int dfs(int u, int p = -1) {
	int &res = sz[u];
	res = 1;
	for (int v : adj[u]) 
		if (v != p && !bk[v]) 
			res += dfs(v, u);
	return res;
}

int getcen(int u, int S, int p = -1) {
	for (int v : adj[u]) 
		if (v != p && !bk[v] && sz[v] * 2 >= S) 
			return getcen(v, S, u);
	return u;
}

void dfs(int u, int cur, int minval, int p = -1) {
	cur += a[u];
	mini(minval, cur);

	if (cur == minval && cur <= 0)
		ans += cnt[-cur];

	for (int v : adj[u]) 
		if (v != p && !bk[v]) 
			dfs(v, cur, minval, u);
}

void solve(int u, int cur, int minval, int p = -1) {
	cur += a[u];
	minval += a[u];
	mini(minval, 0);

	if (minval == 0) 
		cnt[cur]++;

	for (int v : adj[u]) 
		if (v != p && !bk[v]) 	
			solve(v, cur, minval, u);
}

void dfs1(int u, int cur = 0, int p = -1) {
	cur += a[u];
	if (cur < 0)
		return;

	if (cur == 0)
		ans++;

	for (int v : adj[u]) 
		if (v != p && !bk[v])
			dfs1(v, cur, u);
}

void centroid(int u) {
	int s = dfs(u);
	int cen = getcen(u, s);
	bk[cen] = true;
	// cerr << "centroid: " << cen << "\n";

	for (int v : adj[cen]) if (!bk[v]) {
		dfs(v, 0, 0, cen);
		solve(v, a[cen], min(a[cen], 0), cen);
	}

	ans += cnt[0];

	for (int i = 0; i <= s; i++)
		cnt[i] = 0;

	reverse(ALL(adj[cen]));

	for (int v : adj[cen]) if (!bk[v]) {
		dfs(v, 0, 0, cen);
		solve(v, a[cen], min(a[cen], 0), cen);
	}

	for (int i = 0; i <= s; i++)
		cnt[i] = 0;

	dfs1(cen);

	// cerr << ans << "\n";

	for (int v : adj[cen]) {
		if (!bk[v]) {
			// cerr << cen << " " << v << "\n";
			centroid(v);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	#ifdef ONLINE_JUDGE
	// freopen(TASK".inp","r",stdin);
	// freopen(TASK".out","w",stdout);
	#endif
	cin >> n;
	for (int i = 1; i <= n; i++) {
		char c; cin >> c;
		a[i] = (c == '(') ? 1 : -1;
	}

	for (int i = 1; i < n; i++){
		int u,v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	centroid(1);

	cout << ans;
	return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 43472 KB Output is correct
2 Correct 352 ms 43468 KB Output is correct
3 Correct 361 ms 43628 KB Output is correct
4 Correct 349 ms 43616 KB Output is correct
5 Correct 352 ms 43528 KB Output is correct
6 Correct 378 ms 43528 KB Output is correct
7 Correct 354 ms 43492 KB Output is correct
8 Correct 384 ms 43500 KB Output is correct
9 Correct 344 ms 43448 KB Output is correct
10 Correct 352 ms 43480 KB Output is correct
11 Correct 362 ms 43536 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7508 KB Output is correct
2 Correct 5 ms 7440 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 5 ms 7380 KB Output is correct
6 Correct 5 ms 7380 KB Output is correct
7 Correct 6 ms 7508 KB Output is correct
8 Correct 6 ms 7380 KB Output is correct
9 Correct 5 ms 7380 KB Output is correct
10 Correct 4 ms 7380 KB Output is correct
11 Correct 354 ms 43472 KB Output is correct
12 Correct 352 ms 43468 KB Output is correct
13 Correct 361 ms 43628 KB Output is correct
14 Correct 349 ms 43616 KB Output is correct
15 Correct 352 ms 43528 KB Output is correct
16 Correct 378 ms 43528 KB Output is correct
17 Correct 354 ms 43492 KB Output is correct
18 Correct 384 ms 43500 KB Output is correct
19 Correct 344 ms 43448 KB Output is correct
20 Correct 352 ms 43480 KB Output is correct
21 Correct 362 ms 43536 KB Output is correct
22 Correct 816 ms 25008 KB Output is correct
23 Correct 763 ms 24924 KB Output is correct
24 Correct 877 ms 25028 KB Output is correct
25 Correct 788 ms 24928 KB Output is correct
26 Correct 463 ms 30936 KB Output is correct
27 Correct 473 ms 28316 KB Output is correct
28 Correct 475 ms 27140 KB Output is correct
29 Correct 350 ms 43484 KB Output is correct
30 Correct 345 ms 43464 KB Output is correct
31 Correct 93 ms 24512 KB Output is correct
32 Correct 363 ms 43592 KB Output is correct