oj.uz

Submission #419594

# Submission time Handle Problem Language Result Execution time Memory
419594 2021-06-07T10:01:51 Z giorgikob Zagrade (COI17_zagrade) C++14
100 / 100
 1160 ms 51128 KB 
#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;

const int N = 3e5+5, mod = 1e9+7, K = 20;

int n;
vector<int>gr[N];
int sz[N],fix[N],A[N][2];
ll answer;
char c;

void dfs(int x,int p){

    sz[x] = 1;
    for(auto to : gr[x]){
        if(to == p || fix[to]) continue;
        dfs(to,x);
        sz[x] += sz[to];
    }

}

int get_centroid(int x,int p,int total){

    int mx = total - sz[x];
    int ind = 0;
    for(auto to : gr[x]){
        if(to == p || fix[to]) continue;
        if(mx < sz[to]){
            mx = sz[to];
            ind = to;
        }
    }

    if(mx*2 <= total){
        return x;
    }

    return get_centroid(ind,x,total);
}



void get(int x,int p,int k,int cur,vector<int>&cnt,int mx){

    cur += A[x][k];

    if(mx <= cur){
        cnt[cur]++;
    }

    mx = max(mx,cur);

    for(auto to : gr[x]){
        if(to == p || fix[to]) continue;
        get(to,x,k,cur,cnt,mx);
    }
}

void go(int x,int total){

    if(total == 1) return ;

    dfs(x,0);
    int centroid = get_centroid(x,0,total);

    dfs(centroid,0);

    vector<vector<int>>cnt(2,vector<int>(total+5,0));

    int cur0 = 0,cur1 = 0;

    for(auto to : gr[centroid]){
        if(fix[to]) continue;
        vector<vector<int>>cur_cnt(2,vector<int>(sz[to]+5,0));
        get(to,centroid,0,0,cur_cnt[0],0);
        get(to,centroid,1,0,cur_cnt[1],0);

        for(int k = 0; k <= 1; k++){
            for(int i = 0; i <= sz[to]+1; i++){
                if(cur_cnt[k][i] == 0) continue;
                answer += (ll)cur_cnt[k][i]*(ll)cnt[1-k][i];
                //cout << cur_cnt[k][i]*cnt[1-k][i] << endl;
            }
            //answer += cur_cnt[k][0]*(cnt[0][0]+cnt[1][0]);
            //cout << to << " " << k << endl;
            //cout << cur_cnt[k][0]*(cnt[0][0]+cnt[1][0]) << " 0000" << endl;
        }

        for(int k = 0; k <= 1; k++){
            for(int i = 0; i <= sz[to]+1; i++){
                if(i+A[centroid][k] >= 0)
                cnt[k][i+A[centroid][k]] += cur_cnt[k][i];
            }
        }
    }

    //cout << centroid << " " << answer << endl;
    answer += cnt[0][0] + cnt[1][0];
    fix[centroid] = 1;
    for(auto to : gr[centroid]){
        if(fix[to] == 1) continue;
        go(to,sz[to]);
    }
}

int main(){

    //freopen("a.txt","r",stdin);

    ios::sync_with_stdio(0);

    cin >> n;
    //cout << n << endl;
    for(int i = 1; i <= n; i++){
        cin >> c;
        if(c == '(') A[i][0] = 1, A[i][1] = -1;
        if(c == ')') A[i][0] = -1, A[i][1] = 1;
    }

    for(int i = 1; i < n; i++){
        int x,y;
        cin >> x >> y;
        gr[x].pb(y);
        gr[y].pb(x);
    }

    go(1,n);

    cout << answer << endl;
}

Compilation message

zagrade.cpp: In function 'void go(int, int)':
zagrade.cpp:75:9: warning: unused variable 'cur0' [-Wunused-variable]
   75 |     int cur0 = 0,cur1 = 0;
      |         ^~~~
zagrade.cpp:75:18: warning: unused variable 'cur1' [-Wunused-variable]
   75 |     int cur0 = 0,cur1 = 0;
      |                  ^~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 527 ms 50076 KB Output is correct
2 Correct 521 ms 50268 KB Output is correct
3 Correct 530 ms 50168 KB Output is correct
4 Correct 528 ms 50220 KB Output is correct
5 Correct 506 ms 50124 KB Output is correct
6 Correct 525 ms 50132 KB Output is correct
7 Correct 523 ms 50124 KB Output is correct
8 Correct 547 ms 50156 KB Output is correct
9 Correct 524 ms 50092 KB Output is correct
10 Correct 497 ms 50128 KB Output is correct
11 Correct 498 ms 50152 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7372 KB Output is correct
2 Correct 6 ms 7372 KB Output is correct
3 Correct 6 ms 7424 KB Output is correct
4 Correct 5 ms 7372 KB Output is correct
5 Correct 5 ms 7372 KB Output is correct
6 Correct 6 ms 7436 KB Output is correct
7 Correct 5 ms 7372 KB Output is correct
8 Correct 5 ms 7372 KB Output is correct
9 Correct 6 ms 7372 KB Output is correct
10 Correct 5 ms 7372 KB Output is correct
11 Correct 527 ms 50076 KB Output is correct
12 Correct 521 ms 50268 KB Output is correct
13 Correct 530 ms 50168 KB Output is correct
14 Correct 528 ms 50220 KB Output is correct
15 Correct 506 ms 50124 KB Output is correct
16 Correct 525 ms 50132 KB Output is correct
17 Correct 523 ms 50124 KB Output is correct
18 Correct 547 ms 50156 KB Output is correct
19 Correct 524 ms 50092 KB Output is correct
20 Correct 497 ms 50128 KB Output is correct
21 Correct 498 ms 50152 KB Output is correct
22 Correct 1067 ms 26396 KB Output is correct
23 Correct 1066 ms 27392 KB Output is correct
24 Correct 1160 ms 26864 KB Output is correct
25 Correct 1145 ms 27180 KB Output is correct
26 Correct 578 ms 35164 KB Output is correct
27 Correct 594 ms 31872 KB Output is correct
28 Correct 593 ms 30404 KB Output is correct
29 Correct 499 ms 51128 KB Output is correct
30 Correct 508 ms 51128 KB Output is correct
31 Correct 141 ms 27036 KB Output is correct
32 Correct 504 ms 51080 KB Output is correct