Submission #3730822


Source Code Expand

#include<bits/stdc++.h>
#define fi first
#define se second
#define LL long long

using namespace std;
const int maxn = 1e5 + 5;
typedef pair<int, int> P;

vector<int> g[maxn];
char s[maxn];
int sz[maxn], rt;
LL dp[maxn][3], ans = 1LL << 18;
LL f[3][3];

void dfs(int u, int fa) {
    for(auto v:g[u]) {
        if(v == fa)
            continue;
        dfs(v, u);
    }
    for(int i = 0; i < 3; i++) {
        for(int j = 0; j < 3; j++)
            f[i][j] = 1LL << 60;
        f[i][i] = 1 + (i > 1);
    }
    for(auto v:g[u]) {
        if(v == fa)
            continue;
        if(sz[v]) {
            for(int i = 0; i < 3; i++) {
                f[i][2] = min(f[i][0] + dp[v][2], f[i][2] + dp[v][0]) + 1;
                f[i][2] = min(f[i][1] + dp[v][1] + 1, f[i][2]);
                f[i][1] = min(f[i][0] + dp[v][1], f[i][1] + dp[v][0] + 1);
                f[i][0] = f[i][0] + dp[v][0] + 1;
            }
            sz[u]++;
        }
    }
    for(int i = 0; i < 3; i++)
        dp[u][i] = 1LL << 60;
    int op = (sz[u] + (s[u] == 'W')) & 1;
    for(int j = 0; j < 3; j++) {
        dp[u][j] = min(dp[u][j], f[0][j] + ((op + (j == 0) + (j == 2 && u == rt)) & 1));
    }
    for(int j = 1; j < 3; j++) {
        dp[u][j] = min(dp[u][j], f[1][j] + ((op + 1 + (j == 2 && u == rt)) & 1));
    }
    for(int j = 2; j < 3; j++) {
        dp[u][j] = min(dp[u][j], f[2][j] + ((op + 2) & 1));
    }

//    cout<<u<<" : "<<dp[u][0]<<" "<<dp[u][1]<<" "<<dp[u][1]<<endl;
//    for(int i = 0; i < 3; i++) {
//        for(int j = 0; j < 3; j++) cout<<i<<" "<<j<<" "<<f[i][j]<<endl;
//    }
    if(s[u] == 'W')
        sz[u]++;
}

int main() {
#ifdef CX_TEST
    freopen("E:\\program--GG\\test_in.txt", "r", stdin);
#endif
    int n, i, u, v;
    scanf("%d", &n);
    for(i = 1; i < n; i++) {
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    scanf("%s", s + 1);
    for(i = 1; i <= n; i++) {
        if(s[i] == 'W')
            break;
    }
    rt = i;
    if(i > n)
        return puts("0"), 0;
    dfs(i, 0);
    cout << min(min(dp[i][0], dp[i][1]), dp[i][2] - 1) << endl;
    return 0;
}

Submission Info

Submission Time
Task F - Monochrome Cat
User vjudge2
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2132 Byte
Status WA
Exec Time 54 ms
Memory 16384 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:66:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
./Main.cpp:68:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &u, &v);
                              ^
