QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#323137#952. Spring cleaningCamillus0 266ms12988kbC++204.1kb2024-02-08 18:10:232024-02-08 18:10:24

Judging History

你现在查看的是最新测评结果

  • [2024-02-08 18:10:24]
  • 评测
  • 测评结果:0
  • 用时:266ms
  • 内存:12988kb
  • [2024-02-08 18:10:23]
  • 提交

answer

/// @author Camillus
#include <bits/stdc++.h>
using namespace std;

static constexpr int maxn = 1 << 17;

vector<int> g[maxn];
int p[maxn];
int sz[maxn];
int cnt[maxn];

int root = 0;

void dfs1(int u) {
    sz[u] = 1;

    auto it = find(g[u].begin(), g[u].end(), p[u]);
    if (it != g[u].end()) g[u].erase(it);

    if (g[u].empty()) {
        cnt[u] = 1;
        return;
    }

    for (int v : g[u]) {
        p[v] = u;
        dfs1(v);
        sz[u] += sz[v];
        cnt[u] += cnt[v];
    }

    int &f = g[u].front();
    for (int &v : g[u]) {
        if (sz[v] > sz[f]) {
            swap(f, v);
        }
    }
}


int tin[maxn];
int head[maxn];
int timer = 0;

void dfs2(int u) {
    tin[u] = timer++;

    if (head[u] == 0) {
        head[u] = u;
    }

    if (!g[u].empty()) {
        head[g[u].front()] = head[u];
    }

    for (int v : g[u]) {
        dfs2(v);
    }
}

namespace st {
    using value_t = array<int, 2>;
    value_t cnt[maxn * 2 - 1];
    bool reversed[maxn];

    constexpr value_t merge(const value_t &first, const value_t &second) {
        value_t result = first;
        result[0] += second[0];
        result[1] += second[1];
        return result;
    }

    inline void apply(int x) {
        swap(cnt[x][0], cnt[x][1]);
        reversed[x] ^= 1;
    }

    inline void push(int x) {
        if (reversed[x]) {
            apply(x * 2 + 1);
            apply(x * 2 + 1);
            reversed[x] = true;
        }
    }

    void reverse(int l, int r, int x = 0, int lx = 0, int rx = maxn) {
        if (l >= rx || lx >= r) {
            return;
        }

        if (l <= lx && rx <= r) {
            apply(x);
            return;
        }

        push(x);

        reverse(l, r, x * 2 + 1, lx, (lx + rx) / 2);
        reverse(l, r, x * 2 + 2, (lx + rx) / 2, rx);

        cnt[x] = merge(cnt[x * 2 + 1], cnt[x * 2 + 2]);
    }

    value_t get(int l, int r, int x = 0, int lx = 0, int rx = maxn) {
        if (l >= rx || lx >= r) {
            return value_t();
        }

        if (l <= lx && rx <= r) {
            return cnt[x];
        }

        push(x);

        return merge(
            get(l, r, x * 2 + 1, lx, (lx + rx) / 2),
            get(l, r, x * 2 + 2, (lx + rx) / 2, rx)
        );
    }

    void build(int n) {
        for (int u = 1; u <= n; u++) {
            int x = maxn + tin[u] - 1;
            cnt[x][::cnt[u] % 2] = 1;
        }

        for (int x = maxn - 2; x >= 0; x--) {
            cnt[x] = merge(cnt[x * 2 + 1], cnt[x * 2 + 2]);
        }
    }
} // namespace st

