Submission #26340

#	Time	Username	Problem	Language	Result	Execution time	Memory
26340		kdh9949	Zagrade (COI17_zagrade)	C++14	100 / 100	1346 ms	37344 KiB

zagrade

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

int n, v[300010], s[300010], chk[300010], cnt[300010];
char str[300010];
vector<int> e[300010];

int sf(int x, int p){
	s[x] = 1;
	for(auto &i : e[x]){
		if(i != p && !chk[i]) s[x] += sf(i, x);
	}
	return s[x];
}

int cf(int x, int p, int t){
	for(auto &i : e[x]){
		if(i != p && !chk[i] && s[i] > t / 2) return cf(i, x, t);
	}
	return x;
}

void g(ll &ret, int t, int mv, int x, int p, int d, int mx){
	if(d == mx){
		if(!t) ret += cnt[d];
		else cnt[d]++;
	}
	for(auto &i : e[x]){
		if(i != p && !chk[i]) g(ret, t, mv, i, x, d + mv * v[i], max(mx, d + mv * v[i]));
	}
}

ll f(int x){
	int ts = sf(x, 0);
	x = cf(x, 0, ts);
	chk[x] = 1;
	ll ret = 0;
	fill(cnt, cnt + ts + 1, 0); if(v[x] > 0) cnt[1] = 1;
	for(auto &i : e[x]){
		if(!chk[i]){
			g(ret, 0, -1, i, x, -v[i], max(0, -v[i]));
			g(ret, 1, 1, i, x, v[x] + v[i], max({0, v[x], v[x] + v[i]}));
		}
	}
	fill(cnt, cnt + ts + 1, 0); if(v[x] < 0) cnt[1] = 1;
	for(auto &i : e[x]){
		if(!chk[i]){
			g(ret, 0, 1, i, x, v[i], max(0, v[i]));
			g(ret, 1, -1, i, x, -(v[x] + v[i]), max({0, -v[x], -(v[x] + v[i])}));
		}
	}
	for(auto &i : e[x]) if(!chk[i]) ret += f(i);
	return ret;
}

int main(){
	scanf("%d%s", &n, str + 1);
	for(int i = 1; i <= n; i++) v[i] = 2 * (str[i] == '(') - 1;
	for(int i = 0, x, y; i < n - 1; i++){
		scanf("%d%d", &x, &y);
		e[x].push_back(y);
		e[y].push_back(x);
	}
	printf("%lld\n", f(1));
}

Compilation message (stderr)

zagrade.cpp: In function 'int main()':
zagrade.cpp:58:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%s", &n, str + 1);
                            ^
zagrade.cpp:61:24: 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