oj.uz

Submission #673546

# Submission time Handle Problem Language Result Execution time Memory
673546 2022-12-21T03:31:43 Z tar_palantir Zagrade (COI17_zagrade) C++17
100 / 100
 709 ms 43312 KB 
#include<bits/stdc++.h>
using namespace std;

const int mn=3e5+11;

vector<int>adj[mn];
bool r[mn];// removed?
int sz[mn];

int get_tree_size(int u,int par=-1){
    sz[u]=1;
    for(int v:adj[u])if(v!=par && !r[v])
        sz[u]+=get_tree_size(v,u);
    return sz[u];
}
int get_centroid(int u,int tree_size,int par=-1){
    for(int v:adj[u])if(v!=par && !r[v])
        if(sz[v]*2>tree_size)
            return get_centroid(v,tree_size,u);
    return u;
}
// centroid helper functions

// data processing goes below
inline int get(char x){
    return x==')' ? -1 : 1;
}
char a[mn];

struct holder{
    int cnt[2*mn];
    int elements[3*mn],cc=0;

    inline void emplace(int x){
        elements[++cc]=x;
        cnt[x+mn]++;
    }
    inline void erase(int x){
        if(cnt[x+mn])cnt[x+mn]--;
    }
    inline int get(int x){
        return cnt[x+mn];
    }
    inline void clear(){
        while(cc)erase(elements[cc--]);
    }
}st;

void traverse(int u,int par,int cur,int dip,bool dir){
    if(dip>=0){
        if(dir)st.emplace(cur);
        else st.erase(cur);
    }
    for(int v:adj[u])if(v!=par && !r[v]){
        int nxt=cur+get(a[v]);
        traverse(v,u,nxt,min(dip+get(a[v]),get(a[v])),dir);
    }
}

long long res=0;
void dfs(int u,int par,int cur,int dip){
    if(-cur+dip>=0)res+=st.get(-cur);
    
    for(int v:adj[u])if(v!=par && !r[v]){
        int nxt=cur+get(a[v]);
        dfs(v,u,nxt,min(dip,nxt));
    }
}

void centroid_decompose(int root=1){
    root=get_centroid(root,get_tree_size(root));

    st.clear();
    traverse(root,-1,get(a[root]),get(a[root]),1);

    for(int other:adj[root])if(!r[other]){
        int cur=get(a[root])+get(a[other]);
        int dip=min(get(a[other]),cur);

        traverse(other,root,cur,dip,0);
        dfs(other,root,get(a[other]),get(a[other]));
        traverse(other,root,cur,dip,1);
    }
    res+=st.get(0);

    r[root]=true;
    for(int other:adj[root])if(!r[other])
        centroid_decompose(other);
}

int32_t main()
{
    cin.tie(0)->sync_with_stdio(0);
    #ifdef _TPR_
        freopen("t.inp","r",stdin);
        freopen("t.out","w",stdout);
    #endif
    int n;cin>>n;
    cin>>a+1;

    for(int i=2,u,v;i<=n;i++){
        cin>>u>>v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }

    centroid_decompose();
    return cout<<res,0;
}

Compilation message

zagrade.cpp: In function 'int32_t main()':
zagrade.cpp:99:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   99 |     cin>>a+1;
      |          ~^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 5 ms 7380 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct
4 Correct 5 ms 7368 KB Output is correct
5 Correct 5 ms 7388 KB Output is correct
6 Correct 5 ms 7380 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 4 ms 7392 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 4 ms 7380 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 364 ms 41416 KB Output is correct
2 Correct 358 ms 41456 KB Output is correct
3 Correct 354 ms 41532 KB Output is correct
4 Correct 366 ms 41460 KB Output is correct
5 Correct 353 ms 41432 KB Output is correct
6 Correct 381 ms 42244 KB Output is correct
7 Correct 364 ms 41432 KB Output is correct
8 Correct 405 ms 42156 KB Output is correct
9 Correct 400 ms 41468 KB Output is correct
10 Correct 390 ms 43252 KB Output is correct
11 Correct 367 ms 42632 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 5 ms 7380 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct
4 Correct 5 ms 7368 KB Output is correct
5 Correct 5 ms 7388 KB Output is correct
6 Correct 5 ms 7380 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 4 ms 7392 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 4 ms 7380 KB Output is correct
11 Correct 364 ms 41416 KB Output is correct
12 Correct 358 ms 41456 KB Output is correct
13 Correct 354 ms 41532 KB Output is correct
14 Correct 366 ms 41460 KB Output is correct
15 Correct 353 ms 41432 KB Output is correct
16 Correct 381 ms 42244 KB Output is correct
17 Correct 364 ms 41432 KB Output is correct
18 Correct 405 ms 42156 KB Output is correct
19 Correct 400 ms 41468 KB Output is correct
20 Correct 390 ms 43252 KB Output is correct
21 Correct 367 ms 42632 KB Output is correct
22 Correct 693 ms 23648 KB Output is correct
23 Correct 682 ms 23516 KB Output is correct
24 Correct 664 ms 23492 KB Output is correct
25 Correct 709 ms 23396 KB Output is correct
26 Correct 435 ms 29212 KB Output is correct
27 Correct 449 ms 26232 KB Output is correct
28 Correct 472 ms 25320 KB Output is correct
29 Correct 359 ms 43312 KB Output is correct
30 Correct 352 ms 43220 KB Output is correct
31 Correct 78 ms 23676 KB Output is correct
32 Correct 369 ms 42744 KB Output is correct