oj.uz

Submission #104553

# Submission time Handle Problem Language Result Execution time Memory
104553 2019-04-07T22:41:49 Z Shtef Zagrade (COI17_zagrade) C++14
10 / 100
 3000 ms 38156 KB 
#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;

int n, val[300005], ss[300005], br;
ll dp[300005], sol;
string s;
vector <int> ms[300005];
bool bio[300005];

void dfs1(int x, int p){
	br++;
	ss[x] = 1;
	for(vector <int>::iterator i = ms[x].begin() ; i != ms[x].end() ; ++i){
		int o = *i;
		if(o == p || bio[o])
			continue;
		dfs1(o, x);
		ss[x] += ss[o];
	}
}

int dfs2(int x, int p){
	for(vector <int>::iterator i = ms[x].begin() ; i != ms[x].end() ; ++i){
		int o = *i;
		if(o == p || bio[o])
			continue;
		if(ss[o] > br / 2)
			return dfs2(o, x);
	}
	return x;
}

void processdp(int x, int p, int sad, int sve, int add){
	sad = (val[x] == 1 ? max(1, sad + 1) : sad - 1);
	sve -= (sad < 0);
	if(sad <= 0){
		dp[-sve] += add;
	}
	for(vector <int>::iterator i = ms[x].begin() ; i != ms[x].end() ; ++i){
		int o = *i;
		if(o == p || bio[o])
			continue;
		processdp(o, x, sad, sve, add);
	}
}

void dfs3(int x, int p, int sad, int sve){
	sad = (val[x] == -1 ? min(-1, sad - 1) : sad + 1);
	sve += (sad > 0);
	if(sad >= 0){
		sol += dp[sve];
	}
	for(vector <int>::iterator i = ms[x].begin() ; i != ms[x].end() ; ++i){
		int o = *i;
		if(o == p || bio[o])
			continue;
		dfs3(o, x, sad, sve);
	}
}

void decompose(int root){
	dfs1(root, -1);
	int centroid = dfs2(root, -1);
	bio[centroid] = 1;
	processdp(centroid, -1, 0, 0, 1);
	sol += dp[0];
	for(vector <int>::iterator i = ms[centroid].begin() ; i != ms[centroid].end() ; ++i){
		int o = *i;
		if(bio[o])
			continue;
		processdp(o, centroid, val[centroid], min(0, val[centroid]), -1);
		dfs3(o, centroid, 0, 0);
		processdp(o, centroid, val[centroid], min(0, val[centroid]), 1);
	}
	//cout << centroid << ' ' << sol << endl;
	processdp(centroid, -1, 0, 0, -1);
	for(vector <int>::iterator i = ms[centroid].begin() ; i != ms[centroid].end() ; ++i){
		int o = *i;
		if(bio[o])
			continue;
		decompose(o);
	}
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
cin >> s;
for(int i = 0 ; i < n ; ++i){
	if(s[i] == '('){
		val[i + 1] = 1;
	}
	else{
		val[i + 1] = -1;
	}
}
for(int i = 0 ; i < n - 1 ; ++i){
	int x, y;
	cin >> x >> y;
	ms[x].push_back(y);
	ms[y].push_back(x);
}
decompose(1);
cout << sol << endl;

return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 7424 KB Output is correct
2 Correct 10 ms 7424 KB Output is correct
3 Correct 9 ms 7424 KB Output is correct
4 Correct 11 ms 7552 KB Output is correct
5 Correct 10 ms 7540 KB Output is correct
6 Correct 10 ms 7552 KB Output is correct
7 Correct 10 ms 7424 KB Output is correct
8 Correct 10 ms 7552 KB Output is correct
9 Correct 10 ms 7424 KB Output is correct
10 Correct 9 ms 7424 KB Output is correct

Subtask #2
0 / 30.0

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

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 7424 KB Output is correct
2 Correct 10 ms 7424 KB Output is correct
3 Correct 9 ms 7424 KB Output is correct
4 Correct 11 ms 7552 KB Output is correct
5 Correct 10 ms 7540 KB Output is correct
6 Correct 10 ms 7552 KB Output is correct
7 Correct 10 ms 7424 KB Output is correct
8 Correct 10 ms 7552 KB Output is correct
9 Correct 10 ms 7424 KB Output is correct
10 Correct 9 ms 7424 KB Output is correct
11 Execution timed out 3022 ms 38156 KB Time limit exceeded
12 Halted 0 ms 0 KB -