oj.uz

Submission #896802

# Submission time Handle Problem Language Result Execution time Memory
896802 2024-01-02T07:44:06 Z dwuy Zagrade (COI17_zagrade) C++14
100 / 100
 552 ms 74760 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> mp1, mp2;
    if(c1(a[u]) < 0) mp1[-1]++;
    for(int v: G[u]) if(!vist[v]){
        vector<int> node1, node2;
        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], mp1);
                node2.push_back(u);
            }
            if(op[u] == fop[u]){
                res += getmap(op[u], mp2);
                node1.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: node1) mp1[op[u]]++, res += op[u]==0;
        for(int u: node2) mp2[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 3 ms 17244 KB Output is correct
3 Correct 3 ms 17412 KB Output is correct
4 Correct 4 ms 17244 KB Output is correct
5 Correct 3 ms 17244 KB Output is correct
6 Correct 3 ms 17244 KB Output is correct
7 Correct 5 ms 17244 KB Output is correct
8 Correct 3 ms 17244 KB Output is correct
9 Correct 3 ms 17244 KB Output is correct
10 Correct 3 ms 17244 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 54716 KB Output is correct
2 Correct 395 ms 60184 KB Output is correct
3 Correct 270 ms 54716 KB Output is correct
4 Correct 370 ms 59020 KB Output is correct
5 Correct 275 ms 54832 KB Output is correct
6 Correct 307 ms 56844 KB Output is correct
7 Correct 277 ms 54860 KB Output is correct
8 Correct 309 ms 56704 KB Output is correct
9 Correct 277 ms 54716 KB Output is correct
10 Correct 540 ms 74668 KB Output is correct
11 Correct 243 ms 57120 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 3 ms 17244 KB Output is correct
3 Correct 3 ms 17412 KB Output is correct
4 Correct 4 ms 17244 KB Output is correct
5 Correct 3 ms 17244 KB Output is correct
6 Correct 3 ms 17244 KB Output is correct
7 Correct 5 ms 17244 KB Output is correct
8 Correct 3 ms 17244 KB Output is correct
9 Correct 3 ms 17244 KB Output is correct
10 Correct 3 ms 17244 KB Output is correct
11 Correct 276 ms 54716 KB Output is correct
12 Correct 395 ms 60184 KB Output is correct
13 Correct 270 ms 54716 KB Output is correct
14 Correct 370 ms 59020 KB Output is correct
15 Correct 275 ms 54832 KB Output is correct
16 Correct 307 ms 56844 KB Output is correct
17 Correct 277 ms 54860 KB Output is correct
18 Correct 309 ms 56704 KB Output is correct
19 Correct 277 ms 54716 KB Output is correct
20 Correct 540 ms 74668 KB Output is correct
21 Correct 243 ms 57120 KB Output is correct
22 Correct 465 ms 33856 KB Output is correct
23 Correct 481 ms 33724 KB Output is correct
24 Correct 474 ms 33888 KB Output is correct
25 Correct 489 ms 33980 KB Output is correct
26 Correct 310 ms 40636 KB Output is correct
27 Correct 308 ms 37060 KB Output is correct
28 Correct 318 ms 35776 KB Output is correct
29 Correct 552 ms 74660 KB Output is correct
30 Correct 543 ms 74760 KB Output is correct
31 Correct 77 ms 36780 KB Output is correct
32 Correct 241 ms 57120 KB Output is correct