QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#226285 | #7503. Too Many Edges | SolitaryDream# | AC ✓ | 1545ms | 13904kb | C++17 | 1.2kb | 2023-10-25 19:27:24 | 2023-10-25 19:27:25 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,s,t) for(int i=(s),_t=(t); i<=_t; ++i)
typedef long long ll;
const int N=1e5+50;
set<int> E[N];
int deg[N];
int dis[N],fr[N];
int n,m;
bool solve() {
queue<int> Q;
FOR(i,1,n) deg[i]=dis[i]=fr[i]=0;
FOR(i,1,n) for(auto j: E[i]) deg[j]++;
FOR(i,1,n) if(deg[i]==0) Q.push(i);
while(Q.size()) {
int x=Q.front();
Q.pop();
for(auto y: E[x]) {
if(dis[x]+1>dis[y]) {
dis[y]=dis[x]+1;
fr[y]=x;
}
if(!--deg[y]) Q.push(y);
}
}
int p=1;
FOR(i,2,n) if(dis[i]>dis[p]) p=i;
int res=dis[p];
while(fr[p]) {
cout << "? " << fr[p] << ' ' << p << endl;
int e;
cin >> e;
if(!e) {
E[fr[p]].erase(p);
return 0;
}
p=fr[p];
}
cout << "! " << res << endl;
return 1;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
FOR(i,1,m) {
int x,y;
cin >> x >> y;
E[x].insert(y);
}
while(!solve());
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 8648kb
input:
5 5 1 2 1 3 2 5 3 4 4 5 1 0 1 1
output:
? 4 5 ? 3 4 ? 2 5 ? 1 2 ! 2
result:
ok Correct answer
Test #2:
score: 0
Accepted
time: 2ms
memory: 8316kb
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:
? 124 151 ? 73 124 ? 210 73 ? 99 210 ? 182 99 ? 148 182 ? 97 148 ? 92 97 ? 136 92 ? 31 136 ? 171 31 ? 184 171 ? 208 184 ? 146 208 ? 68 146 ? 203 68 ? 4 203 ? 74 4 ? 219 74 ? 88 219 ? 157 88 ? 43 157 ? 126 43 ? 228 126 ? 16 228 ? 213 16 ? 214 213 ? 133 214 ? 37 133 ? 216 37 ? 32 216 ? 122 32 ? 49 122...
result:
ok Correct answer
Test #3:
score: 0
Accepted
time: 1545ms
memory: 13084kb
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:
? 31700 11512 ? 11240 31700 ? 30299 11240 ? 29669 30299 ? 14903 29669 ? 29261 14903 ? 3190 29261 ? 29839 3190 ? 2312 29839 ? 851 2312 ? 30214 851 ? 21823 30214 ? 26688 21823 ? 23280 26688 ? 7744 23280 ? 29774 7744 ? 12608 29774 ? 28630 12608 ? 23887 28630 ? 27560 23887 ? 12947 27560 ? 26396 12947 ? ...
result:
ok Correct answer
Test #4:
score: 0
Accepted
time: 1191ms
memory: 12932kb
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:
? 5617 519 ? 23733 5617 ? 3426 23733 ? 23793 3426 ? 23558 23793 ? 12631 23558 ? 18270 12631 ? 18024 18270 ? 10796 18024 ? 29421 10796 ? 25898 29421 ? 1156 25898 ? 18733 1156 ? 405 18733 ? 2738 405 ? 10094 2738 ? 20561 10094 ? 26090 20561 ? 22975 26090 ? 33565 22975 ? 9571 33565 ? 16155 9571 ? 26137 ...
result:
ok Correct answer
Test #5:
score: 0
Accepted
time: 958ms
memory: 12576kb
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:
? 544 60 ? 615 544 ? 763 615 ? 386 763 ? 41 386 ? 317 41 ? 871 317 ? 544 60 ? 564 544 ? 82 564 ? 182 82 ? 746 182 ? 317 746 ? 249 317 ? 544 60 ? 564 544 ? 82 564 ? 182 82 ? 746 182 ? 687 746 ? 249 687 ? 21 249 ? 544 60 ? 564 544 ? 82 564 ? 386 82 ? 544 60 ? 564 544 ? 507 564 ? 823 507 ? 544 60 ? 163...
result:
ok Correct answer
Test #6:
score: 0
Accepted
time: 896ms
memory: 13492kb
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:
? 1203 5183 ? 4758 1203 ? 4758 1980 ? 5026 4758 ? 3086 5026 ? 8773 3086 ? 9571 5629 ? 3531 9571 ? 5039 3531 ? 8773 5039 ? 3561 8773 ? 6669 3561 ? 7917 5629 ? 6347 7917 ? 4222 6347 ? 7476 5064 ? 5067 7476 ? 9518 5067 ? 5121 9518 ? 6724 5532 ? 654 6203 ? 8097 7030 ? 3993 8097 ? 9627 3993 ? 5121 9627 ?...
result:
ok Correct answer
Test #7:
score: 0
Accepted
time: 833ms
memory: 13904kb
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:
? 32318 14482 ? 9083 32318 ? 3487 9083 ? 16352 3487 ? 20009 25528 ? 23120 20009 ? 9498 23120 ? 32081 9498 ? 38318 32081 ? 12482 326 ? 15928 12482 ? 20952 15928 ? 22368 1702 ? 369 22368 ? 18978 369 ? 1980 18978 ? 10411 1980 ? 10441 10411 ? 16052 10441 ? 14833 16052 ? 26759 14833 ? 18081 26759 ? 25765...
result:
ok Correct answer