oj.uz

Submission #96141

# Submission time Handle Problem Language Result Execution time Memory
96141 2019-02-06T12:29:25 Z igzi Zagrade (COI17_zagrade) C++17
100 / 100
 1162 ms 45448 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7544 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 7 ms 7420 KB Output is correct
4 Correct 7 ms 7416 KB Output is correct
5 Correct 7 ms 7420 KB Output is correct
6 Correct 8 ms 7416 KB Output is correct
7 Correct 7 ms 7416 KB Output is correct
8 Correct 7 ms 7416 KB Output is correct
9 Correct 8 ms 7416 KB Output is correct
10 Correct 9 ms 7544 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 582 ms 45212 KB Output is correct
2 Correct 544 ms 45064 KB Output is correct
3 Correct 633 ms 45320 KB Output is correct
4 Correct 538 ms 45124 KB Output is correct
5 Correct 571 ms 45212 KB Output is correct
6 Correct 618 ms 45060 KB Output is correct
7 Correct 568 ms 45216 KB Output is correct
8 Correct 576 ms 45240 KB Output is correct
9 Correct 552 ms 45448 KB Output is correct
10 Correct 485 ms 45196 KB Output is correct
11 Correct 495 ms 45196 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7544 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 7 ms 7420 KB Output is correct
4 Correct 7 ms 7416 KB Output is correct
5 Correct 7 ms 7420 KB Output is correct
6 Correct 8 ms 7416 KB Output is correct
7 Correct 7 ms 7416 KB Output is correct
8 Correct 7 ms 7416 KB Output is correct
9 Correct 8 ms 7416 KB Output is correct
10 Correct 9 ms 7544 KB Output is correct
11 Correct 582 ms 45212 KB Output is correct
12 Correct 544 ms 45064 KB Output is correct
13 Correct 633 ms 45320 KB Output is correct
14 Correct 538 ms 45124 KB Output is correct
15 Correct 571 ms 45212 KB Output is correct
16 Correct 618 ms 45060 KB Output is correct
17 Correct 568 ms 45216 KB Output is correct
18 Correct 576 ms 45240 KB Output is correct
19 Correct 552 ms 45448 KB Output is correct
20 Correct 485 ms 45196 KB Output is correct
21 Correct 495 ms 45196 KB Output is correct
22 Correct 1092 ms 26540 KB Output is correct
23 Correct 1037 ms 26504 KB Output is correct
24 Correct 1042 ms 26380 KB Output is correct
25 Correct 1162 ms 26508 KB Output is correct
26 Correct 713 ms 32668 KB Output is correct
27 Correct 711 ms 30000 KB Output is correct
28 Correct 708 ms 28680 KB Output is correct
29 Correct 483 ms 45068 KB Output is correct
30 Correct 487 ms 45188 KB Output is correct
31 Correct 106 ms 26116 KB Output is correct
32 Correct 487 ms 45196 KB Output is correct