QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#224020#7503. Too Many EdgesDAleksaAC ✓1813ms11228kbC++141.5kb2023-10-22 23:02:592023-10-22 23:02:59

Judging History

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

  • [2023-10-22 23:02:59]
  • 评测
  • 测评结果:AC
  • 用时:1813ms
  • 内存:11228kb
  • [2023-10-22 23:02:59]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 5e4 + 10;
int n, m;
set<int> g[N];
int dp[N];
bool mark[N];
vector<int> path;

int ask(int u, int v) {
    cout << "? " << u << " " << v << endl;
    int x;
    cin >> x;
    return x;
}

void dfs(int u) {
    if(mark[u]) return;
    mark[u] = true;
    for(int v : g[u]) {
        if(mark[v]) {
            dp[u] = max(dp[u], dp[v] + 1);
            continue;
        }
        dfs(v);
        dp[u] = max(dp[u], dp[v] + 1);
    }
}

void dfs2(int u) {
    path.push_back(u);
    for(int v : g[u]) {
        if(dp[v] == dp[u] - 1) {
            dfs2(v);
            break;
        }
    }
}

int main() {
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].insert(v);
    }
    while(true) {
        for(int i = 1; i <= n; i++) {
            mark[i] = false;
            dp[i] = 0;
        }
        for(int i = 1; i <= n; i++) {
            if(mark[i]) continue;
            dfs(i);
        }
        path.clear();
        int mx = 1;
        for(int i = 2; i <= n; i++) if(dp[i] > dp[mx]) mx = i;
        dfs2(mx);
        bool ok = true;
        for(int i = 1; i < path.size(); i++) {
            if(ask(path[i - 1], path[i]) == 0) {
                g[path[i - 1]].erase(path[i]);
                ok = false;
                break;
            }
        }
        if(ok) {
            cout << "! " << path.size() - 1;
            return 0;
        }
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 6008kb

input:

5 5
1 2
1 3
2 5
3 4
4 5
1
0
1
1

output:

? 1 3
? 3 4
? 1 2
? 2 5
! 2

result:

ok Correct answer

Test #2:

score: 0
Accepted
time: 5ms
memory: 6100kb

input:

230 470
212 98
107 123
116 72
158 83
135 111
78 123
221 217
214 203
28 221
229 3
111 127
128 13
125 116
180 78
175 191
182 99
194 6
12 83
209 29
169 129
192 208
145 38
33 86
104 85
145 82
38 82
193 153
109 41
199 194
89 72
161 227
36 177
13 141
173 110
212 77
155 81
87 82
104 172
148 182
170 222
68 ...

output:

? 147 145
? 145 53
? 53 178
? 178 223
? 223 101
? 101 195
? 195 38
? 38 81
? 81 207
? 207 87
? 87 82
? 82 137
? 137 196
? 196 15
? 15 113
? 113 20
? 20 40
? 40 227
? 227 224
? 224 56
? 56 175
? 175 167
? 167 176
? 176 211
? 211 112
? 112 62
? 62 135
? 135 198
? 198 201
? 201 131
? 131 191
? 191 205
...

result:

ok Correct answer

Test #3:

score: 0
Accepted
time: 1813ms
memory: 11140kb

input:

32500 94033
5330 27480
6016 11178
29267 1197
5789 21547
23714 25915
15710 17107
16950 10411
13998 15431
11106 14400
927 25530
18890 3967
11978 17027
2434 683
20135 5988
10802 22709
29179 6971
24499 12498
10977 795
30366 3120
4051 21131
25859 15273
19124 10952
14475 11243
11810 1265
7311 2036
385 158...

output:

? 30795 20050
? 20050 15862
? 15862 1668
? 1668 22076
? 22076 17815
? 17815 28912
? 28912 25379
? 25379 11968
? 11968 31990
? 31990 14693
? 14693 6640
? 6640 17937
? 17937 7124
? 7124 29226
? 29226 28558
? 28558 18098
? 18098 4847
? 4847 4189
? 4189 20645
? 20645 10285
? 10285 9077
? 9077 26952
? 26...

result:

ok Correct answer

Test #4:

score: 0
Accepted
time: 1469ms
memory: 11228kb

input:

36000 90053
30475 13651
22999 24861
5951 9742
17517 23989
18959 6538
19553 11038
25437 54
12236 7008
3442 9514
7624 30567
5054 23318
21048 4679
6580 31177
12845 5309
31293 10448
25535 15480
7341 8165
23069 17566
25018 15241
706 18925
8811 14849
30704 24536
10309 25098
27442 20863
33703 13600
17627 2...

output:

? 27417 18458
? 18458 24103
? 24103 35222
? 35222 31782
? 31782 18244
? 18244 17499
? 17499 23130
? 23130 30211
? 30211 27504
? 27417 18458
? 18458 24103
? 24103 35222
? 35222 31782
? 31782 18244
? 18244 17499
? 17499 23130
? 23130 30211
? 30211 12381
? 12381 13269
? 13269 21585
? 21585 22431
? 2243...

result:

ok Correct answer

Test #5:

score: 0
Accepted
time: 547ms
memory: 10328kb

input:

1000 90666
693 375
340 106
283 416
832 864
597 973
285 987
662 444
384 672
508 47
794 463
24 133
230 954
48 584
540 707
87 218
264 845
586 992
247 597
654 706
306 812
294 386
533 120
999 942
879 981
203 78
678 341
534 577
612 281
509 41
199 567
311 661
936 211
693 750
44 7
334 375
224 859
393 228
45...

output:

? 555 880
? 880 40
? 555 40
? 40 553
? 553 569
? 569 651
? 555 40
? 40 553
? 553 651
? 651 180
? 555 40
? 40 553
? 553 774
? 774 180
? 555 40
? 40 553
? 553 651
? 651 399
? 399 122
? 122 758
? 758 365
? 555 40
? 40 553
? 553 774
? 774 104
? 104 602
? 602 331
? 331 15
? 555 40
? 40 553
? 553 774
? 77...

result:

ok Correct answer

Test #6:

score: 0
Accepted
time: 482ms
memory: 10740kb

input:

10000 99884
6716 7602
5917 3638
9554 2505
7904 6893
8915 7173
1819 2730
4845 9714
7482 4797
2183 781
5041 5987
9537 993
8484 3337
346 3291
6062 7613
1286 5687
9991 498
7433 4952
9597 5802
1137 8805
8083 6147
4717 5900
3773 118
3752 9992
9395 8969
1966 9404
2766 6267
1893 404
4181 5691
4387 8020
7127...

output:

? 7209 3286
? 3286 5533
? 3286 275
? 5533 8509
? 275 2954
? 2954 3567
? 3567 9762
? 8509 8293
? 8293 8990
? 8990 6487
? 6487 9659
? 9659 424
? 5533 9660
? 9660 5929
? 5533 9660
? 9660 3459
? 3459 2255
? 275 4517
? 4517 9156
? 9156 8726
? 8726 3095
? 3095 432
? 432 5379
? 5379 7849
? 7849 3361
? 3286...

result:

ok Correct answer

Test #7:

score: 0
Accepted
time: 606ms
memory: 10820kb

input:

40000 99987
234 24171
17105 36233
5533 12466
38544 18454
35367 21436
9444 8046
11745 26615
32997 35770
11004 25416
39988 7619
30595 16666
38275 20547
26230 11888
29603 5464
18435 37346
10469 19694
24129 29204
5336 37947
86 38735
31032 21467
14175 37267
38749 6213
38615 13802
15736 4270
25539 38284
1...

output:

? 19062 27908
? 27908 22029
? 22029 20140
? 20140 1478
? 1478 8191
? 8191 567
? 22029 39181
? 19062 21807
? 21807 20093
? 19062 21807
? 21807 37248
? 37248 17471
? 39181 405
? 405 18304
? 567 29357
? 29357 15081
? 15081 20173
? 18304 9978
? 9978 4478
? 19062 21953
? 20093 39920
? 39920 29746
? 29746...

result:

ok Correct answer