Submission #96141

#	Time	Username	Problem	Language	Result	Execution time	Memory
96141		igzi	Zagrade (COI17_zagrade)	C++17	100 / 100	1162 ms	45448 KiB

zagrade

#include <bits/stdc++.h>
#define maxN 300005

using namespace std;

vector <int> adj[maxN];
long long ans=0,cnt[maxN],s[maxN],n,x,y,i;
bool mar[maxN];
string t;

void dfs0(int n,int par){
s[n]=1;
for(int i=0;i<adj[n].size();i++){
int x=adj[n][i];
if(x==par || mar[x]) continue;
dfs0(x,n);
s[n]+=s[x];
}
}

int cen(int n,int par,int S){
for(int i=0;i<adj[n].size();i++){
int x=adj[n][i];
if(x==par || mar[x]) continue;
if(s[x]>S/2) return cen(x,n,S);
}
return n;
}

void dfs1(int n,int par,int a,int m){
if(t[n]==')') a++;
else a--;
m=max(m,a);
if(a>=0 && a==m) ans+=cnt[a];
for(int i=0;i<adj[n].size();i++){
int x=adj[n][i];
if(x==par || mar[x]) continue;
dfs1(x,n,a,m);
}
}

void dfs2(int n,int par,int a,int m){
if(t[n]=='(') a++;
else a--;
m=max(m,a);
if(m==a) cnt[a]++;
for(int i=0;i<adj[n].size();i++){
int x=adj[n][i];
if(x==par || mar[x]) continue;
dfs2(x,n,a,m);
}
}

void decompose(int n){
int tmp=-1;
dfs0(n,-1);
int c=cen(n,-1,s[n]);
mar[c]=true;
for(int i=0;i<=s[n];i++){
cnt[i]=0;
}
if(t[c]=='(') {cnt[1]++; tmp+=2;}
for(int i=0;i<adj[c].size();i++){
int x=adj[c][i];
if(mar[x]) continue;
dfs1(x,c,0,0);
dfs2(x,c,tmp,max(0,tmp));
}
for(int i=0;i<adj[c].size();i++){
int x=adj[c][i];
if(mar[x]) continue;
decompose(x);
}
}

int main(){
    std::ios_base::sync_with_stdio(false);
    cin>>n;
    cin>>t;
    for(i=1;i<n;i++){
        cin>>x>>y;
        x--;
        y--;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    decompose(0);
    for(i=0;i<n;i++){
        if(t[i]=='(') t[i]=')';
        else t[i]='(';
        mar[i]=false;
    }
    decompose(0);
    cout<<ans<<endl;
    return 0;
}

Compilation message (stderr)

zagrade.cpp: In function 'void dfs0(int, int)':
zagrade.cpp:13:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(int i=0;i<adj[n].size();i++){
             ~^~~~~~~~~~~~~~
zagrade.cpp: In function 'int cen(int, int, int)':
zagrade.cpp:22:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(int i=0;i<adj[n].size();i++){
             ~^~~~~~~~~~~~~~
zagrade.cpp: In function 'void dfs1(int, int, int, int)':
zagrade.cpp:35:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(int i=0;i<adj[n].size();i++){
             ~^~~~~~~~~~~~~~
zagrade.cpp: In function 'void dfs2(int, int, int, int)':
zagrade.cpp:47:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(int i=0;i<adj[n].size();i++){
             ~^~~~~~~~~~~~~~
zagrade.cpp: In function 'void decompose(int)':
zagrade.cpp:63:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(int i=0;i<adj[c].size();i++){
             ~^~~~~~~~~~~~~~
zagrade.cpp:69:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(int i=0;i<adj[c].size();i++){
             ~^~~~~~~~~~~~~~

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