oj.uz

Submission #40174

# Submission time Handle Problem Language Result Execution time Memory
40174 2018-01-29T10:00:20 Z krauch Zagrade (COI17_zagrade) C++14
100 / 100
 1378 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], MXVAL;
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 (bal == mn) MXVAL = max(MXVAL, abs(bal));
    if (bal2 == mx) tmp[bal2] += kek;
    if (bal2 == mx) MXVAL = max(MXVAL, abs(bal2));
    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;
        MXVAL = 0;
        calc(to, root, (a[root] == ')' ? -1 : 1), (a[root] == ')' ? -1 : 1), 0, 0, 1);
        forn(i, 0, MXVAL) {
            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:131:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d\n", &n);
                      ^
zagrade.cpp:133:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%c", a + i);
                           ^
zagrade.cpp:135:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("\n");
                ^
zagrade.cpp:139: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 3 ms 18620 KB Output is correct
2 Correct 0 ms 18620 KB Output is correct
3 Correct 0 ms 18620 KB Output is correct
4 Correct 2 ms 18620 KB Output is correct
5 Correct 3 ms 18620 KB Output is correct
6 Correct 9 ms 18620 KB Output is correct
7 Correct 11 ms 18620 KB Output is correct
8 Correct 0 ms 18620 KB Output is correct
9 Correct 2 ms 18620 KB Output is correct
10 Correct 6 ms 18620 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 569 ms 51304 KB Output is correct
2 Correct 597 ms 51300 KB Output is correct
3 Correct 546 ms 51308 KB Output is correct
4 Correct 610 ms 51308 KB Output is correct
5 Correct 593 ms 51304 KB Output is correct
6 Correct 551 ms 51304 KB Output is correct
7 Correct 549 ms 51304 KB Output is correct
8 Correct 642 ms 51304 KB Output is correct
9 Correct 569 ms 51304 KB Output is correct
10 Correct 505 ms 51304 KB Output is correct
11 Correct 515 ms 51308 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18620 KB Output is correct
2 Correct 0 ms 18620 KB Output is correct
3 Correct 0 ms 18620 KB Output is correct
4 Correct 2 ms 18620 KB Output is correct
5 Correct 3 ms 18620 KB Output is correct
6 Correct 9 ms 18620 KB Output is correct
7 Correct 11 ms 18620 KB Output is correct
8 Correct 0 ms 18620 KB Output is correct
9 Correct 2 ms 18620 KB Output is correct
10 Correct 6 ms 18620 KB Output is correct
11 Correct 569 ms 51304 KB Output is correct
12 Correct 597 ms 51300 KB Output is correct
13 Correct 546 ms 51308 KB Output is correct
14 Correct 610 ms 51308 KB Output is correct
15 Correct 593 ms 51304 KB Output is correct
16 Correct 551 ms 51304 KB Output is correct
17 Correct 549 ms 51304 KB Output is correct
18 Correct 642 ms 51304 KB Output is correct
19 Correct 569 ms 51304 KB Output is correct
20 Correct 505 ms 51304 KB Output is correct
21 Correct 515 ms 51308 KB Output is correct
22 Correct 1231 ms 28388 KB Output is correct
23 Correct 1271 ms 28388 KB Output is correct
24 Correct 1190 ms 28388 KB Output is correct
25 Correct 1378 ms 28388 KB Output is correct
26 Correct 730 ms 35680 KB Output is correct
27 Correct 738 ms 32252 KB Output is correct
28 Correct 761 ms 30920 KB Output is correct
29 Correct 510 ms 51308 KB Output is correct
30 Correct 513 ms 51304 KB Output is correct
31 Correct 148 ms 33208 KB Output is correct
32 Correct 533 ms 51308 KB Output is correct