oj.uz

Submission #545326

# Submission time Handle Problem Language Result Execution time Memory
545326 2022-04-04T09:18:18 Z socpite Zagrade (COI17_zagrade) C++17
10 / 100
 3000 ms 73376 KB 
#include<bits/stdc++.h>
using namespace std;

#define f first
#define s second

typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 3e5+5;

vector<pii> up[maxn];
vector<pii> down[maxn];
vector<int> tree[maxn];
int A[maxn];
int sum[maxn], subsz[maxn], col[maxn], vis[maxn], mx[maxn];
vector<int> csum[maxn];

int n;

void predfs(int x, int p){
    subsz[x]=1;
    for(auto v: tree[x]){
        if(v == p || vis[v])continue;
        predfs(v, x);
        subsz[x]+=subsz[v];
    }
}

int gtcen(int x, int p, int tot){
    int re = 0;
    for(auto v: tree[x]){
        if(v == p || vis[v])continue;
        int tmp = gtcen(v, x, tot);
        if(mx[tmp] < mx[re])re = tmp;
        mx[x] = max(mx[x], subsz[v]);
    }
    mx[x]=max(mx[x], tot-subsz[x]);
    if(mx[x] < mx[re])re=x;
    return re;
}

void dfs(int x, int p, int ss, int mn, int mn2, int color, int rr){
    //cout << x << " " << ss << endl;
    if(mn2 >= 0){
        up[ss+A[rr]].push_back({color, rr});
        //cout << "up " << ss+A[rr] << " " << x << " " << rr << endl;
    }
    if(ss == mn && ss <= 0){
        down[-ss].push_back({color, rr});
        //cout << "down " << -ss << " " << x << " " << rr << endl;
    }
    for(auto v: tree[x]){
        if(v == p || vis[v])continue;
        dfs(v, x, ss+A[v], min(ss+A[v], mn), min(0, mn2 + A[v]), color, rr);
    }
}

int build(int x){
    predfs(x, 0);
    x = gtcen(x, 0, subsz[x]);
    vis[x]=1;
    int cc = 0;
    if(A[x] > 0)up[1].push_back({-1, x});
    down[0].push_back({-1, x});
    for(auto v: tree[x]){
        if(vis[v])continue;
        dfs(v, x, A[v], min(0, A[v]), min({0, A[v], A[v]+A[x]}), cc++, x);
    }
    csum[x].assign(cc, 0);
    for(auto v: tree[x]){
        if(!vis[v]){
            int tmp = build(v);
            //cout << x << " " << tmp << endl;
        }
    }
    return x;
}

int main(){
    ll ans = 0;
    cin >> n;
    mx[0]=n;
    for(int i = 1; i <= n; i++){
        char c;
        cin >> c;
        if(c == '(')A[i]=1;
        else A[i]=-1;
    }
    for(int i = 1; i < n; i++){
        int a, b;
        cin >> a >> b;
        tree[a].push_back(b);
        tree[b].push_back(a);
    }
    build(1);
    for(int i = 0; i <= n; i++){
        for(auto v: down[i]){
            sum[v.s]++;
            if(v.f >= 0)csum[v.s][v.f]++;
        }
        for(auto v: up[i]){
            ans += sum[v.s];
            if(v.f >= 0)ans-=csum[v.s][v.f];
        }
        for(auto v: down[i]){
            sum[v.s] = 0;
            if(v.f >= 0)csum[v.s][v.f]=0;
        }
    }
    cout << ans;
}

Compilation message

zagrade.cpp: In function 'int build(int)':
zagrade.cpp:73:17: warning: unused variable 'tmp' [-Wunused-variable]
   73 |             int tmp = build(v);
      |                 ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28628 KB Output is correct
2 Correct 16 ms 28560 KB Output is correct
3 Correct 15 ms 28564 KB Output is correct
4 Correct 15 ms 28564 KB Output is correct
5 Correct 14 ms 28532 KB Output is correct
6 Correct 14 ms 28604 KB Output is correct
7 Correct 15 ms 28636 KB Output is correct
8 Correct 15 ms 28628 KB Output is correct
9 Correct 15 ms 28628 KB Output is correct
10 Correct 18 ms 28500 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3074 ms 73376 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28628 KB Output is correct
2 Correct 16 ms 28560 KB Output is correct
3 Correct 15 ms 28564 KB Output is correct
4 Correct 15 ms 28564 KB Output is correct
5 Correct 14 ms 28532 KB Output is correct
6 Correct 14 ms 28604 KB Output is correct
7 Correct 15 ms 28636 KB Output is correct
8 Correct 15 ms 28628 KB Output is correct
9 Correct 15 ms 28628 KB Output is correct
10 Correct 18 ms 28500 KB Output is correct
11 Execution timed out 3074 ms 73376 KB Time limit exceeded
12 Halted 0 ms 0 KB -