QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#827429#121. Bitaro's PartyRedDiamond#0 13ms4676kbC++112.7kb2024-12-22 22:53:132024-12-22 22:53:14

Judging History

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

  • [2024-12-22 22:53:14]
  • 评测
  • 测评结果:0
  • 用时:13ms
  • 内存:4676kb
  • [2024-12-22 22:53:13]
  • 提交

answer

#include <bits/stdc++.h>


using namespace std;


#define ll long long
#define ld long double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()


const int K = 320;


int n, m, q;
vector<vector<int>> g, gg;
vector<vector<pair<int, int>>> closest;
vector<int> vis, ord, dp;


void dfs(int u) {
    vis[u] = 1;
    for (auto v : g[u]) {
        if (!vis[v]) {
            dfs(v);
        }
    }
    ord.push_back(u);
}


void merge(vector<pair<int, int>> &a, vector<pair<int, int>> b) {
    vector<pair<int, int>> c = a;
    for (auto i : b) {
        c.push_back({i.first + 1, i.second});
    }
    sort(rall(c));
    vector<pair<int, int>> f;
    for (int i = 0; i < c.size(); i += 1) {
        if (!f.empty() && c[i].second == f.back().second) {
            continue;
        }
        f.push_back({c[i].first, c[i].second});
        if (f.size() > K) {
            break;
        }
    }
    a = f;
}


void dfs2(int u) {
    for (auto v : gg[u]) {
        dp[v] = max(dp[v], dp[u] + 1);
        dfs2(v);
    }
}


int32_t main() {
    if (1) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
	}
	cin >> n >> m >> q;
    g.resize(n + 1);
    gg.resize(n + 1);
    for (int i = 1; i <= m; i += 1) {
        int e, s;
        cin >> e >> s;
        g[e].push_back(s);
        gg[s].push_back(e);
    }
    vis.assign(n + 1, 0);
    for (int i = 1; i <= n; i += 1) {
        if (!vis[i]) {
            dfs(i);
        }
    }
    reverse(all(ord));
    closest.resize(n + 1);
    for (auto i : ord) {
        closest[i].push_back({0, i});
        for (auto v : gg[i]) {
            merge(closest[i], closest[v]);
        }
    }
   
    dp.resize(n + 1);
    vector<int> blocked(n + 1, 0);
    for (int iq = 1; iq <= q; iq += 1) {
        int t, y;
        cin >> t >> y;
        vector<int> v;
        for (int j = 0; j < y; j += 1) {
            int x;
            cin >> x;
            v.push_back(x);
            blocked[x] = 1;
        }
        if (y > K) {
            dp[t] = 0;
            dfs2(t);
            int ans = -1;
            for (int i = 1; i <= n; i += 1) {
                if (blocked[i] == 0) {
                    ans = max(ans, dp[i]);
                }
            }
            cout << ans << "\n";
        } else {
            int ans = -1;
            for (auto i : closest[t]) {
                if (!blocked[i.second]) {
                    ans = i.first;
                    break;
                }
            }
            cout << ans << "\n";
        }
        for (auto i : v) {
            blocked[i] = 0;
        }
    }
    return 0;
}

详细

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

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

input:

1 0 1
1 0

output:

0

result:

ok single line: '0'

Test #2:

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

input:

1 0 1
1 1 1

output:

-1

result:

ok single line: '-1'

Test #3:

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

input:

2 1 1
1 2
1 2 1 2

output:

-1

result:

ok single line: '-1'

Test #4:

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

input:

2 1 1
1 2
1 1 1

output:

-1

result:

ok single line: '-1'

Test #5:

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

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: 10ms
memory: 4576kb

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: 7ms
memory: 4596kb

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: 0
Time Limit Exceeded

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:


result:


Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%