Submission #104556

#	Time	Username	Problem	Language	Result	Execution time	Memory
104556		Shtef	Zagrade (COI17_zagrade)	C++14	100 / 100	1460 ms	43940 KiB

zagrade

#include <iostream>
#include <vector>
#include <cstdio>

using namespace std;

typedef long long ll;

int n, val[300005], ss[300005], br;
ll dp[300005], sol;
char s[300005];
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){
	br = 0;
	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(){
scanf("%d", &n);
scanf("%s", &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;
	scanf("%d %d", &x, &y);
	ms[x].push_back(y);
	ms[y].push_back(x);
}
decompose(1);
printf("%lld\n", sol);

return 0;
}

Compilation message (stderr)

zagrade.cpp: In function 'int main()':
zagrade.cpp:93:15: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[300005]' [-Wformat=]
 scanf("%s", &s);
             ~~^
zagrade.cpp:92:6: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf("%d", &n);
 ~~~~~^~~~~~~~~~
zagrade.cpp:93:6: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf("%s", &s);
 ~~~~~^~~~~~~~~~
zagrade.cpp:104:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &x, &y);
  ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60