Submission #931601

#	Time	Username	Problem	Language	Result	Execution time	Memory
931601		vjudge1	Zagrade (COI17_zagrade)	C++17	10 / 100	34 ms	12260 KiB

zagrade

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

#define pb              push_back
#define F               first
#define S               second
#define len(x)          (int)x.size()
#define all(x)          x.begin(),x.end()
#define file            freopen("matrix.txt", "r", stdin);freopen("a.out", "w", stdout);
#define kill(x)         {cout << x << '\n'; continue;}
#define int             long long

const int maxn = 100000 + 5, LG = 31, MOD = 1e9+7;// 998244353
const ll inf =  1061109567;

//priority_queue< pii , vector<pii> , greater<pii> pq;

int n, ans;
string s;
vector<int> g[maxn];

void dfs(int v, int par = -1, string ss = "") {
	ss.pb(s[v-1]);
	// cerr << v << ' ' << ss << '\n';
	for(int u : g[v])
		if(u ^ par)
			dfs(u, v, ss);

	if(len(ss) & 1) return;
	int a = 0, b = 0;
	for(int i = 0; i < len(ss); ++i) {
		a += (ss[i] == '(');
		b += (ss[i] == ')');
		if(b > a) return;
	}
	if(a == b) {
		++ans;
	//	cerr << "added " << v << '\n';
	}
}

signed main() {
	ios::sync_with_stdio(0), cin.tie(0);	
	cin >> n >> s;

	for(int i = 0; i < n-1; ++i) {
		int v, u;
		cin >> v >> u;
		g[v].pb(u); g[u].pb(v);
	}

	for(int i = 1; i <= n; ++i) {
		dfs(i);
	}
	cout << ans;
}

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