Submission #419594

#TimeUsernameProblemLanguageResultExecution timeMemory
419594giorgikobZagrade (COI17_zagrade)C++14
100 / 100
1160 ms51128 KiB
#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 (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;
      |                  ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...