Submission #41769

#	Time	Username	Problem	Language	Result	Execution time	Memory
41769		top34051	Zagrade (COI17_zagrade)	C++14	100 / 100	955 ms	84376 KiB

zagrade

#include<bits/stdc++.h>
using namespace std;

#define pb push_back
const int maxn = 3e5 + 5;

int n;
char s[maxn];
int sz[maxn], cen[maxn];
vector<int> way[maxn];

long long ans;
int cnt[2][maxn];

void dfs(int t, int u, int last, int cur, int mx, vector<int> &vec) {
	if(t==0) cur += s[u]=='(' ? 1 : -1;
	else cur += s[u]=='(' ? -1 : 1;
	mx = max(mx, cur);
	if(cur==mx) vec.pb(cur);
	for(auto v : way[u]) {
		if(v==last || cen[v]) continue;
		dfs(t,v,u,cur,mx,vec);
	}
}

void solve(int u) {
	int t = s[u]=='(' ? -1 : 1;
	vector<int> L, R;
	for(auto v : way[u]) {
		if(cen[v]) continue;
		vector<int> tl, tr;
		dfs(0,v,u,0,0,tl);
		dfs(1,v,u,t,max(t,0),tr);
		for(auto x : tl) {
			L.push_back(x);
			ans += cnt[1][x];
			if(x==t) ans++;
		}
		for(auto x : tr) {
			R.push_back(x);
			ans += cnt[0][x];
			if(x==0) ans++;
		}
		for(auto x : tl) cnt[0][x]++;
		for(auto x : tr) cnt[1][x]++;
	}
	for(auto x : L) cnt[0][x]--;
	for(auto x : R) cnt[1][x]--;
}

void survey(int u, int last) {
//    printf("survey %d %d\n",u,last);
	sz[u] = 1;
	for(auto v : way[u]) {
		if(v==last || cen[v]) continue;
		survey(v, u);
		sz[u] += sz[v];
	}
}

void decom(int u) {
	survey(u, 0);
	int x = u, last = 0;
	redo:
	for(auto v : way[x]) {
		if(v==last || cen[v]) continue;
		if(sz[v]>sz[u]/2) {
			last = x; x = v;
			goto redo;
		}
	}
	solve(x);
	cen[x] = 1;
	for(auto v : way[x]) {
		if(cen[v]) continue;
		decom(v);
	}
}

int main() {
    int x,y;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf(" %c",&s[i]);
	for(int i=0;i<n-1;i++) {
		scanf("%d%d",&x,&y);
		way[x].pb(y); way[y].pb(x);
	}
	decom(1);
	printf("%lld",ans);
}

Compilation message (stderr)

zagrade.cpp: In function 'int main()':
zagrade.cpp:82:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
zagrade.cpp:83:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf(" %c",&s[i]);
                                          ^
zagrade.cpp:85:22: 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