QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#534202#121. Bitaro's Partyisirazeev0 180ms86500kbC++202.2kb2024-08-26 21:56:402024-08-26 21:56:40

Judging History

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

  • [2024-08-26 21:56:40]
  • 评测
  • 测评结果:0
  • 用时:180ms
  • 内存:86500kb
  • [2024-08-26 21:56:40]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
#define int long long

const int N = (int) 1e5 + 10;
const int C = 1300;

const int INF = (int) 1e18;

set<pair<int, int>> biggest[N];

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int n, m, q;
    cin >> n >> m >> q;
    vector<int> rev_g[n];
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        rev_g[v - 1].emplace_back(u - 1);
    }
    for (int i = 0; i < n; i++) {
        biggest[i].insert({0, i});
        set<int> was;
        map<int, int> dist;
        dist[i] = 0;
        was.insert(i);
        for (int j: rev_g[i]) {
            for (auto [c, ind]: biggest[j]) {
                if (was.find(ind) != was.end()) {
                    if (dist[ind] < c + 1) {
                        biggest[i].erase({dist[ind], ind});
                        dist[ind] = c + 1;
                        biggest[i].insert({c + 1, ind});
                    }
                } else {
                    biggest[i].insert({c + 1, ind});
                }
                if ((int) biggest[i].size() > C) biggest[i].erase(biggest[i].begin());
            }
        }
    }
    for (int _ = 0; _ < q; _++) {
        int T, Y;
        cin >> T >> Y;
        T--;
        set<int> block;
        for (int i = 0; i < Y; i++) {
            int A;
            cin >> A;
            block.insert(A - 1);
        }
        if (Y >= C) {
            int dp[n];
            for (int i = 0; i < n; i++) dp[i] = -INF;
            dp[T] = 0;
            for (int i = T; i >= 0; i--) {
                for (int j: rev_g[i])
                    dp[j] = max(dp[j], dp[i] + 1);
            }
            int res = -1;
            for (int i = 0; i < n; i++) if (block.find(i) == block.end()) res = max(res, dp[i]);
            cout << res << "\n";
            continue;
        } else {
            int res = -1;
            for (auto [val, ind]: biggest[T]) {
                if (block.find(ind) == block.end())
                    res = max(res, val);
            }
            cout << res << "\n";
        }
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 7
Accepted
time: 2ms
memory: 8472kb

input:

1 0 1
1 0

output:

0

result:

ok single line: '0'

Test #2:

score: 7
Accepted
time: 2ms
memory: 8176kb

input:

1 0 1
1 1 1

output:

-1

result:

ok single line: '-1'

Test #3:

score: 7
Accepted
time: 0ms
memory: 8436kb

input:

2 1 1
1 2
1 2 1 2

output:

-1

result:

ok single line: '-1'

Test #4:

score: 7
Accepted
time: 2ms
memory: 8500kb

input:

2 1 1
1 2
1 1 1

output:

-1

result:

ok single line: '-1'

Test #5:

score: 7
Accepted
time: 18ms
memory: 16020kb

input:

1000 2000 1
66 427
211 505
213 674
56 131
180 883
127 167
228 262
42 50
386 688
346 943
170 396
127 150
169 192
253 706
96 497
141 277
317 711
792 802
244 469
24 702
135 252
31 764
52 95
701 900
473 832
510 691
14 474
158 488
422 491
228 897
318 622
195 548
479 626
525 728
53 109
133 854
392 416
34 ...

output:

12

result:

ok single line: '12'

Test #6:

score: 7
Accepted
time: 13ms
memory: 14716kb

input:

1000 2000 1
762 826
799 904
17 20
56 733
46 416
261 768
196 392
121 144
14 69
244 625
331 485
331 383
502 635
107 914
131 274
288 495
70 103
417 934
318 535
775 930
9 113
250 677
82 200
2 4
36 77
367 553
8 31
633 712
21 179
484 963
117 146
207 413
685 787
561 903
508 710
834 912
4 76
196 977
355 394...

output:

14

result:

ok single line: '14'

Test #7:

score: 7
Accepted
time: 17ms
memory: 14944kb

input:

1000 2000 1
86 222
107 710
207 983
80 929
4 5
685 963
758 769
228 274
34 35
14 26
614 786
383 679
41 62
125 522
619 851
175 359
253 492
127 182
27 367
111 221
170 453
519 612
137 191
254 301
53 148
214 824
31 374
402 795
25 26
177 461
301 614
574 798
82 104
137 625
86 575
32 364
37 183
131 270
113 6...

output:

2

result:

ok single line: '2'

Test #8:

score: 7
Accepted
time: 178ms
memory: 86500kb

input:

1000 2000 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52...

output:

181

result:

ok single line: '181'

Test #9:

score: 7
Accepted
time: 173ms
memory: 86180kb

input:

1000 2000 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52...

output:

627

result:

ok single line: '627'

Test #10:

score: 0
Wrong Answer
time: 180ms
memory: 86100kb

input:

1000 2000 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52...

output:

-1

result:

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

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%