./Main.cpp:72: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 All
Score / Max Score 0 / 0 0 / 800
Status
AC × 4
AC × 102
WA × 16
Set Name Test Cases
Sample 0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt
All 0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt, 1_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 1_023.txt, 1_024.txt, 1_025.txt, 1_026.txt, 1_027.txt, 1_028.txt, 1_029.txt, 1_030.txt, 1_031.txt, 1_032.txt, 1_033.txt, 1_034.txt, 1_035.txt, 1_036.txt, 1_037.txt, 1_038.txt, 1_039.txt, 1_040.txt, 1_041.txt, 1_042.txt, 1_043.txt, 1_044.txt, 1_045.txt, 1_046.txt, 1_047.txt, 1_048.txt, 1_049.txt, 1_050.txt, 1_051.txt, 1_052.txt, 1_053.txt, 1_054.txt, 1_055.txt, 1_056.txt, 1_057.txt, 1_058.txt, 1_059.txt, 1_060.txt, 1_061.txt, 1_062.txt, 1_063.txt, 1_064.txt, 1_065.txt, 1_066.txt, 1_067.txt, 1_068.txt, 1_069.txt, 1_070.txt, 1_071.txt, 1_072.txt, 1_073.txt, 1_074.txt, 1_075.txt, 1_076.txt, 1_077.txt, 1_078.txt, 1_079.txt, 1_080.txt, 1_081.txt, 1_082.txt, 1_083.txt, 1_084.txt, 1_085.txt, 1_086.txt, 1_087.txt, 1_088.txt, 1_089.txt, 1_090.txt, 1_091.txt, 1_092.txt, 1_093.txt, 1_094.txt, 1_095.txt, 1_096.txt, 1_097.txt, 1_098.txt, 1_099.txt, 1_100.txt, 1_101.txt, 1_102.txt, 1_103.txt, 1_104.txt, 1_105.txt, 1_106.txt, 1_107.txt, 1_108.txt, 1_109.txt, 1_110.txt, 1_111.txt, 1_112.txt, 1_113.txt, 1_114.txt, 1_115.txt, 1_116.txt
Case Name Status Exec Time Memory
0_000.txt AC 2 ms 3328 KB
0_001.txt AC 2 ms 3328 KB
0_002.txt AC 3 ms 3328 KB
0_003.txt AC 3 ms 3328 KB
1_003.txt AC 2 ms 3328 KB
1_004.txt AC 3 ms 3328 KB
1_005.txt AC 2 ms 3328 KB
1_006.txt AC 3 ms 3328 KB
1_007.txt AC 3 ms 3328 KB
1_008.txt AC 3 ms 3328 KB
1_009.txt AC 3 ms 3328 KB
1_010.txt AC 3 ms 3328 KB
1_011.txt AC 3 ms 3328 KB
1_012.txt AC 3 ms 3328 KB
1_013.txt AC 2 ms 3328 KB
1_014.txt AC 3 ms 3328 KB
1_015.txt AC 2 ms 3328 KB
1_016.txt AC 3 ms 3328 KB
1_017.txt AC 2 ms 3328 KB
1_018.txt AC 3 ms 3328 KB
1_019.txt AC 2 ms 3328 KB
1_020.txt AC 3 ms 3328 KB
1_021.txt AC 3 ms 3328 KB
1_022.txt AC 3 ms 3328 KB
1_023.txt AC 3 ms 3328 KB
1_024.txt AC 3 ms 3328 KB
1_025.txt AC 3 ms 3328 KB
1_026.txt AC 3 ms 3328 KB
1_027.txt AC 3 ms 3328 KB
1_028.txt AC 3 ms 3328 KB
1_029.txt AC 3 ms 3328 KB
1_030.txt AC 3 ms 3328 KB
1_031.txt AC 2 ms 3328 KB
1_032.txt AC 3 ms 3328 KB
1_033.txt AC 2 ms 3328 KB
1_034.txt AC 3 ms 3328 KB
1_035.txt AC 2 ms 3328 KB
1_036.txt AC 3 ms 3328 KB
1_037.txt AC 2 ms 3328 KB
1_038.txt AC 3 ms 3328 KB
1_039.txt AC 3 ms 3328 KB
1_040.txt AC 3 ms 3328 KB
1_041.txt AC 2 ms 3328 KB
1_042.txt AC 2 ms 3328 KB
1_043.txt AC 3 ms 3328 KB
1_044.txt AC 3 ms 3328 KB
1_045.txt AC 18 ms 7424 KB
1_046.txt AC 22 ms 8960 KB
1_047.txt AC 33 ms 6400 KB
1_048.txt AC 34 ms 11648 KB
1_049.txt AC 34 ms 12800 KB
1_050.txt AC 30 ms 10496 KB
1_051.txt AC 25 ms 7800 KB
1_052.txt AC 8 ms 4480 KB
1_053.txt AC 23 ms 6392 KB
1_054.txt AC 12 ms 5372 KB
1_055.txt AC 25 ms 7800 KB
1_056.txt AC 15 ms 6140 KB
1_057.txt WA 3 ms 3456 KB
1_058.txt AC 22 ms 7424 KB
1_059.txt AC 14 ms 4480 KB
1_060.txt AC 34 ms 9728 KB
1_061.txt AC 38 ms 10112 KB
1_062.txt WA 21 ms 7296 KB
1_063.txt AC 24 ms 6784 KB
1_064.txt WA 18 ms 5760 KB
1_065.txt AC 4 ms 3584 KB
1_066.txt AC 32 ms 7932 KB
1_067.txt AC 9 ms 4352 KB
1_068.txt AC 21 ms 6272 KB
1_069.txt WA 12 ms 4864 KB
1_070.txt WA 22 ms 6016 KB
1_071.txt AC 29 ms 6016 KB
1_072.txt AC 22 ms 6272 KB
1_073.txt AC 6 ms 3840 KB
1_074.txt WA 5 ms 3712 KB
1_075.txt WA 19 ms 5760 KB
1_076.txt WA 42 ms 8576 KB
1_077.txt AC 28 ms 5888 KB
1_078.txt AC 14 ms 4992 KB
1_079.txt AC 19 ms 5760 KB
1_080.txt WA 21 ms 6016 KB
1_081.txt AC 47 ms 12800 KB
1_082.txt AC 52 ms 15360 KB
1_083.txt AC 34 ms 6528 KB
1_084.txt AC 52 ms 14976 KB
1_085.txt AC 54 ms 16384 KB
1_086.txt AC 49 ms 15488 KB
1_087.txt AC 34 ms 8952 KB
1_088.txt AC 33 ms 8952 KB
1_089.txt AC 29 ms 6904 KB
1_090.txt AC 33 ms 8952 KB
1_091.txt AC 35 ms 8952 KB
1_092.txt AC 29 ms 6904 KB
1_093.txt AC 50 ms 10880 KB
1_094.txt AC 49 ms 12288 KB
1_095.txt AC 35 ms 6528 KB
1_096.txt AC 45 ms 10752 KB
1_097.txt AC 46 ms 12160 KB
1_098.txt AC 47 ms 11904 KB
1_099.txt WA 40 ms 8700 KB
1_100.txt AC 39 ms 8700 KB
1_101.txt AC 32 ms 6652 KB
1_102.txt AC 38 ms 8700 KB
1_103.txt AC 39 ms 8700 KB
1_104.txt WA 38 ms 8700 KB
1_105.txt WA 43 ms 8576 KB
1_106.txt WA 43 ms 8576 KB
1_107.txt AC 34 ms 6528 KB
1_108.txt AC 42 ms 8576 KB
1_109.txt AC 43 ms 8576 KB
1_110.txt WA 43 ms 8576 KB
1_111.txt AC 43 ms 8576 KB
1_112.txt WA 43 ms 8576 KB
1_113.txt AC 34 ms 6528 KB
1_114.txt AC 42 ms 8576 KB
1_115.txt AC 44 ms 8576 KB
1_116.txt WA 43 ms 8576 KB