Submission #26329

#	Time	Username	Problem	Language	Result	Execution time	Memory
26329		khsoo01	Zagrade (COI17_zagrade)	C++11	100 / 100	1573 ms	58732 KiB

zagrade

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 300005;

ll n, tot, chi[N], a[N], ans;
bool blk[N];
char ipt[N];

vector<ll> adj[N];
map<ll, ll> pl, mi;

void calc (ll C, ll P) {
	tot++;
	chi[C] = 1;
	for(auto &T : adj[C]) {
		if(T == P || blk[T]) continue;
		calc(T, C);
		chi[C] += chi[T];
	}
}

ll findcen (ll C, ll P) {
	ll mx = 0;
	for(auto &T : adj[C]) {
		if(T == P || blk[T]) continue;
		if(chi[mx] < chi[T]) mx = T;
	}
	if(chi[mx] <= tot/2) return C;
	return findcen(mx, C);
}

void match (ll C, ll P, ll M, ll V, ll B, map<ll,ll> &S) {
	if(V == M) ans += S[V];
	for(auto &T : adj[C]) {
		if(T == P || blk[T]) continue;
		match(T, C, max(M, V+a[T]*B), V+a[T]*B, B, S);
	}
}

void save (ll C, ll P, ll M, ll V, ll B, map<ll,ll> &S) {
	if(V == M) S[V]++;
	for(auto &T : adj[C]) {
		if(T == P || blk[T]) continue;
		save(T, C, max(M, V+a[T]*B), V+a[T]*B, B, S);
	}
}

void solve (ll I) {
	tot = 0; calc(I, 0);
	ll C = findcen(I, 0);
	pl.clear(); mi.clear();
	pl[a[C]]++; mi[0]++;
	for(auto &T : adj[C]) {
		if(blk[T]) continue;
		ll M1 = max({0ll, a[C], a[T]+a[C]}), M2 = max(0ll, -a[T]);
		match(T, C, M1, a[T]+a[C], 1, mi);
		match(T, C, M2, -a[T], -1, pl);
		save(T, C, M1, a[T]+a[C], 1, pl);
		save(T, C, M2, -a[T], -1, mi);
	}
	blk[C] = true;
	for(auto &T : adj[C]) {
		if(blk[T]) continue;
		solve(T);
	}
}

int main()
{
	scanf("%lld%s",&n,ipt+1);
	for(ll i=1;i<=n;i++) {
		a[i] = 2*(ipt[i] == '(') - 1;
	}
	for(ll i=1;i<n;i++) {
		ll A, B;
		scanf("%lld%lld",&A,&B);
		adj[A].push_back(B);
		adj[B].push_back(A);
	}
	solve(1);
	printf("%lld\n",ans);
}

Compilation message (stderr)

zagrade.cpp: In function 'int main()':
zagrade.cpp:71:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%s",&n,ipt+1);
                          ^
zagrade.cpp:77:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld",&A,&B);
                          ^

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