oj.uz

답안 #40170

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
40170 2018-01-29T09:45:40 Z krauch Zagrade (COI17_zagrade) C++14
40 / 100
 3000 ms 51308 KB 
/*
 _    _    _______   _    _
| |  / /  |  _____| | |  / /
| | / /   | |       | | / /
| |/ /    | |_____  | |/ /
| |\ \    |  _____| | |\ \
| | \ \   | |       | | \ \
| |  \ \  | |_____  | |  \ \
|_|   \_\ |_______| |_|   \_\

*/
#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef double ld;
typedef pair <int, int> PII;
typedef pair <ll, ll> PLL;
typedef pair < ll, int > PLI;


#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define right(x) x << 1 | 1
#define left(x) x << 1
#define forn(x, a, b) for (int x = a; x <= b; ++x)
#define for1(x, a, b) for (int x = a; x >= b; --x)
#define mkp make_pair
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define y1 kekekek

#define fname ""

const ll ool = 1e18 + 9;
const int oo = 1e9 + 9, base = 1e9 + 7;
const ld eps = 1e-7;
const int N = 5e5 + 6;

int n, ROOT = 0,cnt[N], tmp[N];
bool u[N];
char a[N];
vector < int > g[N];
ll ans;

int getsz(int v, int par, int sz) {
    int res = 1;
    bool ok = 1;
    for (auto to : g[v]) {
        if (to == par || u[to]) continue;
        int val = getsz(to, v, sz);
        if (val > sz / 2) ok = 0;
        res += val;
    }
    if (sz - res > sz / 2) ok = 0;
    if (ok) ROOT = v;
    return res;
}

void dfs(int v, int par, int bal, int mn) {
    bal += (a[v] == ')' ? -1 : 1);
    mn = min(mn, bal);
    if (bal == mn) cnt[-bal]++;
    for (auto to : g[v]) {
        if (to == par || u[to]) continue;
        dfs(to, v, bal, mn);
    }
}

void calc(int v, int par, int bal, int mn, int bal2, int mx, int kek) {
    bal += (a[v] == ')' ? -1 : 1);
    bal2 += (a[v] == ')' ? -1 : 1);
    mn = min(mn, bal);
    mx = max(mx, bal2);
    if (bal == mn) cnt[-bal] -= kek;
    if (bal2 == mx) tmp[bal2] += kek;
    for (auto to : g[v]) {
        if (to == par || u[to]) continue;
        calc(to, v, bal, mn, bal2, mx, kek);
    }
}

void build(int v, int sz) {
    getsz(v, 0, sz);
    int root = ROOT;
    //cerr << root << " " << sz << "\n";
    forn(i, 0, sz) cnt[i] = 0;
    dfs(root, 0, 0, 0);
    for (auto to : g[root]) {
        if (u[to]) continue;
        calc(to, root, (a[root] == ')' ? -1 : 1), (a[root] == ')' ? -1 : 1), 0, 0, 1);
        forn(i, 0, sz) {
            ans += 1ll * cnt[i] * tmp[i];
            //cerr << root << " " << to << " " << i << " " << cnt[i] << " " << tmp[i] << "\n";
        }
        calc(to, root, (a[root] == ')' ? -1 : 1), (a[root] == ')' ? -1 : 1), 0, 0, -1);
    }
    ans += cnt[0];
    //cerr << "kek " << cnt[0] << "\n";

    u[root] = 1;
    vector < int > vec;
    for (auto to : g[root]) {
        vec.eb(0);
        if (u[to]) continue;
        vec.back() = getsz(to, root, sz);
    }
    forn(i, 0, sz(g[root]) - 1) {
        if (u[g[root][i]]) continue;
        build(g[root][i], vec[i]);
    }
}

int main() {
	//ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

	#ifdef krauch
        freopen("input.txt", "r", stdin);
    #else
        //freopen(fname".in", "r", stdin);
        //freopen(fname".out", "w", stdout);
    #endif

    cin >> n;
    forn(i, 1, n) {
        cin >> a[i];
    }

    forn(i, 1, n - 1) {
        int x, y;
        cin >> x >> y;
        g[x].eb(y);
        g[y].eb(x);
    }

    build(1, n);

    cout << ans << "\n";

	return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 18620 KB Output is correct
2 Correct 5 ms 18620 KB Output is correct
3 Correct 4 ms 18620 KB Output is correct
4 Correct 4 ms 18620 KB Output is correct
5 Correct 5 ms 18620 KB Output is correct
6 Correct 6 ms 18620 KB Output is correct
7 Correct 3 ms 18620 KB Output is correct
8 Correct 2 ms 18620 KB Output is correct
9 Correct 11 ms 18620 KB Output is correct
10 Correct 2 ms 18620 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 781 ms 51308 KB Output is correct
2 Correct 721 ms 51300 KB Output is correct
3 Correct 774 ms 51304 KB Output is correct
4 Correct 758 ms 51308 KB Output is correct
5 Correct 777 ms 51308 KB Output is correct
6 Correct 701 ms 51300 KB Output is correct
7 Correct 756 ms 51304 KB Output is correct
8 Correct 756 ms 51304 KB Output is correct
9 Correct 853 ms 51308 KB Output is correct
10 Correct 754 ms 51308 KB Output is correct
11 Correct 694 ms 51308 KB Output is correct

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 18620 KB Output is correct
2 Correct 5 ms 18620 KB Output is correct
3 Correct 4 ms 18620 KB Output is correct
4 Correct 4 ms 18620 KB Output is correct
5 Correct 5 ms 18620 KB Output is correct
6 Correct 6 ms 18620 KB Output is correct
7 Correct 3 ms 18620 KB Output is correct
8 Correct 2 ms 18620 KB Output is correct
9 Correct 11 ms 18620 KB Output is correct
10 Correct 2 ms 18620 KB Output is correct
11 Correct 781 ms 51308 KB Output is correct
12 Correct 721 ms 51300 KB Output is correct
13 Correct 774 ms 51304 KB Output is correct
14 Correct 758 ms 51308 KB Output is correct
15 Correct 777 ms 51308 KB Output is correct
16 Correct 701 ms 51300 KB Output is correct
17 Correct 756 ms 51304 KB Output is correct
18 Correct 756 ms 51304 KB Output is correct
19 Correct 853 ms 51308 KB Output is correct
20 Correct 754 ms 51308 KB Output is correct
21 Correct 694 ms 51308 KB Output is correct
22 Correct 1363 ms 28388 KB Output is correct
23 Correct 1444 ms 28388 KB Output is correct
24 Correct 1450 ms 28388 KB Output is correct
25 Correct 1480 ms 28388 KB Output is correct
26 Correct 902 ms 35676 KB Output is correct
27 Correct 915 ms 32252 KB Output is correct
28 Correct 921 ms 30920 KB Output is correct
29 Correct 666 ms 51304 KB Output is correct
30 Correct 759 ms 51300 KB Output is correct
31 Execution timed out 3000 ms 30104 KB Execution timed out
32 Halted 0 ms 0 KB -