oj.uz

Submission #896800

# Submission time Handle Problem Language Result Execution time Memory
896800 2024-01-02T07:40:01 Z dwuy Zagrade (COI17_zagrade) C++14
100 / 100
 644 ms 69456 KB 
/// dwuy: _,\,,,_\,__,\,,_
#include <bits/stdc++.h>

#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) int32_t(s.length())
#define MASK(k)(1LL<<(k))
#define TASK ""
#define int long long

using namespace std;

typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;

const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int MX = 300005;

int n;
string a;
vector<int> G[MX];

void nhap(){
    cin >> n;
    cin >> a; a = ' ' + a;
    for(int i=1; i<n; i++){
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
}

int numC[MX];
bitset<MX> vist = 0;

void calChild(int u){
    vist[u] = 1;
    numC[u] = 1;
    for(int v: G[u]) if(!vist[v]){
        calChild(v);
        numC[u] += numC[v];
    }
    vist[u] = 0;
}

int centroid(int u, int p, const int &half){
    for(int v: G[u]) if(v!=p && !vist[v]){
        if(numC[v] > half) return centroid(v, u, half);
    }
    return u;
}

int p[MX];
int op[MX];
int cl[MX];
int fop[MX];
int fcl[MX];

int c1(char c){
    return c==')'? 1 : -1;
}

int c2(char c){
    return -c1(c);
}

int getmap(int val, const map<int, int> &mp){
    auto itr = mp.find(val);
    return itr == mp.end()? 0 : itr->se;
}

int calc(int u){
    int res = 0;
    {
        map<int, int> mp;
        if(c1(a[u]) < 0) mp[-1]++;
        for(int v: G[u]) if(!vist[v]){
            vector<int> node;
            stack<int> Q;
            Q.push(v);
            p[v] = u;
            op[v] = c1(a[u]) + c1(a[v]);
            cl[v] = c2(a[v]);
            fop[v] = min({0LL, c1(a[u]), op[v]});
            fcl[v] = min(0LL, c2(a[v]));
            while(Q.size()){
                int u = Q.top();
                Q.pop();
                if(cl[u] == fcl[u]) res += getmap(cl[u], mp);
                if(op[u] == fop[u]) node.push_back(u);
                for(int v: G[u]) if(!vist[v] && v!=p[u]){
                    Q.push(v);
                    p[v] = u;
                    op[v] = op[u] + c1(a[v]);
                    cl[v] = cl[u] + c2(a[v]);
                    fop[v] = min(fop[u], op[v]);
                    fcl[v] = min(fcl[u], cl[v]);
                }
            }
            for(int u: node) mp[op[u]]++, res += op[u]==0;
        }
    }
    {
        map<int, int> mp;
        for(int v: G[u]) if(!vist[v]){
            vector<int> node;
            stack<int> Q;
            Q.push(v);
            p[v] = u;
            op[v] = c1(a[u]) + c1(a[v]);
            cl[v] = c2(a[v]);
            fop[v] = min({0LL, c1(a[u]), op[v]});
            fcl[v] = min(0LL, c2(a[v]));
            while(Q.size()){
                int u = Q.top();
                Q.pop();
                if(cl[u] == fcl[u]) node.push_back(u);
                if(op[u] == fop[u]) res += getmap(op[u], mp);
                for(int v: G[u]) if(!vist[v] && v!=p[u]){
                    Q.push(v);
                    p[v] = u;
                    op[v] = op[u] + c1(a[v]);
                    cl[v] = cl[u] + c2(a[v]);
                    fop[v] = min(fop[u], op[v]);
                    fcl[v] = min(fcl[u], cl[v]);
                }
            }
            for(int u: node) mp[cl[u]]++;
        }
    }
    return res;
}

int solve(int u){
    calChild(u);
    u = centroid(u, 0, numC[u]>>1);
    int res = calc(u);
    vist[u] = 1;
    for(int v: G[u]) if(!vist[v]) res += solve(v);
    return res;
}

int32_t main(){
    fastIO;
    //file(TASK);

    nhap();
    cout << solve(1);

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 17240 KB Output is correct
2 Correct 4 ms 17240 KB Output is correct
3 Correct 4 ms 17244 KB Output is correct
4 Correct 4 ms 17244 KB Output is correct
5 Correct 4 ms 17352 KB Output is correct
6 Correct 4 ms 17244 KB Output is correct
7 Correct 4 ms 17244 KB Output is correct
8 Correct 3 ms 17424 KB Output is correct
9 Correct 3 ms 17244 KB Output is correct
10 Correct 3 ms 17452 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 372 ms 58960 KB Output is correct
2 Correct 481 ms 64284 KB Output is correct
3 Correct 349 ms 59052 KB Output is correct
4 Correct 473 ms 63148 KB Output is correct
5 Correct 341 ms 58892 KB Output is correct
6 Correct 400 ms 61056 KB Output is correct
7 Correct 342 ms 58888 KB Output is correct
8 Correct 410 ms 61144 KB Output is correct
9 Correct 341 ms 59000 KB Output is correct
10 Correct 590 ms 69364 KB Output is correct
11 Correct 315 ms 60456 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 17240 KB Output is correct
2 Correct 4 ms 17240 KB Output is correct
3 Correct 4 ms 17244 KB Output is correct
4 Correct 4 ms 17244 KB Output is correct
5 Correct 4 ms 17352 KB Output is correct
6 Correct 4 ms 17244 KB Output is correct
7 Correct 4 ms 17244 KB Output is correct
8 Correct 3 ms 17424 KB Output is correct
9 Correct 3 ms 17244 KB Output is correct
10 Correct 3 ms 17452 KB Output is correct
11 Correct 372 ms 58960 KB Output is correct
12 Correct 481 ms 64284 KB Output is correct
13 Correct 349 ms 59052 KB Output is correct
14 Correct 473 ms 63148 KB Output is correct
15 Correct 341 ms 58892 KB Output is correct
16 Correct 400 ms 61056 KB Output is correct
17 Correct 342 ms 58888 KB Output is correct
18 Correct 410 ms 61144 KB Output is correct
19 Correct 341 ms 59000 KB Output is correct
20 Correct 590 ms 69364 KB Output is correct
21 Correct 315 ms 60456 KB Output is correct
22 Correct 598 ms 38072 KB Output is correct
23 Correct 641 ms 37588 KB Output is correct
24 Correct 644 ms 37564 KB Output is correct
25 Correct 643 ms 37940 KB Output is correct
26 Correct 410 ms 44732 KB Output is correct
27 Correct 417 ms 41408 KB Output is correct
28 Correct 420 ms 39836 KB Output is correct
29 Correct 614 ms 69344 KB Output is correct
30 Correct 592 ms 69456 KB Output is correct
31 Correct 115 ms 39532 KB Output is correct
32 Correct 310 ms 60572 KB Output is correct