Submission #127213

#	Time	Username	Problem	Language	Result	Execution time	Memory
127213		Adhyyan1252	Zagrade (COI17_zagrade)	C++11	100 / 100	1070 ms	67268 KiB

zagrade

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define DEBUG false
vector<vector<int> > g;
string s; 
int n; 
vector<int> alive;
int ans = 0;
vector<int> sz;

void dfs1(int cur, int par){
	if(DEBUG) cout<<"INSIDE "<<cur<<endl;
	sz[cur] = 1;
	for(int u: g[cur]){
		if(u == par || alive[u] == false) continue;
		dfs1(u, cur);
		sz[cur] += sz[u];
	}
}

int find(int cur, int par, int size){
	int big = -1;
	for(int u: g[cur]){
		if(u == par || alive[u] == false)  continue;
		if(big == -1 || sz[u] > sz[big]){
			big = u;
		}
	}
	if(big == -1 || sz[big]*2 <= size) return cur;
	else return find(big, cur, size);
}

vector<int> f;
vector<vector<int> > subf;
int off = 0;
void dfs2(int cur, int par, int val, int low, int part){
	val += s[cur] == '('?1:-1;
	low = min(low, val);
	if(low == val){
		f[val + off]++;
		subf[part][val + subf[part].size()/2]++;
	}
	for(int u: g[cur]){
		if(u == par || alive[u] == false) continue;
		dfs2(u, cur, val, low, part);
	}
}

void dfs3(int cur, int par, int val, int low, int part){
	int cval = s[cur] == '('?1:-1;
	val += cval;
	low = min(low+cval, cval);

	if(low >= 0){
		ans += f[-val + off] - subf[part][-val + subf[part].size()/2];
		if(DEBUG)cout<<"INC ANS "<<cur<<" "<<f[-val + off] - subf[part][-val + subf[part].size()/2]<<endl;
	}
	
	for(int u: g[cur]){
		if(u == par || alive[u] == false) continue;
		dfs3(u, cur, val, low, part);
	}
}

void decomp(int cur){
	if(DEBUG)cout<<"CUR : "<<cur<<endl;
	dfs1(cur, -1);
	int cent = find(cur, -1, sz[cur]);
	if(DEBUG)cout<<"CENT "<<cent<<endl;
	f = vector<int>(sz[cent]*2+1, 0);
	off = sz[cent];
//	cout<<"SZ: "<<g[cent].size()<<" "<<subf.size()<<endl;
	int val = s[cent] == '('?1:-1;
	f[val + off]++;
	
	for(int i = 0; i < g[cent].size(); i++){
		if(!alive[g[cent][i]]) continue;
	
		subf[i] = vector<int>(sz[g[cent][i]]*2+10, 0);
	
		dfs2(g[cent][i], cent, val, min(val, 0LL), i);
	}
	for(int i = 0; i < g[cent].size(); i++){
		if(!alive[g[cent][i]]) continue;
		dfs3(g[cent][i], cent, 0, 0, i);
	}
	ans += f[0 + off];
	alive[cent] = false;
	for(int u: g[cent]){
		if(alive[u]) decomp(u);
	}
}



signed main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>n;
	cin>>s;
	g.resize(n);
	for(int i = 0; i < n-1; i++){
		int u, v; cin>>u>>v; u--, v--;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	alive = vector<int>(n, true);
	ans = 0;
	sz = vector<int>(n, 0);
	subf = vector<vector<int> > (2*n);
	decomp(0);
	cout<<ans<<endl;
}

Compilation message (stderr)

zagrade.cpp: In function 'void decomp(long long int)':
zagrade.cpp:79:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[cent].size(); i++){
                 ~~^~~~~~~~~~~~~~~~
zagrade.cpp:86:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[cent].size(); i++){
                 ~~^~~~~~~~~~~~~~~~

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