Submission #419541

#	Time	Username	Problem	Language	Result	Execution time	Memory
419541		giorgikob	Zagrade (COI17_zagrade)	C++14	0 / 100	614 ms	50172 KiB

zagrade

#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(cur >= 0 && A[x][k] == 1 && mx <= cur){
        cnt[cur]++;
    }

    mx = max(mx,A[x][k]);

    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));
    //cnt[0][0] = 1;
    //cnt[1][0] = 1;

    int cur0 = A[centroid][0];
    int cur1 = A[centroid][1];
    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,cur0,cur_cnt[0],max(0,cur0));
        get(to,centroid,1,cur1,cur_cnt[1],max(0,cur1));

        //cout << to << endl;
        for(int k = 0; k <= 1; k++){
            for(int i = 1; i <= sz[to]+1; i++){
                if(cur_cnt[k][i] == 0) continue;
                //cout << cur_cnt[k][i] << " " << k << " " << i << endl;
                answer += cur_cnt[k][i]*cnt[1-k][i];
            }
            answer += cur_cnt[k][0];
            answer += cur_cnt[k][0]*(cnt[1][0]+cnt[0][0]);
        }
        //cout << 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];
            }
        }
    }

    //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(){

    ios::sync_with_stdio(0);

    cin >> n;
    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;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 30
• Subtask 3: 0 / 60