QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #415682 | #7362. 割 | juan_123 | 0 | 115ms | 12372kb | C++14 | 692b | 2024-05-21 08:40:38 | 2024-11-23 17:01:01 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
mt19937 rnd(time(0));
int ok[100005];
vector<int>p[200005];
int n,m;
const int M = 1000000;
int ans = 0;
signed main(){
cin >> n >> m;
for(int i = 1;i<=m;i++){
int a,b;cin >>a >> b;
p[a].push_back(b),p[b].push_back(a);
}
for(int i = 0;i<min(n*10,M);i++){
// if(ans>=(m+1)/2)break;
int now = rnd()%n+1,tt = 0,ww;
// cout << now << endl;
for(int x:p[now])tt+=(ok[x]==ok[now]),ww+=(ok[x]!=ok[now]);
if(tt>ww){
ok[now]^=1;ans = ans-ww+tt;
}
}
assert(ans>=(m+1)/2);
// cout << ans << endl;
for(int i = 1;i<=n;i++)cout << ok[i] << ' ';cout<< endl;
return 0;
}/*
4 6
1 2
1 3
1 4
2 3
2 4
3 4
*/
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 0
Runtime Error
input:
16 195777 7 4 2 5 10 1 4 16 9 3 1 3 9 8 11 5 9 4 1 12 9 4 6 1 2 7 6 1 14 4 2 16 1 6 5 11 16 3 15 8 16 12 1 4 8 3 9 16 11 8 7 16 16 1 1 7 3 16 4 16 9 12 3 9 16 11 4 14 12 5 16 12 1 8 2 16 4 7 11 7 4 13 5 8 1 4 6 4 2 15 6 5 5 4 4 8 1 9 14 7 8 5 7 1 11 9 12 14 5 2 9 13 4 16 1 7 5 3 13 6 15 8 7 1 1 5 6 ...
output:
result:
Test #2:
score: 0
Runtime Error
input:
18 157831 6 14 14 1 12 17 13 10 8 18 18 15 15 6 2 12 3 15 12 13 17 12 7 8 8 14 1 17 7 4 2 7 12 11 9 13 10 13 15 6 15 13 1 4 6 1 16 15 16 4 7 17 17 5 8 13 18 7 9 15 10 2 12 7 13 1 11 7 6 17 12 3 7 1 5 1 1 11 9 1 12 16 18 7 9 7 1 10 13 7 6 13 18 16 17 4 1 8 17 18 18 5 3 16 18 15 3 5 2 3 12 14 6 12 17 ...
output:
result:
Test #3:
score: 0
Runtime Error
input:
19 198538 3 4 19 5 11 19 7 4 4 13 2 16 12 17 10 15 17 8 5 6 4 15 8 3 12 17 2 10 5 16 3 5 12 11 9 4 2 9 17 3 2 12 8 9 17 1 4 12 9 1 1 4 19 3 8 2 19 15 8 16 3 15 13 4 18 15 11 16 6 18 12 13 7 1 15 2 15 11 14 18 10 5 6 2 7 1 12 5 7 13 12 10 10 12 17 13 10 12 3 11 6 11 8 18 13 5 11 15 11 4 19 10 13 16 1...
output:
result:
Test #4:
score: 0
Runtime Error
input:
83589 185404 43233 56681 3323 66360 73015 30450 53246 1899 78495 28463 53683 41361 69084 10045 74137 44389 62334 49623 80530 50173 40547 25069 50011 28064 11982 16598 38051 72169 60920 75346 15561 27129 15586 377 5254 42928 42181 29431 7640 39932 55204 20070 69987 19176 10794 76339 53208 17098 71742...
output:
result:
Test #5:
score: 0
Runtime Error
input:
89606 189269 38986 50381 52944 21966 76438 76554 26245 36307 37556 65697 12403 88456 4276 23672 60127 77809 29339 73238 4985 18809 71698 84894 62958 87185 18137 9825 604 60020 39768 87394 74584 44463 38609 58296 14612 48625 86908 79587 2151 37614 47272 21206 83180 79226 77511 3510 69744 81504 29102 ...
output:
result:
Test #6:
score: 0
Runtime Error
input:
97464 189549 53251 12158 81432 30655 10095 21770 84832 53850 97262 29895 46488 91881 17252 10769 51795 72927 17345 38319 76129 91725 22467 55018 6907 47653 41429 21232 91453 36452 82095 90201 79595 23937 96518 32359 24885 49205 60454 19597 15788 80825 8990 89800 89785 55912 60357 14318 12642 62541 3...
output:
result:
Test #7:
score: 0
Runtime Error
input:
78481 194415 46092 61133 36226 8857 58328 21579 1393 19800 11105 29638 26132 63170 31475 12911 56125 75060 21007 31451 2879 48784 71502 40714 39031 70254 11276 1256 27927 63170 43672 117 38624 46951 53669 3096 55546 28297 44471 76465 76177 24888 27216 46166 35632 8323 48158 8139 36344 58236 7752 602...
output:
result:
Test #8:
score: 0
Runtime Error
input:
82362 195975 3742 65961 5178 6770 15224 68674 68042 14663 73212 44298 36875 25866 32790 6372 23000 53401 43229 46662 55722 2656 71053 76740 6319 29299 63423 68621 71538 47098 77003 76530 3777 44939 65908 48166 15181 47784 12041 64370 51137 63848 12252 28219 68481 6821 51724 59828 46612 51082 45936 1...
output:
result:
Test #9:
score: 0
Wrong Answer
time: 115ms
memory: 12372kb
input:
81379 182841 56468 44868 53031 43223 14309 65690 40586 22789 12604 66347 47330 22208 57571 24404 63464 18262 25011 45667 16231 24698 71524 37304 34135 78382 12631 76042 2735 54607 65003 23334 75436 73990 65807 10768 28435 66699 35592 52725 66181 27623 29161 32647 59791 44444 17516 61276 57950 44110 ...
output:
0 1 0 0 1 1 0 1 1 1 1 1 0 1 1 1 0 1 1 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0 0 1 1 0 1 1 1 1 1 1 0 1 1 0 1 1 0 1 0 1 1 0 1 0 0 1 1 1 0 1 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 0 0 1 0 1 0 0 0 1 1 1 0 0 1 1 1 0 1 0 0 0 1 0 1 0 1 1 1 1 0 1 0 0 0 0 1 0 0 0 0 1 1 1 0 1 0 1 0 1 1 1 0 0 1 0 0 1 1 1 0 1 1 1 0 ...
result:
wrong answer Your solution is wrong!
Test #10:
score: 0
Runtime Error
input:
91356 198560 71601 29245 47552 90107 57700 85176 2337 24599 43240 21000 61189 48015 52025 72430 30647 84579 42035 82292 58729 88305 14473 38629 77323 20684 52465 26152 33826 11367 53639 32806 43946 24220 30783 14226 89836 53714 35139 20177 8549 12231 52673 15018 803 45176 22484 31182 1598 68139 2570...