제출 #419594

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
419594		giorgikob	Zagrade (COI17_zagrade)	C++14	100 / 100	1160 ms	51128 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];
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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 10
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60