답안 #40174 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
40174	2018-01-29T10:00:20 Z	krauch	Zagrade (COI17_zagrade)	C++14	100 / 100	1378 ms	51308 KB

zagrade

/*
 _    _    _______   _    _
| |  / /  |  _____| | |  / /
| | / /   | |       | | / /
| |/ /    | |_____  | |/ /
| |\ \    |  _____| | |\ \
| | \ \   | |       | | \ \
| |  \ \  | |_____  | |  \ \
|_|   \_\ |_______| |_|   \_\

*/
#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #40174

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 30.0 / 30.0

Subtask #3 60.0 / 60.0

Subtask #1
10.0 / 10.0

Subtask #2
30.0 / 30.0

Subtask #3
60.0 / 60.0