oj.uz

Submission #894937

# Submission time Handle Problem Language Result Execution time Memory
894937 2023-12-29T09:07:35 Z vjudge1 Zagrade (COI17_zagrade) C++11
40 / 100
 177 ms 40208 KB 
#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
using namespace std;
#define F first
#define S second
typedef long long ll;
#define pii pair <int, int>
#define pll pair <ll, ll>
typedef long double ld;
const ll N = 3 * 1e5 + 10;
const ll mod = 1e9 + 7;

ll um(ll a, ll b){
	return ((1LL * a * b) % mod + mod) % mod;
}
ll subr(ll a, ll b){
	return ((1LL * a - b) % mod + mod) % mod;
}
ll add(ll a, ll b){
	return (1LL * a + b) % mod;
}
ll binpow(ll x, ll step){
	ll res = 1LL;
	while(step){
		if(step & 1) res = um(res, x);
		x = um(x, x);
		step /= 2;
	}
	return res;
}
vector <ll> q[N];
bool arr[N];
ll ans, n;
void over(){
	ll cur = 0, mx = 0;
	map<ll, ll> mp;
	for(ll i = 1; i <= n; i++){
		if(arr[i]){
			mp[cur]++;
			cur--;
		} else{
			mp[cur] = 0;
			cur++;
			ans += mp[cur];
		}
	}
	cur = mx = 0;
	map<ll, ll> mp1;
	for(ll i = n; i >= 1; i--){
		if(arr[i]){
			mp1[cur]++;
			cur--;
		} else{
			mp1[cur] = 0;
			cur++;
			ans += mp1[cur];
		}
	}
}
void dfs(ll v, ll p, ll cnt){
	if(cnt == 0) ans++;
	for(auto u : q[v]){
		if(u == p) continue;
		if(arr[u]) dfs(u, v, cnt + 1);
		else{
			if(cnt > 0) dfs(u, v, cnt - 1);
		}
	}
}
void subtask1(){
	for(ll i = 1; i <= n; i++){
		if(arr[i] == true) dfs(i, -1, 1);
	}
}
int main() {
	ios::sync_with_stdio(false);
  	cin.tie(NULL);
	string s;
  	cin >> n >> s;
  	for(ll i = 0; i < n; i++){
  		if(s[i] == '(') arr[i + 1] = true;
  	}
  	for(ll i = 0, a, b; i < n - 1; i++){
  		cin >> a >> b;
  		q[a].pb(b);
  		q[b].pb(a);
  	}
  	if(n <= 1000) subtask1();
  	else over();
  	cout << ans;
  	
  	// subtask1();
  	// cout << ans << endl;
  	// ans = 0;
  	// over();
  	// cout << ans;
  return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7516 KB Output is correct
2 Correct 5 ms 7516 KB Output is correct
3 Correct 4 ms 7608 KB Output is correct
4 Correct 3 ms 7516 KB Output is correct
5 Correct 4 ms 7768 KB Output is correct
6 Correct 5 ms 7516 KB Output is correct
7 Correct 5 ms 7516 KB Output is correct
8 Correct 3 ms 7640 KB Output is correct
9 Correct 6 ms 7516 KB Output is correct
10 Correct 4 ms 7656 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 21044 KB Output is correct
2 Correct 158 ms 36580 KB Output is correct
3 Correct 78 ms 21648 KB Output is correct
4 Correct 157 ms 32792 KB Output is correct
5 Correct 90 ms 21996 KB Output is correct
6 Correct 125 ms 26852 KB Output is correct
7 Correct 80 ms 21596 KB Output is correct
8 Correct 134 ms 26724 KB Output is correct
9 Correct 95 ms 21628 KB Output is correct
10 Correct 166 ms 40208 KB Output is correct
11 Correct 68 ms 21652 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7516 KB Output is correct
2 Correct 5 ms 7516 KB Output is correct
3 Correct 4 ms 7608 KB Output is correct
4 Correct 3 ms 7516 KB Output is correct
5 Correct 4 ms 7768 KB Output is correct
6 Correct 5 ms 7516 KB Output is correct
7 Correct 5 ms 7516 KB Output is correct
8 Correct 3 ms 7640 KB Output is correct
9 Correct 6 ms 7516 KB Output is correct
10 Correct 4 ms 7656 KB Output is correct
11 Correct 82 ms 21044 KB Output is correct
12 Correct 158 ms 36580 KB Output is correct
13 Correct 78 ms 21648 KB Output is correct
14 Correct 157 ms 32792 KB Output is correct
15 Correct 90 ms 21996 KB Output is correct
16 Correct 125 ms 26852 KB Output is correct
17 Correct 80 ms 21596 KB Output is correct
18 Correct 134 ms 26724 KB Output is correct
19 Correct 95 ms 21628 KB Output is correct
20 Correct 166 ms 40208 KB Output is correct
21 Correct 68 ms 21652 KB Output is correct
22 Incorrect 177 ms 27876 KB Output isn't correct
23 Halted 0 ms 0 KB -