QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#390093 | #2657. Bird Watching | kevinyang# | AC ✓ | 110ms | 15144kb | C++17 | 1.7kb | 2024-04-15 03:32:28 | 2024-04-15 03:32:29 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
int n,m,t;
cin >> n >> m >> t;
vector<vector<int>>g(n+1);
vector<int>ans(n+1);
vector<int>val(n+1);
t++;
for(int i = 0; i<m; i++){
int x,y;
cin >> x >> y;
x++;y++;
g[y].push_back(x);
}
vector<vector<int>>adj(n+1);
for(int i = 1; i<=n; i*=2){
if(true){
for(int j = 1; j<=n; j++){
if(j==t)continue;
for(int nxt: g[j]){
adj[j].push_back(nxt);
}
}
for(int nxt: g[t]){
if(nxt&i){
adj[t].push_back(nxt);
}
}
vector<bool>vis(n+1);
queue<int>q;
q.push(t);
while(q.size()){
int cur = q.front(); q.pop();
for(int nxt: adj[cur]){
if(vis[nxt])continue;
vis[nxt] = true;
q.push(nxt);
}
}
for(int nxt: g[t]){
if(!(nxt&i) && vis[nxt]){
ans[nxt] = -1;
}
}
for(int j = 1; j<=n; j++){
adj[j].clear();
}
}
if(true){
for(int j = 1; j<=n; j++){
if(j==t)continue;
for(int nxt: g[j]){
adj[j].push_back(nxt);
}
}
for(int nxt: g[t]){
if(!(nxt&i)){
adj[t].push_back(nxt);
}
}
vector<bool>vis(n+1);
queue<int>q;
q.push(t);
while(q.size()){
int cur = q.front(); q.pop();
for(int nxt: adj[cur]){
if(vis[nxt])continue;
vis[nxt] = true;
q.push(nxt);
}
}
for(int nxt: g[t]){
if((nxt&i) && vis[nxt]){
ans[nxt] = -1;
}
}
for(int j = 1; j<=n; j++){
adj[j].clear();
}
}
}
set<int>s;
for(int nxt: g[t]){
if(ans[nxt] == 0){
s.insert(nxt);
}
}
cout << s.size() << '\n';
for(int nxt: s){
cout << nxt-1 << '\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3852kb
input:
4 4 0 1 0 2 1 1 3 3 2
output:
1 1
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
4 5 0 1 0 2 1 1 3 3 2 2 0
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
4 5 0 1 0 2 0 0 3 3 1 3 2
output:
2 1 2
result:
ok 3 lines
Test #4:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
8 11 2 0 1 0 2 1 2 2 3 2 0 0 3 4 0 4 2 5 2 4 5 6 7
output:
2 1 5
result:
ok 3 lines
Test #5:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
3 3 2 0 1 0 2 1 2
output:
1 1
result:
ok 2 lines
Test #6:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
6 8 2 0 1 0 2 1 2 2 0 2 3 3 4 4 2 2 5
output:
2 1 4
result:
ok 3 lines
Test #7:
score: 0
Accepted
time: 65ms
memory: 11432kb
input:
100000 49999 82851 0 21680 1 1142 3 51938 3 82851 4 25039 6 63264 9 36942 12 19587 12 82851 15 82851 15 85274 19 1248 19 82851 21 46974 23 40249 24 34249 24 82851 25 68076 27 77165 27 82851 29 74245 35 40712 36 37955 38 31234 38 82851 39 75641 40 68459 46 25676 46 82851 49 25888 51 79102 51 82851 53...
output:
2 56773 91338
result:
ok 3 lines
Test #8:
score: 0
Accepted
time: 67ms
memory: 12688kb
input:
100000 50437 25225 2 46349 5 45575 9 36127 10 84232 12 9379 13 44006 16 14656 17 87422 18 9522 20 65674 22 89921 23 83299 24 36153 26 88660 27 69283 31 25688 32 28939 35 65111 38 83234 40 83865 42 55664 44 93660 45 66065 47 61561 49 64614 50 28310 56 18424 59 97956 68 48798 69 96155 75 85191 78 5686...
output:
223 416 587 1043 1499 2023 3682 3921 4265 5217 5288 5585 6021 6290 6682 6806 6977 7809 8084 8603 8895 9026 9600 9735 10404 10632 11073 12162 12386 13405 14083 14617 14849 15307 15645 15838 16226 16383 17194 18078 18794 19054 19638 19795 20073 20448 20478 20886 21133 21139 21727 21838 22628 22871 232...
result:
ok 224 lines
Test #9:
score: 0
Accepted
time: 107ms
memory: 13060kb
input:
100000 99983 61273 1 48814 1 51742 1 85303 1 91584 1 93989 4 9271 4 13191 4 76591 8 30708 8 50461 10 15454 10 30525 10 44180 10 77994 12 61170 20 51375 22 26335 22 36481 23 73110 23 74681 29 35112 29 44772 29 53627 30 10383 30 61459 31 52841 31 67294 34 45774 34 56335 34 91437 38 47916 39 5608 39 33...
output:
189 910 2029 2036 2184 2330 2490 2884 4024 4130 5263 5568 5658 6187 6441 6632 7253 7265 8473 8513 8900 9679 10020 10596 10892 11576 11633 14789 15029 15068 15313 15442 15483 16937 17983 18161 19094 19417 19955 20172 20754 20824 23022 23448 24368 24570 25431 25616 25883 26067 26898 27759 28234 29331 ...
result:
ok 190 lines
Test #10:
score: 0
Accepted
time: 110ms
memory: 12912kb
input:
100000 99743 28534 1 793 1 56308 1 63500 1 64005 1 84142 2 1181 2 12385 2 16455 2 21367 3 28534 4 7061 4 27248 4 76447 4 97568 6 7897 6 12843 6 83881 6 83906 7 28534 7 53812 7 57476 9 28534 9 78119 9 80176 12 3311 12 20243 12 79733 13 52664 13 68838 13 72679 14 24258 14 95764 14 96386 16 9343 20 250...
output:
1049 3 407 418 786 910 960 1009 1010 1060 1126 1169 1240 1351 1462 1468 1719 1722 1974 2011 2078 2100 2106 2362 2398 2399 2433 2808 2817 2824 2896 2943 2979 3106 3108 3263 3364 3542 3566 3569 3572 3645 3708 3871 4106 4129 4174 4234 4351 4376 4407 4411 4736 4830 4869 4937 5001 5119 5134 5291 5301 555...
result:
ok 1050 lines
Test #11:
score: 0
Accepted
time: 62ms
memory: 12124kb
input:
100000 99900 20066 1 6411 1 18249 1 22420 1 89993 10 20857 10 77435 10 77634 10 81968 10 82021 10 82384 10 91230 10 94465 10 96023 12 24320 12 29869 12 37999 12 68729 26 5404 26 28750 26 52022 26 67966 26 71502 26 72564 26 86094 26 86633 26 88220 32 1509 32 2313 32 12231 32 14346 32 24125 32 25247 3...
output:
0
result:
ok single line: '0'
Test #12:
score: 0
Accepted
time: 64ms
memory: 12168kb
input:
100000 98874 77194 3 2350 3 4520 3 8985 3 17833 3 17956 3 26060 3 33183 3 51688 3 64260 3 69710 3 71505 3 77194 3 96220 10 16024 10 16573 10 16955 10 53848 10 76733 10 77194 10 82761 10 88105 10 90985 10 91909 10 96417 10 98272 16 20544 16 20571 16 27690 16 29651 16 33458 16 74234 16 74621 16 81893 ...
output:
1 72921
result:
ok 2 lines
Test #13:
score: 0
Accepted
time: 70ms
memory: 14736kb
input:
100000 84023 32012 1 50185 2 5476 3 49231 4 50628 5 61997 6 19740 8 55838 9 65298 10 97105 11 22405 12 46836 13 58142 14 42953 15 49233 16 96942 17 52452 18 52312 19 61028 20 68360 21 9720 22 47111 24 12007 25 57471 26 27810 28 80728 31 81920 34 18651 35 57197 36 46400 37 70433 38 8554 39 95951 40 9...
output:
7 4728 11748 42348 43852 76667 93418 97301
result:
ok 8 lines
Test #14:
score: 0
Accepted
time: 67ms
memory: 15016kb
input:
100000 90298 62025 1 36825 2 50365 3 91850 4 17171 5 29085 6 31969 7 60418 8 30680 9 84590 10 96577 11 74250 13 90022 14 8897 15 68823 16 21239 17 48361 18 65354 19 94606 20 80738 21 55640 22 11569 23 83725 24 19566 25 59908 26 10150 27 34079 28 44987 29 75524 30 8054 31 75025 33 70321 34 2409 35 46...
output:
127 675 1415 1893 5509 5529 6321 6431 6876 6878 7002 7619 9425 9525 10280 10833 11095 12106 12820 12876 13203 13512 13519 14379 14490 15025 16660 17881 18450 18558 19130 19678 21435 22366 22474 25745 26424 27118 27657 28593 29067 29147 29220 30391 30419 30623 31110 32627 33327 33507 33682 33882 3437...
result:
ok 128 lines
Test #15:
score: 0
Accepted
time: 93ms
memory: 15144kb
input:
100000 97998 71702 1 98311 2 81773 3 40482 4 32761 6 26940 7 43090 8 58974 9 35064 10 41593 11 37271 12 52803 12 55275 12 86452 13 27109 13 29324 14 27376 15 86832 16 60234 17 43058 18 61933 19 90028 20 34396 22 93225 23 26523 24 2755 25 2044 27 36895 28 34853 29 77501 30 12959 31 41971 32 61578 34 ...
output:
4 6392 10074 36504 93249
result:
ok 5 lines