oj.uz

Submission #931601

# Submission time Handle Problem Language Result Execution time Memory
931601 2024-02-22T06:33:14 Z vjudge1 Zagrade (COI17_zagrade) C++17
10 / 100
 34 ms 12260 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2652 KB Output is correct
2 Correct 33 ms 2652 KB Output is correct
3 Correct 27 ms 2844 KB Output is correct
4 Correct 31 ms 2648 KB Output is correct
5 Correct 27 ms 2904 KB Output is correct
6 Correct 29 ms 2652 KB Output is correct
7 Correct 34 ms 2652 KB Output is correct
8 Correct 24 ms 2648 KB Output is correct
9 Correct 28 ms 2844 KB Output is correct
10 Correct 12 ms 2848 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 24 ms 12260 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2652 KB Output is correct
2 Correct 33 ms 2652 KB Output is correct
3 Correct 27 ms 2844 KB Output is correct
4 Correct 31 ms 2648 KB Output is correct
5 Correct 27 ms 2904 KB Output is correct
6 Correct 29 ms 2652 KB Output is correct
7 Correct 34 ms 2652 KB Output is correct
8 Correct 24 ms 2648 KB Output is correct
9 Correct 28 ms 2844 KB Output is correct
10 Correct 12 ms 2848 KB Output is correct
11 Runtime error 24 ms 12260 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -