oj.uz

Submission #698573

# Submission time Handle Problem Language Result Execution time Memory
698573 2023-02-13T21:27:44 Z jcelin Zagrade (COI17_zagrade) C++14
100 / 100
 1389 ms 76840 KB 
#include <bits/stdc++.h>
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

#define ii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vii vector<ii>
#define vll vector<ll>
#define vpll vector<pll>
#define msi multiset<int>
#define si set<int>
#define PB push_back
#define PF push_front
#define PPB pop_back
#define PPF pop_front
#define X first
#define Y second
#define MP make_pair
#define FOR(i, a, b) for (int i = int(a); i < int(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()

const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const int dxx[] = {-1, 1, 0, 0, 1, 1, -1, -1};
const int dyy[] = {0, 0, -1, 1, -1, 1, -1, 1};
const int mod = 1e9 + 7;
const int MOD = 1e9 + 7;
const int MAXN = 1e6 + 7;
const int inf = mod;
const ll INF = 1e18;
const int logo = 20;
const int off = 1 << logo;
const int trsz = off << 1;

string s;
int n, sz[MAXN];
bool bio[MAXN];
ll ans = 0;
vi g[MAXN];
map<ii, int> f;

void dfs(int u, int p = -1){
	sz[u] = 1;
	for(auto &x : g[u]) if(x != p and !bio[x]) dfs(x, u), sz[u] += sz[x];
}

int cen(int u, int p, int szi){
	for(auto &x : g[u]) if(x != p and !bio[x]) if(sz[x] * 2 > szi) return cen(x, u, szi);
	return u; 
}

void dodaj(int x, int t, int a = 0, int b = 0, int p = -1){
	if(s[x] == '(') a++;
	else{
		if(a) a--;
		else b++;
	}
	
	f[{a, b}] += t;
	
	for(auto &y : g[x]) if(!bio[y] and y != p) dodaj(y, t, a, b, x);
}

void rijesi(int x, int centr, int a = 0, int b = 0, int p = -1){
	if(s[x] == ')') b++;
	else{
		if(b) b--;
		else a++;
	}
	
	int na = a, nb = b;
	if(s[centr] == '(') na++;
	else{
		if(na) na--;
		else nb++;
	}
	
	if(nb == 0) ans += (ll)f[{0, na}];
	for(auto &y : g[x]) if(!bio[y] and y != p) rijesi(y, centr, a, b, x);
}

void decompose(int u){
	dfs(u);
	int centr = cen(u, -1, sz[u]);
	//sad napravi rjesenje
	
	bio[centr] = 1;
	f.clear(); f[{0, 0}] = 1;
	for(auto &x : g[centr]) if(!bio[x]) dodaj(x, 1);
	
	if(s[centr] == '(') ans += (ll)f[{0, 1}];

	for(auto &x : g[centr]){
		if(bio[x]) continue;
		dodaj(x, -1);
		rijesi(x, centr);
		dodaj(x, 1);
	}
	
	for(auto &x : g[centr]) if(!bio[x]) decompose(x);
}

void solve(){
	cin >> n >> s;
	REP(i, n - 1){
		int a, b;
		cin >> a >> b;
		a--, b--;
		g[a].PB(b);
		g[b].PB(a);
	}
	dfs(0);
	decompose(0);
	cout << ans << "\n";
}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int t=1;
	//cin >> t;
	while(t--)solve();
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23836 KB Output is correct
2 Correct 13 ms 23836 KB Output is correct
3 Correct 13 ms 23824 KB Output is correct
4 Correct 13 ms 23764 KB Output is correct
5 Correct 14 ms 23796 KB Output is correct
6 Correct 14 ms 23820 KB Output is correct
7 Correct 15 ms 23764 KB Output is correct
8 Correct 14 ms 23764 KB Output is correct
9 Correct 13 ms 23820 KB Output is correct
10 Correct 12 ms 23764 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 919 ms 58180 KB Output is correct
2 Correct 1389 ms 65068 KB Output is correct
3 Correct 921 ms 58248 KB Output is correct
4 Correct 1318 ms 64400 KB Output is correct
5 Correct 898 ms 58364 KB Output is correct
6 Correct 1101 ms 60572 KB Output is correct
7 Correct 936 ms 58356 KB Output is correct
8 Correct 1076 ms 61912 KB Output is correct
9 Correct 904 ms 58184 KB Output is correct
10 Correct 1345 ms 76840 KB Output is correct
11 Correct 455 ms 57912 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23836 KB Output is correct
2 Correct 13 ms 23836 KB Output is correct
3 Correct 13 ms 23824 KB Output is correct
4 Correct 13 ms 23764 KB Output is correct
5 Correct 14 ms 23796 KB Output is correct
6 Correct 14 ms 23820 KB Output is correct
7 Correct 15 ms 23764 KB Output is correct
8 Correct 14 ms 23764 KB Output is correct
9 Correct 13 ms 23820 KB Output is correct
10 Correct 12 ms 23764 KB Output is correct
11 Correct 919 ms 58180 KB Output is correct
12 Correct 1389 ms 65068 KB Output is correct
13 Correct 921 ms 58248 KB Output is correct
14 Correct 1318 ms 64400 KB Output is correct
15 Correct 898 ms 58364 KB Output is correct
16 Correct 1101 ms 60572 KB Output is correct
17 Correct 936 ms 58356 KB Output is correct
18 Correct 1076 ms 61912 KB Output is correct
19 Correct 904 ms 58184 KB Output is correct
20 Correct 1345 ms 76840 KB Output is correct
21 Correct 455 ms 57912 KB Output is correct
22 Correct 1198 ms 39308 KB Output is correct
23 Correct 1039 ms 39240 KB Output is correct
24 Correct 1027 ms 39308 KB Output is correct
25 Correct 1031 ms 39336 KB Output is correct
26 Correct 953 ms 45592 KB Output is correct
27 Correct 931 ms 42892 KB Output is correct
28 Correct 915 ms 41672 KB Output is correct
29 Correct 1376 ms 76612 KB Output is correct
30 Correct 1339 ms 76712 KB Output is correct
31 Correct 105 ms 39012 KB Output is correct
32 Correct 455 ms 57848 KB Output is correct