oj.uz

Submission #223642

# Submission time Handle Problem Language Result Execution time Memory
223642 2020-04-15T21:42:54 Z kingfran1907 Zagrade (COI17_zagrade) C++14
100 / 100
 1808 ms 46584 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long llint;

const int maxn = 3e5+10;

int n;
int niz[maxn];
vector< int > graph[maxn];
bool bio[maxn];
int cnt[maxn];

pair<int, int> fin(int x, int parr, int siz) {
    bool flag = true;
    int ac = 1;
    int cen = -1;

    int suma = siz - 1;
    for (int i = 0; i < graph[x].size(); i++) {
        int tren = graph[x][i];
        if (tren == parr) continue;
        if (bio[tren]) continue;

        pair<int, int> t = fin(tren, x, siz);
        ac += t.second;
        suma -= t.second;
        if (t.second > siz / 2) flag = false;
        cen = max(cen, t.first);
    }
    if (flag && suma <= siz / 2) cen = x;
    return make_pair(cen, ac);
}

int cn(int x, int parr) {
    int out = 1;
    for (int i = 0; i < graph[x].size(); i++) {
        int tren = graph[x][i];
        if (bio[tren]) continue;
        if (tren == parr) continue;

        out += cn(tren, x);
    }
    return out;
}

llint las(int x, int parr, int sum, int mini) {
    llint out = 0;
    sum += niz[x];
    mini = min(mini, sum);
    if (sum <= mini && sum <= 0) out += cnt[-sum];
    //printf("las %d %d %d %d\n", x, parr, sum, mini);

    for (int i = 0; i < graph[x].size(); i++) {
        int tren = graph[x][i];
        if (tren == parr) continue;
        if (bio[tren]) continue;

        out += las(tren, x, sum, mini);
    }
    return out;
}

void fron(int x, int parr, int sum, int mini) {
    sum += niz[x];
    mini = min(niz[x], mini + niz[x]);
    if (mini >= 0) cnt[sum]++;
    //printf("fron %d %d %d %d\n", x, parr, sum, mini);

    for (int i = 0; i < graph[x].size(); i++) {
        int tren = graph[x][i];
        if (tren == parr) continue;
        if (bio[tren]) continue;

        //printf("conn: %d %d\n", x, tren);
        fron(tren, x, sum, mini);
    }
    //printf("ret fron %d %d\n", x, parr);
}

void fron2(int x, int parr, int sum, int mini) {
    sum += niz[x];
    mini = min(niz[x], mini + niz[x]);
    if (mini >= 0) cnt[sum]--;
    //printf("fron %d %d %d %d\n", x, parr, sum, mini);

    for (int i = 0; i < graph[x].size(); i++) {
        int tren = graph[x][i];
        if (tren == parr) continue;
        if (bio[tren]) continue;

        //printf("conn: %d %d\n", x, tren);
        fron2(tren, x, sum, mini);
    }
    //printf("ret fron %d %d\n", x, parr);
}

llint f(int x, int siz) {
    //printf("fin %d %d\n", x, siz);
    int cen = fin(x, -1, siz).first;
    llint out = 0;

    //printf("fin start cal (cen = %d)\n", cen);
    //memset(cnt, 0, sizeof cnt);
    //if (niz[cen] == 1) cnt[1] = 1;
    cnt[0]++;
    for (int i = 0; i < graph[cen].size(); i++) {
        int tren = graph[cen][i];
        if (bio[tren]) continue;

        out += las(tren, cen, niz[cen], niz[cen]);
        fron(tren, cen, 0, 0);
    }
    if (niz[cen] == -1) out += cnt[1];

    for (int i = 0; i < graph[cen].size(); i++) {
        int tren = graph[cen][i];
        if (bio[tren]) continue;

        fron2(tren, cen, 0, 0);
    }
    cnt[0]--;

    //memset(cnt, 0, sizeof cnt);
    for (int i = graph[cen].size() - 1; i >= 0; i--) {
        int tren = graph[cen][i];
        if (bio[tren]) continue;

        out += las(tren, cen, niz[cen], niz[cen]);
        fron(tren, cen, 0, 0);
    }

    for (int i = 0; i < graph[cen].size(); i++) {
        int tren = graph[cen][i];
        if (bio[tren]) continue;

        fron2(tren, cen, 0, 0);
    }

    bio[cen] = true;
    for (int i = 0; i < graph[cen].size(); i++) {
        int tren = graph[cen][i];
        if (bio[tren]) continue;

        int si = cn(tren, -1);
        out += f(tren, si);
    }
    return out;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        char c;
        scanf(" %c", &c);

        if (c == '(') niz[i] = 1;
        else niz[i] = -1;
    }

    for (int i = 1; i < n; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    memset(bio, false, sizeof bio);
    printf("%lld\n", f(1, n));
    return 0;
}

