oj.uz

답안 #40171

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
40171 2018-01-29T09:49:09 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

    scanf("%d\n", &n);
    forn(i, 1, n) {
        scanf("%c", a + i);
    }
    scanf("\n");

    forn(i, 1, n - 1) {
        int x, y;
        scanf("%d %d\n", &x, &y);
        g[x].eb(y);
        g[y].eb(x);
    }

    build(1, n);

    cout << ans << "\n";

	return 0;
}

Compilation message

zagrade.cpp: In function 'int main()':
zagrade.cpp:128:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d\n", &n);
                      ^
zagrade.cpp:130:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%c", a + i);
                           ^
zagrade.cpp:132:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("\n");
                ^
zagrade.cpp:136:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d\n", &x, &y);
                                 ^

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 18620 KB Output is correct
2 Correct 3 ms 18620 KB Output is correct
3 Correct 6 ms 18620 KB Output is correct
4 Correct 4 ms 18620 KB Output is correct
5 Correct 2 ms 18620 KB Output is correct
6 Correct 0 ms 18620 KB Output is correct
7 Correct 0 ms 18620 KB Output is correct
8 Correct 9 ms 18620 KB Output is correct
9 Correct 6 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 565 ms 51308 KB Output is correct
2 Correct 602 ms 51304 KB Output is correct
3 Correct 604 ms 51304 KB Output is correct
4 Correct 636 ms 51304 KB Output is correct
5 Correct 600 ms 51308 KB Output is correct
6 Correct 559 ms 51304 KB Output is correct
7 Correct 563 ms 51304 KB Output is correct
8 Correct 600 ms 51308 KB Output is correct
9 Correct 592 ms 51308 KB Output is correct
10 Correct 532 ms 51308 KB Output is correct
11 Correct 502 ms 51308 KB Output is correct

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 18620 KB Output is correct
2 Correct 3 ms 18620 KB Output is correct
3 Correct 6 ms 18620 KB Output is correct
4 Correct 4 ms 18620 KB Output is correct
5 Correct 2 ms 18620 KB Output is correct
6 Correct 0 ms 18620 KB Output is correct
7 Correct 0 ms 18620 KB Output is correct
8 Correct 9 ms 18620 KB Output is correct
9 Correct 6 ms 18620 KB Output is correct
10 Correct 2 ms 18620 KB Output is correct
11 Correct 565 ms 51308 KB Output is correct
12 Correct 602 ms 51304 KB Output is correct
13 Correct 604 ms 51304 KB Output is correct
14 Correct 636 ms 51304 KB Output is correct
15 Correct 600 ms 51308 KB Output is correct
16 Correct 559 ms 51304 KB Output is correct
17 Correct 563 ms 51304 KB Output is correct
18 Correct 600 ms 51308 KB Output is correct
19 Correct 592 ms 51308 KB Output is correct
20 Correct 532 ms 51308 KB Output is correct
21 Correct 502 ms 51308 KB Output is correct
22 Correct 1291 ms 28388 KB Output is correct
23 Correct 1271 ms 28388 KB Output is correct
24 Correct 1180 ms 28388 KB Output is correct
25 Correct 1292 ms 28388 KB Output is correct
26 Correct 721 ms 35680 KB Output is correct
27 Correct 762 ms 32260 KB Output is correct
28 Correct 787 ms 30924 KB Output is correct
29 Correct 526 ms 51308 KB Output is correct
30 Correct 536 ms 51308 KB Output is correct
31 Execution timed out 3000 ms 30104 KB Execution timed out
32 Halted 0 ms 0 KB -