Submission #1690588


Source Code Expand

// Copyright (C) 2017 __debug.

// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License as
// published by the Free Software Foundation; version 3

// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this program; If not, see <http://www.gnu.org/licenses/>.


#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>

#define x first
#define y second
#define MP std::make_pair
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(), (x).end()
#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#ifdef __linux__
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif

using std::pair;
using std::vector;
using std::string;

typedef long long LL;
typedef pair<int, int> Pii;

const int oo = 0x3f3f3f3f;

template<typename T> inline bool chkmax(T &a, T b) { return a < b ? a = b, true : false; }
template<typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, true : false; }
string procStatus()
{
    std::ifstream t("/proc/self/status");
    return string(std::istreambuf_iterator<char>(t), std::istreambuf_iterator<char>());
}
template<typename T> T read(T &x)
{
    int f = 1;
    char ch = getchar();
    for (; !isdigit(ch); ch = getchar())
        f = (ch == '-' ? -1 : 1);
    for (x = 0; isdigit(ch); ch = getchar())
        x = 10 * x + ch - '0';
    return x *= f;
}
template<typename T> void write(T x)
{
    if (x == 0) {
        putchar('0');
        return;
    }
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    static char s[20];
    int top = 0;
    for (; x; x /= 10)
        s[++top] = x % 10 + '0';
    while (top)
        putchar(s[top--]);
}
// EOT

const int MAXN = 2e5 + 5;

int N;
vector<int> G[MAXN];
char S[MAXN];

