Submission #419529

#	Time	Username	Problem	Language	Result	Execution time	Memory
419529		giorgikob	Zagrade (COI17_zagrade)	C++14	0 / 100	581 ms	50136 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){

    //cout << x << " " << p << " " << up << endl;
    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;
        }
    }
    //cout << mx << endl;

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

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

    dfs(centroid,0);
    //cout << centroid << endl;

    vector<vector<int>>cnt(2,vector<int>(total+5,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);

        //cout << to << endl;
        for(int k = 0; k <= 1; k++){
            for(int i = 0; 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];
            }
        }
        //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