Submission #104552

#	Time	Username	Problem	Language	Result	Execution time	Memory
104552		Shtef	Zagrade (COI17_zagrade)	C++14	0 / 100	3010 ms	42380 KiB

zagrade

#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;
		sol += dp[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: 0 / 10
• Subtask 2: 0 / 30
• Subtask 3: 0 / 60