void reverse_path(int u) {
    while (true) {
        int v = head[u];

        st::reverse(tin[v], tin[u] + 1);

        if (u == 0) {
            break;
        }

        if (u == root) {
            break;
        } else {
            u = p[u];
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;

        g[u].push_back(v);
        g[v].push_back(u);
    }

    for (int u = 1; u <= n; u++) {
        if (g[u].size() > 1) {
            root = u;
        }
    }

    dfs1(root);
    dfs2(root);

    st::build(n);

    while (q--) {
        int d;
        cin >> d;

        map<int, int> c;

        for (int i = 0; i < d; i++) {
            int u;
            cin >> u;

            c[u] ^= 1;
        }

        for (auto &[u, k] : c) {
            if (g[u].size() == 0) {
                k ^= 1;
            }
        }

        for (auto &[u, k] : c) {
            if (k) {
                reverse_path(u);
            }
        }

        auto result = st::cnt[0];

        result[1] += d;

        if (st::get(0, 1)[1]) {
            cout << -1 << '\n';
        } else {
            cout << (result[0] - 1) * 2 + result[1] << '\n';
        }

        for (auto &[u, k] : c) {
            if (k) {
                reverse_path(u);
            }
        }
    }
    return 0;
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Accepted
time: 1ms
memory: 4576kb

input:

7 3
1 2
2 4
4 5
5 6
5 7
3 4
1 4
2 2 4
1 1

output:

-1
10
8

result:

ok 3 lines

Test #2:

score: -0
Wrong Answer
time: 176ms
memory: 6524kb

input:

20000 5000
9844 2753
14120 15267
6630 9346
16091 21
11589 11672
7243 10729
9376 18990
19172 16424
15329 4466
19473 2205
9722 13188
13805 12632
9639 7877
10960 12697
1725 10231
13383 4059
9258 10586
18536 11667
5581 666
1382 7072
17656 11359
10793 10158
18150 13161
9758 4811
280 4330
3962 17592
10138...

output:

89011
33577908
23454
23216
23454
23461
23476
23449
23470
23458
23474
23466
23465
23470
67132587
23462
23462
23471
23466
33577907
23460
23452
23468
23964
23462
23458
23456
23458
23470
23457
83909290
33577384
16800678
23461
33578409
23976
23455
23459
23458
23462
16800689
23460
23455
23462
23471
169972...

result:

wrong answer 1st lines differ - expected: '23481', found: '89011'

Subtask #2:

score: 0
Wrong Answer

Test #3:

score: 0
Wrong Answer
time: 7ms
memory: 5268kb

input:

3000 1
1 592
1 797
1 1542
1 1567
1 2784
1 455
1 140
1 2242
1 910
1 1018
1 961
1 661
1 2408
1 1791
1 776
1 2894
1 369
1 435
1 2441
1 519
1 2223
1 102
1 1478
1 2261
1 1920
1 2541
1 1835
1 1918
1 848
1 25
1 1993
1 1020
1 2852
1 719
1 226
1 2
1 156
1 13
1 748
1 2521
1 1762
1 2164
1 2905
1 2949
1 2994
1 ...

output:

168581433

result:

wrong answer 1st lines differ - expected: '84526', found: '168581433'

Subtask #3:

score: 0
Time Limit Exceeded

Test #8:

score: 0
Time Limit Exceeded

input:

5000 1
1342 1343
4110 4111
1415 1416
2960 2961
504 505
2756 2757
4496 4497
4178 4179
1933 1934
661 662
2894 2895
4041 4042
286 287
4881 4882
2988 2989
281 282
3038 3039
782 783
3878 3879
4914 4915
4578 4579
3877 3878
1870 1871
3014 3015
411 412
2711 2712
1479 1480
4818 4819
1930 1931
733 734
290 291...

output:


result:


Subtask #4:

score: 0
Time Limit Exceeded

Test #13:

score: 0
Time Limit Exceeded

input:

20000 300
2298 16922
18552 10941
5144 7836
2466 9076
15500 13240
2610 15368
46 12878
8306 1607
9979 8975
2496 19531
11248 4651
4852 18243
7396 1470
7610 10848
10295 14356
4459 5642
4890 16696
3731 3723
762 4227
13780 8107
13906 2311
9823 2028
15526 1892
6024 10011
9630 9756
9126 15139
14648 115
9097...

output:


result:


Subtask #5:

score: 0
Wrong Answer

Test #19:

score: 19
Accepted
time: 196ms
memory: 10268kb

input:

65535 65535
1811 13118
468 385
23933 56882
4701 42452
49582 14109
22804 8146
20990 13165
2862 42235
19741 48554
50898 55957
62662 44085
48624 14885
7097 61368
19900 36151
553 50630
52087 31138
45875 33789
57834 46368
50259 10233
56656 29222
48661 58651
62042 50198
5077 28414
50381 15211
60800 37526
...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 65535 lines

Test #20:

score: -19
Wrong Answer
time: 266ms
memory: 10208kb

input:

65535 4945
42941 23543
45541 34209
47644 12262
63786 38185
22551 3126
54952 11257
17620 53826
57165 30291
59502 23927
492 5929
64283 64528
57715 29045
63287 26916
59711 10374
25832 3012
35364 52502
43385 51892
37943 19200
33799 9796
56123 63643
35588 2879
38798 22405
12420 21846
39766 20399
51516 62...

output:

98263
98304
98745
98279
98292
33653207
98788
99025
98274
98289
98267
98771
98277
98250
98290
98298
98256
98268
99015
98271
98273
98750
229352
229852
229331
67207874
98301
98290
98281
98296
98777
33652969
33652930
67273436
33652937
33652974
67273183
33652959
33652960
98267
164295
98274
98291
98289
98...

result:

wrong answer 1st lines differ - expected: '98244', found: '98263'

Subtask #6:

score: 0
Wrong Answer

Test #24:

score: 0
Wrong Answer
time: 266ms
memory: 12988kb

input:

100000 100000
48535 38306
85495 24582
10294 14137
41148 31842
32266 36977
2963 82055
78886 1396
81175 93259
80317 66239
83481 49641
35645 57424
97195 2160
53900 55968
4256 17352
95865 83196
64417 63683
64041 61292
3392 82881
22755 53454
71067 1268
2191 84847
66432 7544
15405 77351
50616 64123
97980 ...

output:

117138
-1
-1
117137
-1
-1
117137
-1
117143
117143
-1
117140
117136
117141
117139
117140
117142
117145
117141
117146
-1
-1
-1
-1
-1
117138
-1
-1
117136
117139
-1
117144
117141
-1
117138
117144
117139
117141
117140
117137
117137
117141
117138
117137
-1
117144
117139
-1
117139
117146
-1
117140
-1
-1
-1...

result:

wrong answer 7th lines differ - expected: '117136', found: '117137'

Subtask #7:

score: 0
Skipped

Dependency #1:

0%