oj.uz

Submission #990635

# Submission time Handle Problem Language Result Execution time Memory
990635 2024-05-30T20:07:17 Z ZeroCool Zagrade (COI17_zagrade) C++14
100 / 100
 717 ms 60992 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
using namespace std;

template<typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define int long long
#define ll long long
#define ar array
#define ld long double

//#define endl '\n'

const ll N = 4e5 + 20;
const ll INF = 1e17;
const int MOD = 1e9 + 7;

int n, A[N], del[N], ans, sz[N];
vector<int> g[N];
map<int,int> cnt;

int dfs1(int x,int p){
	sz[x] = 1;
	for(auto u : g[x]){
		if(u == p || del[u])continue;
		sz[x] += dfs1(u, x);
	}
	return sz[x];
}

int C(int x,int p,int s){
	for(auto u: g[x]){
		if(u == p || del[u])continue;
		if(sz[u] * 2 > s)return C(u, x, s);
	}
	return x;
}

void dfs2(int x,int p, int sum, int mn,int mx){
	sum += A[x];
	mx = max(mx, sum);
	mn = min(mn, sum);
	if(sum <= mn){
		ans += cnt[-mn];
	}
	for(auto u: g[x]){
		if(u == p || del[u])continue;
		dfs2(u, x, sum, mn, mx);
	}
}

void dfs3(int x,int p,int sum, int mn,int mx){
	sum += A[x];
	mx = max(mx, sum);
	mn = min(mn, sum);
	if(sum >= mx){
		cnt[sum]++;
	}
	for(auto u: g[x]){
		if(u == p || del[u])continue;
		dfs3(u, x, sum, mn, mx);
	}
}

void cen(int x){
	int c = C(x, x, dfs1(x, x));
	del[c] = 1;
	cnt.clear();
	if(A[c] == 1)cnt[A[c]]++;
	for(auto u: g[c]){
		if(del[u])continue;
		dfs2(u, c, 0, 0, 0);
		dfs3(u, c, A[c], min(A[c], 0ll), max(A[c], 0ll));
	}
	ans += cnt[0];
	cnt.clear();
	reverse(g[c].begin(), g[c].end());
	for(auto u: g[c]){
		if(del[u])continue;
		dfs2(u, c, 0, 0, 0);
		dfs3(u, c, A[c], min(A[c], 0ll), max(A[c], 0ll));
	}
	for(auto u: g[c]){
		if(!del[u])cen(u);
	}
}

void VladiDadi(){
	cin>>n;
	string s;
	cin>>s;
	for(int i = 0;i<n;i++)A[i] = (s[i] == '(' ? 1 : -1);
	for(int i =1 ;i<n;i++){
		int u, v;
		cin>>u>>v;
		--u, --v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	cen(0);
	cout<<ans;
}



signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t = 1;

	
	//cin>>t;
	while(t--)
	VladiDadi();
}

Subtask #1
10.0 / 10.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 325 ms 51744 KB Output is correct
2 Correct 505 ms 55272 KB Output is correct
3 Correct 323 ms 51736 KB Output is correct
4 Correct 456 ms 54500 KB Output is correct
5 Correct 325 ms 51584 KB Output is correct
6 Correct 385 ms 52968 KB Output is correct
7 Correct 323 ms 51496 KB Output is correct
8 Correct 391 ms 52880 KB Output is correct
9 Correct 326 ms 51544 KB Output is correct
10 Correct 708 ms 60908 KB Output is correct
11 Correct 253 ms 51684 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 3 ms 13012 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 3 ms 12892 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct
9 Correct 3 ms 12892 KB Output is correct
10 Correct 2 ms 12900 KB Output is correct
11 Correct 325 ms 51744 KB Output is correct
12 Correct 505 ms 55272 KB Output is correct
13 Correct 323 ms 51736 KB Output is correct
14 Correct 456 ms 54500 KB Output is correct
15 Correct 325 ms 51584 KB Output is correct
16 Correct 385 ms 52968 KB Output is correct
17 Correct 323 ms 51496 KB Output is correct
18 Correct 391 ms 52880 KB Output is correct
19 Correct 326 ms 51544 KB Output is correct
20 Correct 708 ms 60908 KB Output is correct
21 Correct 253 ms 51684 KB Output is correct
22 Correct 383 ms 34528 KB Output is correct
23 Correct 389 ms 34536 KB Output is correct
24 Correct 387 ms 34536 KB Output is correct
25 Correct 407 ms 34536 KB Output is correct
26 Correct 387 ms 40308 KB Output is correct
27 Correct 389 ms 37604 KB Output is correct
28 Correct 407 ms 36652 KB Output is correct
29 Correct 717 ms 60992 KB Output is correct
30 Correct 699 ms 60912 KB Output is correct
31 Correct 65 ms 34340 KB Output is correct
32 Correct 262 ms 51656 KB Output is correct