void input()
{
    read(N);
    for (int i = 1; i < N; ++i) {
        int u, v;
        read(u); read(v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    scanf("%s", S + 1);
}

int maxd[MAXN], secd[MAXN], maxu[MAXN];
int costd[MAXN];
int cnt[MAXN];

void dfs1(int u, int f)
{
    costd[u] = (S[u] == '1' ? 0 : +oo);
    cnt[u] = (S[u] == '1');
    for (int i = 0; i < SZ(G[u]); ++i) {
        int v = G[u][i];
        if (v == f)
            continue;
        dfs1(v, u);
        if (chkmax(secd[u], maxd[v] + 1)) {
            if (secd[u] > maxd[u])
                std::swap(secd[u], maxd[u]);
        }
        chkmin(costd[u], costd[v] + 1);
        cnt[u] += cnt[v];
    }
}

void dfs2(int u, int f, int x)
{
    maxu[u] = x;
    for (int i = 0; i < SZ(G[u]); ++i) {
        int v = G[u][i];
        if (v == f)
            continue;
        dfs2(v, u, std::max(x, (maxd[u] == maxd[v] + 1 ? secd[u] : maxd[u])) + 1);
    }
}

void solve()
{
    dfs1(1, 0);
    dfs2(1, 0, 0);

    LL ans = 1;

    for (int u = 1; u <= N; ++u) {
        if (chkmax(secd[u], maxu[u])) {
            if (secd[u] > maxd[u])
                std::swap(secd[u], maxd[u]);
        }
        LL rbnd = std::min(maxd[u] - 1, secd[u] + 1);
        LL lbnd = std::min(costd[u], cnt[u] == cnt[1] ? +oo : maxu[u]);
        // printf("%d: %d %d\n", u, lbnd, rbnd);
        if (lbnd <= rbnd)
            ans += rbnd - lbnd + 1;
    }

    printf("%lld\n", ans);
}

int main()
{
#ifdef __DEBUG
    freopen("F.in", "r", stdin);
    freopen("F.out", "w", stdout);
#endif

    input();
    solve();

    return 0;
}

// 弓满则折,月满则缺。

Submission Info

Submission Time
Task F - Black Radius
User Ivlleiooq
Language C++14 (GCC 5.4.1)
Score 1300
Code Size 3883 Byte
Status WA
Exec Time 150 ms
Memory 29568 KB

Compile Error

./Main.cpp: In function ‘void input()’:
./Main.cpp:91:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", S + 1);
                       ^

Judge Result

Set Name Sample Subtask All
Score / Max Score 0 / 0 1300 / 1300 0 / 600
Status
AC × 3
AC × 31
AC × 39
WA × 42
Set Name Test Cases
Sample 0_00.txt, 0_01.txt, 0_02.txt
Subtask 0_01.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt
All 0_00.txt, 0_01.txt, 0_02.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 2_00.txt, 2_01.txt, 2_02.txt, 2_03.txt, 2_04.txt, 2_05.txt, 2_06.txt, 2_07.txt, 2_08.txt, 2_09.txt, 2_10.txt, 2_11.txt, 2_12.txt, 2_13.txt, 2_14.txt, 2_15.txt, 2_16.txt, 2_17.txt, 2_18.txt, 2_19.txt, 2_20.txt, 2_21.txt, 2_22.txt, 2_23.txt, 2_24.txt, 2_25.txt, 2_26.txt, 2_27.txt, 2_28.txt, 2_29.txt, 2_30.txt, 2_31.txt, 2_32.txt, 2_33.txt, 2_34.txt, 2_35.txt, 2_36.txt, 2_37.txt, 2_38.txt, 2_39.txt, 2_40.txt, 2_41.txt, 2_42.txt, 2_43.txt, 2_44.txt, 2_45.txt, 2_46.txt, 2_47.txt
Case Name Status Exec Time Memory
0_00.txt AC 3 ms 7040 KB
0_01.txt AC 3 ms 7040 KB
0_02.txt AC 3 ms 7040 KB
1_00.txt AC 3 ms 7040 KB
1_01.txt AC 120 ms 29568 KB
1_02.txt AC 142 ms 24448 KB
1_03.txt AC 108 ms 15360 KB
1_04.txt AC 62 ms 15608 KB
1_05.txt AC 43 ms 16116 KB
1_06.txt AC 70 ms 15488 KB
1_07.txt AC 73 ms 15488 KB
1_08.txt AC 78 ms 16640 KB
1_09.txt AC 98 ms 22528 KB
1_10.txt AC 94 ms 21376 KB
1_11.txt AC 109 ms 29440 KB
1_12.txt AC 80 ms 18560 KB
1_13.txt AC 92 ms 21888 KB
1_14.txt AC 84 ms 18176 KB
1_15.txt AC 76 ms 16896 KB
1_16.txt AC 87 ms 19328 KB
1_17.txt AC 105 ms 20864 KB
1_18.txt AC 76 ms 15360 KB
1_19.txt AC 77 ms 15360 KB
1_20.txt AC 87 ms 15360 KB
1_21.txt AC 88 ms 16256 KB
1_22.txt AC 65 ms 15612 KB
1_23.txt AC 72 ms 15612 KB
1_24.txt AC 82 ms 18560 KB
1_25.txt AC 84 ms 17784 KB
1_26.txt AC 62 ms 15356 KB
1_27.txt AC 67 ms 15736 KB
1_28.txt AC 61 ms 16248 KB
1_29.txt AC 89 ms 18812 KB
2_00.txt AC 3 ms 7040 KB
2_01.txt WA 132 ms 28928 KB
2_02.txt WA 118 ms 26752 KB
2_03.txt WA 117 ms 26112 KB
2_04.txt WA 113 ms 22144 KB
2_05.txt WA 133 ms 22400 KB
2_06.txt WA 150 ms 23424 KB
2_07.txt WA 131 ms 15360 KB
2_08.txt WA 131 ms 15360 KB
2_09.txt WA 122 ms 15360 KB
2_10.txt AC 77 ms 15736 KB
2_11.txt WA 66 ms 15608 KB
2_12.txt AC 52 ms 15608 KB
2_13.txt AC 44 ms 16116 KB
2_14.txt AC 46 ms 16116 KB
2_15.txt AC 46 ms 16116 KB
2_16.txt WA 71 ms 15488 KB
2_17.txt WA 71 ms 15488 KB
2_18.txt WA 75 ms 15488 KB
2_19.txt WA 88 ms 15488 KB
2_20.txt WA 84 ms 15488 KB
2_21.txt WA 78 ms 15488 KB
2_22.txt WA 76 ms 16512 KB
2_23.txt WA 75 ms 17280 KB
2_24.txt WA 77 ms 17024 KB
2_25.txt WA 93 ms 23040 KB
2_26.txt WA 98 ms 21504 KB
2_27.txt WA 93 ms 22912 KB
2_28.txt WA 84 ms 20864 KB
2_29.txt WA 107 ms 27264 KB
2_30.txt WA 110 ms 25216 KB
2_31.txt WA 96 ms 20992 KB
2_32.txt WA 70 ms 15872 KB
2_33.txt WA 86 ms 18432 KB
2_34.txt WA 82 ms 20480 KB
2_35.txt WA 102 ms 23808 KB
2_36.txt WA 75 ms 15232 KB
2_37.txt WA 69 ms 15360 KB
2_38.txt WA 78 ms 16768 KB
2_39.txt WA 86 ms 15488 KB
2_40.txt WA 59 ms 15608 KB
2_41.txt WA 79 ms 15488 KB
2_42.txt WA 65 ms 15608 KB
2_43.txt WA 92 ms 22144 KB
2_44.txt WA 62 ms 15608 KB
2_45.txt WA 47 ms 15864 KB
2_46.txt WA 51 ms 16116 KB
2_47.txt WA 81 ms 19576 KB