oj.uz

Submission #419593

# Submission time Handle Problem Language Result Execution time Memory
419593 2021-06-07T10:00:53 Z giorgikob Zagrade (COI17_zagrade) C++14
10 / 100
 549 ms 50576 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];
int 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 += cur_cnt[k][i]*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 7372 KB Output is correct
4 Correct 6 ms 7372 KB Output is correct
5 Correct 6 ms 7372 KB Output is correct
6 Correct 6 ms 7372 KB Output is correct
7 Correct 6 ms 7372 KB Output is correct
8 Correct 6 ms 7372 KB Output is correct
9 Correct 6 ms 7372 KB Output is correct
10 Correct 6 ms 7368 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 546 ms 50200 KB Output is correct
2 Correct 549 ms 50384 KB Output is correct
3 Correct 539 ms 50432 KB Output is correct
4 Correct 527 ms 50448 KB Output is correct
5 Correct 526 ms 50576 KB Output is correct
6 Correct 525 ms 50408 KB Output is correct
7 Correct 512 ms 50480 KB Output is correct
8 Correct 539 ms 50448 KB Output is correct
9 Correct 530 ms 50532 KB Output is correct
10 Correct 534 ms 50520 KB Output is correct
11 Incorrect 527 ms 50384 KB Output isn't correct

Subtask #3
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 7372 KB Output is correct
4 Correct 6 ms 7372 KB Output is correct
5 Correct 6 ms 7372 KB Output is correct
6 Correct 6 ms 7372 KB Output is correct
7 Correct 6 ms 7372 KB Output is correct
8 Correct 6 ms 7372 KB Output is correct
9 Correct 6 ms 7372 KB Output is correct
10 Correct 6 ms 7368 KB Output is correct
11 Correct 546 ms 50200 KB Output is correct
12 Correct 549 ms 50384 KB Output is correct
13 Correct 539 ms 50432 KB Output is correct
14 Correct 527 ms 50448 KB Output is correct
15 Correct 526 ms 50576 KB Output is correct
16 Correct 525 ms 50408 KB Output is correct
17 Correct 512 ms 50480 KB Output is correct
18 Correct 539 ms 50448 KB Output is correct
19 Correct 530 ms 50532 KB Output is correct
20 Correct 534 ms 50520 KB Output is correct
21 Incorrect 527 ms 50384 KB Output isn't correct