Submission #223642

#	Time	Username	Problem	Language	Result	Execution time	Memory
223642		kingfran1907	Zagrade (COI17_zagrade)	C++14	100 / 100	1808 ms	46584 KiB

zagrade

#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 (stderr)

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 / 10
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60