oj.uz

Submission #844849

# Submission time Handle Problem Language Result Execution time Memory
844849 2023-09-06T04:04:08 Z Cookie Zagrade (COI17_zagrade) C++14
100 / 100
 789 ms 49748 KB 
#include<bits/stdc++.h>
#define ll long long
#define vt vector
#define pb push_back
#define pii pair<int, int>
#define sz(v) (int)v.size()
using namespace std;
const ll base = 107, mod = 1e9 + 7;
const int mxn = 3e5 + 5, inf = 1e9, sq = 400;
int n;
int val[mxn + 1], sz[mxn + 1];
vt<int>adj[mxn + 1];
map<int, int>cnt;
bool vis[mxn + 1];
int dfs(int s, int pre){
    sz[s] = 1;
    for(auto i: adj[s]){
        if(i != pre && !vis[i]){
            sz[s] += dfs(i, s);
        }
    }
    return(sz[s]);
}
int centroid(int s, int pre, int need){
    for(auto i: adj[s]){
        if(i != pre && !vis[i]){
            if(sz[i] * 2 > need)return(centroid(i, s, need));
        }
    }
    return(s);
}
ll ans = 0;
void dfs2(int s, int pre, int pref, int mxpref, int mnpref, bool add){
    pref += val[s]; mxpref = max(mxpref, pref); mnpref = min(mnpref, pref);
    if(add){
        if(pref - mxpref >= 0){
            cnt[pref]++; 
        }
    }else{
        if(pref - mnpref <= 0){
            assert(pref == mnpref);
            ans += 1LL * cnt[-mnpref];
        }
    }
    for(auto i: adj[s]){
        if(i != pre && !vis[i]){
            dfs2(i, s, pref, mxpref, mnpref, add);
        }
    }
}

void build(int s){
    int c = centroid(s, -1, dfs(s, -1));
    vis[c] = 1;
    cnt.clear(); 
   
    if(val[c] != -1)cnt[val[c]]++;
    for(auto i: adj[c]){
        if(!vis[i]){
            dfs2(i, c, 0, 0, 0, 0);
            dfs2(i, c, val[c], max(0, val[c]), min(0, val[c]), 1);
        }
    }
    ans += 1LL * cnt[0];
    cnt.clear();
    reverse(adj[c].begin(), adj[c].end());
    for(auto i: adj[c]){
        if(!vis[i]){
            dfs2(i, c, 0, 0, 0, 0);
            dfs2(i, c, val[c], max(0, val[c]), min(0, val[c]), 1);
        }
    }
    for(auto i: adj[c]){
        if(!vis[i]){
            build(i);
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++){
        char c; cin >> c;
        if(c == '(')val[i] = 1;
        else val[i] = -1;
    }
    for(int i = 1; i < n; i++){
        int u, v; cin >> u >> v;
        adj[u].pb(v); adj[v].pb(u);
    }
    build(1);
    cout << ans;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 3 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8680 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 2 ms 8540 KB Output is correct
9 Correct 2 ms 8540 KB Output is correct
10 Correct 2 ms 8540 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 42484 KB Output is correct
2 Correct 619 ms 45652 KB Output is correct
3 Correct 413 ms 42432 KB Output is correct
4 Correct 564 ms 44768 KB Output is correct
5 Correct 420 ms 42324 KB Output is correct
6 Correct 475 ms 43336 KB Output is correct
7 Correct 400 ms 42644 KB Output is correct
8 Correct 459 ms 43248 KB Output is correct
9 Correct 396 ms 42432 KB Output is correct
10 Correct 770 ms 49672 KB Output is correct
11 Correct 318 ms 42320 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 3 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8680 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 2 ms 8540 KB Output is correct
9 Correct 2 ms 8540 KB Output is correct
10 Correct 2 ms 8540 KB Output is correct
11 Correct 406 ms 42484 KB Output is correct
12 Correct 619 ms 45652 KB Output is correct
13 Correct 413 ms 42432 KB Output is correct
14 Correct 564 ms 44768 KB Output is correct
15 Correct 420 ms 42324 KB Output is correct
16 Correct 475 ms 43336 KB Output is correct
17 Correct 400 ms 42644 KB Output is correct
18 Correct 459 ms 43248 KB Output is correct
19 Correct 396 ms 42432 KB Output is correct
20 Correct 770 ms 49672 KB Output is correct
21 Correct 318 ms 42320 KB Output is correct
22 Correct 511 ms 23880 KB Output is correct
23 Correct 503 ms 23888 KB Output is correct
24 Correct 501 ms 23632 KB Output is correct
25 Correct 572 ms 23892 KB Output is correct
26 Correct 470 ms 30036 KB Output is correct
27 Correct 468 ms 27216 KB Output is correct
28 Correct 474 ms 26192 KB Output is correct
29 Correct 777 ms 49748 KB Output is correct
30 Correct 789 ms 49748 KB Output is correct
31 Correct 82 ms 23372 KB Output is correct
32 Correct 339 ms 42444 KB Output is correct