oj.uz

Submission #232815

# Submission time Handle Problem Language Result Execution time Memory
232815 2020-05-18T09:51:04 Z shayan_p Zagrade (COI17_zagrade) C++14
100 / 100
 1754 ms 47756 KB 
// Never let them see you bleed...

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 3e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;

vector<int> v[maxn];

int a[maxn], SZ[maxn];
bool mark[maxn];

void dfsSZ(int u, int par = -1){
    SZ[u] = 1;
    for(int y : v[u]){
	if(!mark[y] && par != y)
	    dfsSZ(y, u), SZ[u]+= SZ[y];
    }
}
int dfsCenter(int u, int N, int par = -1){
    for(int y : v[u]){
	if(!mark[y] && par != y && SZ[y] > N)
	    return dfsCenter(y, N, u);	    
    }
    return u;
}

int cnt[2 * maxn];

int val[maxn], pr[maxn], up[maxn];
ll ANS;

void calc(int u, int bad, int task, int sum, int par = 0){
    pr[u] = par;
    val[u] = val[par] + a[u];
    up[u] = (a[u] == bad ? u : up[pr[up[par]]]);
    if(task == 0)	    
	cnt[maxn + val[u]] = 0;
    if(up[u] == 0){
	if(task == 1)
	    cnt[maxn + val[u]]++;
	if(task == -1)
	    ANS+= cnt[maxn + sum - val[u]];
    }
    for(int y : v[u])
	if(!mark[y] && par != y)
	    calc(y, bad, task, sum, u);	
}

void solve(int r){
    dfsSZ(r);
    r = dfsCenter(r, SZ[r]/2);
    mark[r] = 1;
    if(a[r] == 1)
	cnt[maxn]++;    
    for(int u : v[r]){
	if(mark[u])
	    continue;
	calc(u, 1, -1, -a[r]);
	calc(u, -1, 1, 0);	
    }
    if(a[r] == 1)
	cnt[maxn] = 0;
    for(int u : v[r]){
	if(mark[u])
	    continue;
	calc(u, -1, 0, 0);
    }

    if(a[r] == -1)
	cnt[maxn]++;
    for(int u : v[r]){
	if(mark[u])
	    continue;
	calc(u, -1, -1, -a[r]);
	calc(u, 1, 1, 0);
    }
    if(a[r] == -1)
	cnt[maxn] = 0;    
    for(int u : v[r]){
	if(mark[u])
	    continue;
	calc(u, 1, 0, 0);
    }

    for(int u : v[r]){
	if(!mark[u])
	    solve(u);
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();

    int n;
    cin >> n;
    string s;
    cin >> s;	
    for(int i = 0; i < n; i++){
	a[i+1] = (s[i] == '(' ? 1 : -1);
    }
    for(int i = 0; i < n-1; i++){
	int a, b;
	cin >> a >> b;
	v[a].PB(b);
	v[b].PB(a);
    }
    solve(1);
    return cout << ANS << endl, 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7424 KB Output is correct
2 Correct 9 ms 7424 KB Output is correct
3 Correct 10 ms 7424 KB Output is correct
4 Correct 10 ms 7424 KB Output is correct
5 Correct 10 ms 7552 KB Output is correct
6 Correct 10 ms 7424 KB Output is correct
7 Correct 9 ms 7424 KB Output is correct
8 Correct 10 ms 7552 KB Output is correct
9 Correct 10 ms 7424 KB Output is correct
10 Correct 9 ms 7424 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 697 ms 46348 KB Output is correct
2 Correct 673 ms 46628 KB Output is correct
3 Correct 694 ms 46476 KB Output is correct
4 Correct 688 ms 46480 KB Output is correct
5 Correct 699 ms 46352 KB Output is correct
6 Correct 695 ms 46516 KB Output is correct
7 Correct 693 ms 46344 KB Output is correct
8 Correct 687 ms 46344 KB Output is correct
9 Correct 689 ms 46348 KB Output is correct
10 Correct 580 ms 47496 KB Output is correct
11 Correct 588 ms 46220 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7424 KB Output is correct
2 Correct 9 ms 7424 KB Output is correct
3 Correct 10 ms 7424 KB Output is correct
4 Correct 10 ms 7424 KB Output is correct
5 Correct 10 ms 7552 KB Output is correct
6 Correct 10 ms 7424 KB Output is correct
7 Correct 9 ms 7424 KB Output is correct
8 Correct 10 ms 7552 KB Output is correct
9 Correct 10 ms 7424 KB Output is correct
10 Correct 9 ms 7424 KB Output is correct
11 Correct 697 ms 46348 KB Output is correct
12 Correct 673 ms 46628 KB Output is correct
13 Correct 694 ms 46476 KB Output is correct
14 Correct 688 ms 46480 KB Output is correct
15 Correct 699 ms 46352 KB Output is correct
16 Correct 695 ms 46516 KB Output is correct
17 Correct 693 ms 46344 KB Output is correct
18 Correct 687 ms 46344 KB Output is correct
19 Correct 689 ms 46348 KB Output is correct
20 Correct 580 ms 47496 KB Output is correct
21 Correct 588 ms 46220 KB Output is correct
22 Correct 1747 ms 27760 KB Output is correct
23 Correct 1724 ms 27660 KB Output is correct
24 Correct 1742 ms 27788 KB Output is correct
25 Correct 1754 ms 27700 KB Output is correct
26 Correct 834 ms 33804 KB Output is correct
27 Correct 835 ms 30860 KB Output is correct
28 Correct 853 ms 29900 KB Output is correct
29 Correct 571 ms 47500 KB Output is correct
30 Correct 589 ms 47756 KB Output is correct
31 Correct 129 ms 27268 KB Output is correct
32 Correct 591 ms 46496 KB Output is correct