Compilation message

zagrade.cpp: In function 'std::pair<int, int> fin(int, int, int)':
zagrade.cpp:20:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < graph[x].size(); i++) {
                     ~~^~~~~~~~~~~~~~~~~
zagrade.cpp: In function 'int cn(int, int)':
zagrade.cpp:37:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < graph[x].size(); i++) {
                     ~~^~~~~~~~~~~~~~~~~
zagrade.cpp: In function 'llint las(int, int, int, int)':
zagrade.cpp:54:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < graph[x].size(); i++) {
                     ~~^~~~~~~~~~~~~~~~~
zagrade.cpp: In function 'void fron(int, int, int, int)':
zagrade.cpp:70:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < graph[x].size(); i++) {
                     ~~^~~~~~~~~~~~~~~~~
zagrade.cpp: In function 'void fron2(int, int, int, int)':
zagrade.cpp:87:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < graph[x].size(); i++) {
                     ~~^~~~~~~~~~~~~~~~~
zagrade.cpp: In function 'llint f(int, int)':
zagrade.cpp:107:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < graph[cen].size(); i++) {
                     ~~^~~~~~~~~~~~~~~~~~~
zagrade.cpp:116:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < graph[cen].size(); i++) {
                     ~~^~~~~~~~~~~~~~~~~~~
zagrade.cpp:133:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < graph[cen].size(); i++) {
                     ~~^~~~~~~~~~~~~~~~~~~
zagrade.cpp:141:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < graph[cen].size(); i++) {
                     ~~^~~~~~~~~~~~~~~~~~~
zagrade.cpp: In function 'int main()':
zagrade.cpp:152:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
zagrade.cpp:155:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c", &c);
         ~~~~~^~~~~~~~~~~
zagrade.cpp:163:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 647 ms 41724 KB Output is correct
2 Correct 635 ms 46072 KB Output is correct
3 Correct 652 ms 46072 KB Output is correct
4 Correct 621 ms 45944 KB Output is correct
5 Correct 632 ms 46024 KB Output is correct
6 Correct 653 ms 46072 KB Output is correct
7 Correct 626 ms 46072 KB Output is correct
8 Correct 689 ms 45944 KB Output is correct
9 Correct 658 ms 45944 KB Output is correct
10 Correct 643 ms 46584 KB Output is correct
11 Correct 650 ms 45944 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 7680 KB Output is correct
2 Correct 10 ms 7680 KB Output is correct
3 Correct 10 ms 7680 KB Output is correct
4 Correct 11 ms 7680 KB Output is correct
5 Correct 10 ms 7680 KB Output is correct
6 Correct 9 ms 7680 KB Output is correct
7 Correct 10 ms 7680 KB Output is correct
8 Correct 12 ms 7680 KB Output is correct
9 Correct 10 ms 7680 KB Output is correct
10 Correct 11 ms 7680 KB Output is correct
11 Correct 647 ms 41724 KB Output is correct
12 Correct 635 ms 46072 KB Output is correct
13 Correct 652 ms 46072 KB Output is correct
14 Correct 621 ms 45944 KB Output is correct
15 Correct 632 ms 46024 KB Output is correct
16 Correct 653 ms 46072 KB Output is correct
17 Correct 626 ms 46072 KB Output is correct
18 Correct 689 ms 45944 KB Output is correct
19 Correct 658 ms 45944 KB Output is correct
20 Correct 643 ms 46584 KB Output is correct
21 Correct 650 ms 45944 KB Output is correct
22 Correct 1808 ms 22648 KB Output is correct
23 Correct 1610 ms 22644 KB Output is correct
24 Correct 1468 ms 22652 KB Output is correct
25 Correct 1459 ms 22636 KB Output is correct
26 Correct 804 ms 30328 KB Output is correct
27 Correct 827 ms 26872 KB Output is correct
28 Correct 841 ms 25436 KB Output is correct
29 Correct 618 ms 46456 KB Output is correct
30 Correct 630 ms 46432 KB Output is correct
31 Correct 145 ms 22252 KB Output is correct
32 Correct 608 ms 46052 KB Output is correct