oj.uz

Submission #40172

# Submission time Handle Problem Language Result Execution time Memory
40172 2018-01-29T09:53:36 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 / 2 + 1) 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 / 2 + 1) {
            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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 18620 KB Output is correct
2 Correct 2 ms 18620 KB Output is correct
3 Correct 5 ms 18620 KB Output is correct
4 Correct 5 ms 18620 KB Output is correct
5 Correct 0 ms 18620 KB Output is correct
6 Correct 3 ms 18620 KB Output is correct
7 Correct 2 ms 18620 KB Output is correct
8 Correct 4 ms 18620 KB Output is correct
9 Correct 0 ms 18620 KB Output is correct
10 Correct 0 ms 18620 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 585 ms 51304 KB Output is correct
2 Correct 563 ms 51304 KB Output is correct
3 Correct 588 ms 51304 KB Output is correct
4 Correct 581 ms 51300 KB Output is correct
5 Correct 587 ms 51300 KB Output is correct
6 Correct 554 ms 51304 KB Output is correct
7 Correct 568 ms 51308 KB Output is correct
8 Correct 600 ms 51300 KB Output is correct
9 Correct 602 ms 51304 KB Output is correct
10 Correct 497 ms 51304 KB Output is correct
11 Correct 511 ms 51304 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 18620 KB Output is correct
2 Correct 2 ms 18620 KB Output is correct
3 Correct 5 ms 18620 KB Output is correct
4 Correct 5 ms 18620 KB Output is correct
5 Correct 0 ms 18620 KB Output is correct
6 Correct 3 ms 18620 KB Output is correct
7 Correct 2 ms 18620 KB Output is correct
8 Correct 4 ms 18620 KB Output is correct
9 Correct 0 ms 18620 KB Output is correct
10 Correct 0 ms 18620 KB Output is correct
11 Correct 585 ms 51304 KB Output is correct
12 Correct 563 ms 51304 KB Output is correct
13 Correct 588 ms 51304 KB Output is correct
14 Correct 581 ms 51300 KB Output is correct
15 Correct 587 ms 51300 KB Output is correct
16 Correct 554 ms 51304 KB Output is correct
17 Correct 568 ms 51308 KB Output is correct
18 Correct 600 ms 51300 KB Output is correct
19 Correct 602 ms 51304 KB Output is correct
20 Correct 497 ms 51304 KB Output is correct
21 Correct 511 ms 51304 KB Output is correct
22 Correct 1224 ms 28388 KB Output is correct
23 Correct 1181 ms 28388 KB Output is correct
24 Correct 1284 ms 28388 KB Output is correct
25 Correct 1301 ms 28388 KB Output is correct
26 Correct 716 ms 35680 KB Output is correct
27 Correct 739 ms 32256 KB Output is correct
28 Correct 766 ms 30924 KB Output is correct
29 Correct 495 ms 51304 KB Output is correct
30 Correct 514 ms 51304 KB Output is correct
31 Execution timed out 3000 ms 30104 KB Execution timed out
32 Halted 0 ms 0 KB -