QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#448489	#8809. Telephone Plans	arbuzick^#	5	1ms	4008kb	C++20	2.2kb	2024-06-19 17:51:34	2024-06-19 17:52:05

Judging History

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

[2024-06-19 17:52:05]
评测

测评结果：5
用时：1ms
内存：4008kb

查看

[2024-06-19 17:51:34]
提交

answer

#include <bits/stdc++.h>

using namespace std;

constexpr int maxn = 2e3 + 5;

int lst[maxn][maxn];

int cnt[maxn * 5];

void solve() {
    int e;
    cin >> e;
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cnt[0]++;
        }
    }
    vector<set<int>> g(n);
    vector<vector<int>> nw(q, vector<int>(n));
    int prv = 0;
    for (int t = 0; t < q; ++t) {
        int tp;
        cin >> tp;
        if (tp == 1) {
            int x, y;
            cin >> x >> y;
            x ^= prv, y ^= prv;
            x--, y--;
            g[x].insert(y);
            g[y].insert(x);
        } else if (tp == 2) {
            int x, y;
            cin >> x >> y;
            x ^= prv, y ^= prv;
            x--, y--;
            g[x].erase(y);
            g[y].erase(x);
        }
        vector<int> used(n);
        for (int i = 0; i < n; ++i) {
            if (!used[i]) {
                vector<int> nw;
                queue<int> q;
                used[i] = 1;
                q.push(i);
                while (!q.empty()) {
                    int v = q.front();
                    q.pop();
                    nw.push_back(v);
                    for (auto u : g[v]) {
                        if (!used[u]) {
                            used[u] = 1;
                            q.push(u);
                        }
                    }
                }
                for (auto vl1 : nw) {
                    for (auto vl2 : nw) {
                        cnt[lst[vl1][vl2]]--;
                        lst[vl1][vl2] = t + 1;
                        cnt[lst[vl1][vl2]]++;
                    }
                }
            }
        }
        if (tp == 3) {
            int tm;
            cin >> tm;
            tm ^= prv;
            int ans = 0;
            for (int i = max(0, t - tm); i <= t; ++i) {
                ans += cnt[i + 1];
            }
            ans -= n;
            cout << ans / 2 << '\n';
            prv = (ans / 2) * e;
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

源文件, 语言: C++20

详细

Subtask #1:

score: 3

Accepted

Test #1:

score: 3

Accepted

time: 0ms

memory: 3564kb

input:

output:

result:

ok 147 lines

Test #2:

score: 0

Accepted

time: 0ms

memory: 3552kb

input:

output:

result:

ok 8 lines

Test #3:

score: 0

Accepted

time: 1ms

memory: 3796kb

input:

output:

result:

ok 92 lines

Test #4:

score: 0

Accepted

time: 1ms

memory: 3628kb

input:

output:

result:

ok 92 lines

Test #5:

score: 0

Accepted

time: 1ms

memory: 3924kb

input:

output:

result:

ok 92 lines

Test #6:

score: 0

Accepted

time: 1ms

memory: 3760kb

input:

output:

result:

ok 92 lines

Test #7:

score: 0

Accepted

time: 0ms

memory: 3948kb

input:

output:

result:

ok 92 lines

Test #8:

score: 0

Accepted

time: 0ms

memory: 3688kb

input:

output:

result:

ok 92 lines

Test #9:

score: 0

Accepted

time: 0ms

memory: 3680kb

input:

output:

result:

ok 92 lines

Test #10:

score: 0

Accepted

time: 1ms

memory: 3684kb

input:

output:

result:

ok 92 lines

Test #11:

score: 0

Accepted

time: 1ms

memory: 3692kb

input:

output:

result:

ok 92 lines

Test #12:

score: 0

Accepted

time: 1ms

memory: 3764kb

input:

output:

result:

ok 92 lines

Test #13:

score: 0

Accepted

time: 1ms

memory: 4004kb

input:

output:

result:

ok 92 lines

Test #14:

score: 0

Accepted

time: 1ms

memory: 3924kb

input:

output:

result:

ok 92 lines

Test #15:

score: 0

Accepted

time: 1ms

memory: 3800kb

input:

output:

result:

ok 92 lines

Test #16:

score: 0

Accepted

time: 1ms

memory: 3820kb

input:

output:

result:

ok 92 lines

Test #17:

score: 0

Accepted

time: 1ms

memory: 3692kb

input:

output:

result:

ok 92 lines

Test #18:

score: 0

Accepted

time: 1ms

memory: 3676kb

input:

output:

result:

ok 92 lines

Test #19:

score: 0

Accepted

time: 1ms

memory: 3732kb

input:

output:

result:

ok 92 lines

Test #20:

score: 0

Accepted

time: 0ms

memory: 3752kb

input:

output:

result:

ok 92 lines

Test #21:

score: 0

Accepted

time: 0ms

memory: 3700kb

input:

output:

result:

ok 94 lines

Test #22:

score: 0

Accepted

time: 1ms

memory: 3992kb

input:

output:

result:

ok 93 lines

Test #23:

score: 0

Accepted

time: 1ms

memory: 3700kb

input:

output:

result:

ok 92 lines

Test #24:

score: 0

Accepted

time: 1ms

memory: 3700kb

input:

output:

result:

ok 92 lines

Test #25:

score: 0

Accepted

time: 1ms

memory: 3756kb

input:

output:

result:

ok 92 lines

Test #26:

score: 0

Accepted

time: 1ms

memory: 3692kb

input:

output:

result:

ok 92 lines

Test #27:

score: 0

Accepted

time: 1ms

memory: 3692kb

input:

output:

result:

ok 139 lines

Test #28:

score: 0

Accepted

time: 1ms

memory: 3688kb

input:

output:

result:

ok 149 lines

Subtask #2:

score: 2

Accepted

Test #29:

score: 2

Accepted

time: 0ms

memory: 3508kb

input:

output:

result:

ok 147 lines

Test #30:

score: 0

Accepted

time: 0ms

memory: 3616kb

input:

output:

result:

ok 8 lines

Test #31:

score: 0

Accepted

time: 0ms

memory: 3700kb

input:

output:

result:

ok 92 lines

Test #32:

score: 0

Accepted

time: 0ms

memory: 3804kb

input:

output:

result:

ok 92 lines

Test #33:

score: 0

Accepted

time: 1ms

memory: 3820kb

input:

output:

result:

ok 92 lines

Test #34:

score: 0

Accepted

time: 1ms

memory: 3928kb

input:

output:

result:

ok 92 lines

Test #35:

score: 0

Accepted

time: 1ms

memory: 3696kb

input:

output:

result:

ok 92 lines

Test #36:

score: 0

Accepted

time: 1ms

memory: 3944kb

input:

output:

result:

ok 92 lines

Test #37:

score: 0

Accepted

time: 1ms

memory: 4000kb

input:

output:

result:

ok 92 lines

Test #38:

score: 0

Accepted

time: 1ms

memory: 3648kb

input:

output:

result:

ok 92 lines

Test #39:

score: 0

Accepted

time: 1ms

memory: 4004kb

input:

output:

result:

ok 92 lines

Test #40:

score: 0

Accepted

time: 1ms

memory: 3692kb

input:

1
30 150
1 23 18
3 1
3 0
1 22 12
3 5
3 0
1 16 20
3 4
3 1
3 14
1 17 5
3 1
3 6
1 5 29
3 14
1 4 29
1 29 23
3 5
3 14
3 12
1 22 14
3 8
1 40 54
1 54 42
1 38 41
3 41
1 79 83
3 79
3 84
3 82
1 67 79
3 73
3 83
1 86 95
3 122
3 117
1 112 100
3 106
3 109
3 105
1 107 101
3 120
3 175
3 135
1 155 150
3 138
1 140 13...

output:

result:

ok 92 lines

Test #41:

score: 0

Accepted

time: 1ms

memory: 3976kb

input:

output:

result:

ok 92 lines

Test #42:

score: 0

Accepted

time: 1ms

memory: 3696kb

input:

output:

result:

ok 92 lines

Test #43:

score: 0

Accepted

time: 1ms

memory: 3688kb

input:

output:

result:

ok 92 lines

Test #44:

score: 0

Accepted

time: 0ms

memory: 3708kb

input:

output:

result:

ok 92 lines

Test #45:

score: 0

Accepted

time: 0ms

memory: 3696kb

input:

output:

result:

ok 92 lines

Test #46:

score: 0

Accepted

time: 1ms

memory: 3944kb

input:

output:

result:

ok 92 lines

Test #47:

score: 0

Accepted

time: 1ms

memory: 4008kb

input:

output:

result:

ok 92 lines

Test #48:

score: 0

Accepted

time: 1ms

memory: 3760kb

input:

output:

result:

ok 92 lines

Test #49:

score: 0

Accepted

time: 0ms

memory: 3700kb

input:

output:

result:

ok 94 lines

Test #50:

score: 0

Accepted

time: 1ms

memory: 3992kb

input:

output:

result:

ok 93 lines

Test #51:

score: 0

Accepted

time: 1ms

memory: 3704kb

input:

output:

result:

ok 92 lines

Test #52:

score: 0

Accepted

time: 1ms

memory: 3984kb

input:

1
30 150
1 1 16
1 16 30
3 2
1 18 2
3 1
1 22 20
3 2
1 1 26
3 2
1 8 29
1 3 29
1 17 27
3 6
3 37
3 33
3 38
1 45 35
3 34
3 46
1 33 39
3 33
3 50
3 60
1 62 33
3 33
3 70
3 78
3 65
1 64 69
3 74
1 74 90
3 66
1 77 64
3 122
3 123
1 109 116
3 75
3 98
3 126
1 122 111
3 93
1 138 142
3 154
1 143 133
3 146
1 188 178...

output:

result:

ok 92 lines

Test #53:

score: 0

Accepted

time: 1ms

memory: 3792kb

input:

output:

result:

ok 92 lines

Test #54:

score: 0

Accepted

time: 1ms

memory: 3756kb

input:

output:

result:

ok 92 lines

Test #55:

score: 0

Accepted

time: 1ms

memory: 3916kb

input:

output:

result:

ok 139 lines

Test #56:

score: 0

Accepted

time: 1ms

memory: 3976kb

input:

output:

result:

ok 149 lines

Subtask #3:

score: 0

Time Limit Exceeded

Dependency #1:

100%

Accepted

Test #57:

score: 0

Time Limit Exceeded

input:

0
2000 6000
1 1455 291
1 291 432
1 1253 432
3 1
3 2
1 1458 1253
1 1458 689
3 7
1 597 689
1 597 1759
1 143 1759
1 1655 143
1 1655 878
1 878 817
1 817 871
3 15
3 6
1 871 1188
3 7
1 1188 815
1 815 1414
1 1414 1304
3 22
1 1257 1304
3 19
1 1257 493
1 1654 493
1 1654 327
1 327 240
1 240 1873
1 1873 1717
3...

output:

result:

Subtask #4:

score: 0

Time Limit Exceeded

Dependency #2:

100%

Accepted

Test #80:

score: 0

Time Limit Exceeded

input:

1
2000 6000
1 122 748
3 1
1 29 123
3 0
1 31 835
1 835 277
1 1395 277
3 7
1 1407 320
1 320 1690
1 1059 1690
3 10
1 113 1032
1 113 1880
1 1504 1880
1 1624 1504
1 1828 1624
3 38
1 251 1883
1 251 640
1 879 640
3 79
1 80 956
3 158
1 65 1297
1 1267 1297
1 1267 962
3 138
3 214
3 199
3 211
3 210
1 905 530
3...

output:

result:

Subtask #5:

score: 0

Skipped

Dependency #3:

Subtask #6:

score: 0

Skipped

Dependency #4:

Subtask #7:

score: 0

Skipped