QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#623226 | #8406. Alchemik Bajtazar [B] | chenxinyang2006 | 0 | 23ms | 7668kb | C++20 | 2.1kb | 2024-10-09 10:44:19 | 2024-10-09 10:44:19 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;
template <class T>
void chkmax(T &x,T y){
if(x < y) x = y;
}
template <class T>
void chkmin(T &x,T y){
if(x > y) x = y;
}
inline int popcnt(int x){
return __builtin_popcount(x);
}
inline int ctz(int x){
return __builtin_ctz(x);
}
/*ll power(ll p,int k = mod - 2){
ll ans = 1;
while(k){
if(k % 2 == 1) ans = ans * p % mod;
p = p * p % mod;
k /= 2;
}
return ans;
}*/
int n,m;
vector <int> G[30005];
struct info{
int op,u,v;
};
vector <info> ans,output;
int fa[30005];
vector <int> ord;
void dfs(int u){
ord.eb(u);
for(int v:G[u]){
if(fa[v] == -1){
fa[v] = u;
dfs(v);
}
}
}
int chk(int u,int v){
int t = lower_bound(G[u].begin(),G[u].end(),v) - G[u].begin();
if(t < SZ(G[u]) && G[u][t] == v) return 1;
return 0;
}
void solver(){
rep(u,1,n) sort(G[u].begin(),G[u].end());
fill(fa,fa + n + 1,-1);
fa[1] = 0;
dfs(1);
rep(i,2,n){
int u = ord[i - 1];
if(!chk(1,u)) ans.push_back({1,1,u});
}
rep(u,2,n){
for(int v:G[u]) if(v > u) ans.push_back({0,u,v});
}
}
int main(){
// freopen("test.in","r",stdin);
scanf("%d%d",&n,&m);
rep(i,1,m){
int u,v;
scanf("%d%d",&u,&v);
G[u].eb(v);G[v].eb(u);
}
solver();
swap(ans,output);
rep(u,1,n) G[u].clear();
scanf("%d",&m);
rep(i,1,m){
int u,v;
scanf("%d%d",&u,&v);
G[u].eb(v);G[v].eb(u);
}
solver();
reverse(ans.begin(),ans.end());
for(info &I:ans){
I.op ^= 1;
output.eb(I);
}
printf("%d\n",SZ(output));
for(info &I:output){
if(!I.op) printf("- ");
else printf("+ ");
printf("%d %d\n",I.u,I.v);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 1
Accepted
time: 1ms
memory: 3768kb
input:
2 1 2 1 1 1 2
output:
0
result:
ok
Test #2:
score: 1
Accepted
time: 1ms
memory: 3836kb
input:
3 2 3 1 2 1 2 1 2 1 3
output:
0
result:
ok
Test #3:
score: 1
Accepted
time: 0ms
memory: 3904kb
input:
3 2 3 1 3 2 3 2 3 3 1 1 2
output:
3 + 1 2 - 2 3 + 2 3
result:
ok
Test #4:
score: 1
Accepted
time: 0ms
memory: 3768kb
input:
3 3 2 3 1 3 1 2 3 1 2 2 3 1 3
output:
2 - 2 3 + 2 3
result:
ok
Test #5:
score: 1
Accepted
time: 0ms
memory: 3828kb
input:
5 7 5 4 2 3 5 3 1 5 2 5 1 2 4 3 8 4 3 4 5 1 2 1 5 5 2 3 5 1 4 4 2
output:
13 + 1 3 + 1 4 - 2 3 - 2 5 - 3 4 - 3 5 - 4 5 + 4 5 + 3 5 + 3 4 + 2 5 + 2 4 - 1 3
result:
ok
Test #6:
score: 0
Wrong Answer
time: 0ms
memory: 3896kb
input:
7 6 5 6 2 7 6 2 1 7 3 1 7 4 6 3 2 1 7 6 2 5 6 4 6 1 4
output:
16 + 1 2 + 1 6 + 1 5 + 1 4 - 2 6 - 2 7 - 4 7 - 5 6 + 5 6 + 4 6 + 2 6 + 2 3 - 1 5 - 1 6 - 1 2 - 1 3
result:
wrong answer
Subtask #2:
score: 0
Wrong Answer
Test #10:
score: 0
Wrong Answer
time: 1ms
memory: 3964kb
input:
30 146 20 7 15 14 9 25 11 2 9 7 28 29 3 1 14 24 26 15 9 24 5 11 15 28 12 13 2 4 23 12 27 1 13 10 15 18 10 4 7 1 30 10 21 2 5 15 15 21 6 17 1 17 13 1 18 12 6 29 11 30 20 8 25 3 30 6 14 7 1 20 15 13 22 28 20 21 22 25 23 1 21 5 12 3 27 29 24 7 25 26 1 30 30 14 4 28 24 5 22 23 20 11 13 5 10 21 23 16 10 ...
output:
250 + 1 6 + 1 4 + 1 2 + 1 11 + 1 5 + 1 8 + 1 14 + 1 15 + 1 9 + 1 19 + 1 12 + 1 18 + 1 22 + 1 24 + 1 26 - 2 4 - 2 11 - 2 19 - 2 21 - 3 7 - 3 10 - 3 12 - 3 23 - 3 24 - 3 25 - 4 5 - 4 6 - 4 8 - 4 9 - 4 10 - 4 16 - 4 19 - 4 20 - 4 28 - 4 30 - 5 11 - 5 13 - 5 15 - 5 17 - 5 19 - 5 21 - 5 24 - 5 28 - 6 7 -...
result:
wrong answer
Subtask #3:
score: 0
Wrong Answer
Test #30:
score: 0
Wrong Answer
time: 1ms
memory: 3920kb
input:
77 174 30 58 11 21 76 47 53 6 26 34 6 27 46 37 68 54 40 58 74 5 24 50 60 53 44 58 35 70 44 72 64 39 58 50 32 63 62 32 4 2 27 70 22 58 14 20 32 74 46 43 30 3 38 4 64 50 55 66 51 72 27 41 26 63 30 69 20 51 51 74 15 38 48 8 15 35 71 61 5 70 57 60 41 14 16 58 7 4 32 59 15 70 74 58 64 29 12 50 17 23 23 7...
output:
636 + 1 2 + 1 55 + 1 50 + 1 12 + 1 8 + 1 40 + 1 9 + 1 67 + 1 16 + 1 19 + 1 27 + 1 6 + 1 14 + 1 20 + 1 3 + 1 18 + 1 21 + 1 11 + 1 25 + 1 59 + 1 31 + 1 58 + 1 17 + 1 23 + 1 30 + 1 33 + 1 42 + 1 48 + 1 49 + 1 64 + 1 35 + 1 63 + 1 26 + 1 34 + 1 28 + 1 47 + 1 44 + 1 37 + 1 46 + 1 56 + 1 62 + 1 38 + 1 41 ...
result:
wrong answer
Subtask #4:
score: 0
Wrong Answer
Test #51:
score: 0
Wrong Answer
time: 1ms
memory: 3964kb
input:
243 827 102 228 81 121 175 167 118 27 9 27 85 239 207 236 189 230 126 98 237 211 81 228 112 152 189 21 228 47 208 233 165 156 241 201 87 93 197 113 55 201 207 206 2 39 66 135 112 64 14 106 39 191 232 117 13 122 1 155 226 39 121 43 169 27 220 175 7 171 179 28 92 125 242 110 62 133 102 20 125 58 114 3...
output:
1531 + 1 9 + 1 3 + 1 31 + 1 22 + 1 12 + 1 45 + 1 8 + 1 18 + 1 24 + 1 133 + 1 34 + 1 88 + 1 16 + 1 29 + 1 2 + 1 4 + 1 48 + 1 26 + 1 97 + 1 67 + 1 38 + 1 42 + 1 108 + 1 68 + 1 52 + 1 72 + 1 43 + 1 41 + 1 28 + 1 13 + 1 40 + 1 5 + 1 110 + 1 76 + 1 11 + 1 47 + 1 7 + 1 10 + 1 186 + 1 25 + 1 39 + 1 36 + 1 ...
result:
wrong answer
Subtask #5:
score: 0
Wrong Answer
Test #71:
score: 0
Wrong Answer
time: 0ms
memory: 4008kb
input:
330 1407 6 289 138 281 283 258 57 224 302 108 124 142 268 56 243 115 249 59 157 210 222 177 24 123 23 306 49 316 58 66 170 278 151 188 108 165 128 35 15 209 269 191 51 310 47 300 145 89 311 301 130 209 69 260 126 68 112 306 161 154 94 279 302 137 98 306 134 317 114 81 159 232 114 39 168 247 39 226 1...
output:
3561 + 1 38 + 1 10 + 1 62 + 1 13 + 1 9 + 1 34 + 1 6 + 1 12 + 1 43 + 1 18 + 1 4 + 1 79 + 1 2 + 1 16 + 1 26 + 1 41 + 1 47 + 1 39 + 1 32 + 1 85 + 1 20 + 1 259 + 1 57 + 1 22 + 1 87 + 1 44 + 1 71 + 1 3 + 1 89 + 1 24 + 1 66 + 1 58 + 1 48 + 1 105 + 1 30 + 1 51 + 1 68 + 1 40 + 1 171 + 1 60 + 1 8 + 1 100 + 1...
result:
wrong answer
Subtask #6:
score: 0
Wrong Answer
Test #92:
score: 0
Wrong Answer
time: 2ms
memory: 4052kb
input:
924 1839 387 504 262 823 116 587 377 243 530 378 211 67 646 436 238 451 35 556 87 604 581 387 353 743 686 102 620 253 103 92 688 886 368 359 269 658 881 365 640 119 910 658 917 41 685 661 362 605 341 287 578 180 638 870 906 297 325 784 70 427 876 635 43 754 25 233 113 660 217 377 518 487 646 798 655...
output:
4896 + 1 52 + 1 322 + 1 117 + 1 38 + 1 259 + 1 424 + 1 491 + 1 113 + 1 86 + 1 18 + 1 273 + 1 430 + 1 15 + 1 96 + 1 257 + 1 39 + 1 66 + 1 552 + 1 775 + 1 160 + 1 397 + 1 227 + 1 97 + 1 102 + 1 156 + 1 794 + 1 428 + 1 178 + 1 494 + 1 234 + 1 314 + 1 485 + 1 183 + 1 120 + 1 6 + 1 9 + 1 407 + 1 295 + 1 ...
result:
wrong answer
Subtask #7:
score: 0
Wrong Answer
Test #112:
score: 0
Wrong Answer
time: 6ms
memory: 4588kb
input:
3679 6128 1629 19 2272 2346 2038 2230 2781 946 450 2308 440 2919 1874 3099 1506 1736 122 3082 3365 1836 2727 1543 2613 360 3330 285 2368 484 1409 2864 2777 1349 159 1952 2164 298 1353 1912 2688 2051 190 1992 3376 1360 3308 2279 1938 1815 1604 1329 3547 2031 2885 829 3356 567 840 3191 2104 1593 1122 ...
output:
22365 + 1 638 + 1 2072 + 1 185 + 1 1334 + 1 284 + 1 710 + 1 2011 + 1 764 + 1 328 + 1 859 + 1 40 + 1 2071 + 1 682 + 1 753 + 1 1426 + 1 347 + 1 2094 + 1 491 + 1 140 + 1 73 + 1 629 + 1 298 + 1 1512 + 1 2524 + 1 1891 + 1 982 + 1 577 + 1 649 + 1 1004 + 1 523 + 1 3131 + 1 845 + 1 728 + 1 493 + 1 810 + 1 2...
result:
wrong answer
Subtask #8:
score: 0
Wrong Answer
Test #133:
score: 0
Wrong Answer
time: 8ms
memory: 5404kb
input:
6739 7057 4212 4650 3924 6154 3999 5859 4330 4505 3588 6090 4579 2999 3767 3650 1336 3561 4663 4777 4475 4664 1141 4066 3265 5712 3021 1803 956 5825 4560 3357 4783 6433 5447 4679 2566 5531 2136 584 1749 3551 6195 3416 3132 6314 3005 1680 3712 5492 994 1225 4587 2905 1386 2608 1430 1639 6285 744 1776...
output:
32976 + 1 255 + 1 1423 + 1 268 + 1 2598 + 1 832 + 1 788 + 1 3770 + 1 347 + 1 4216 + 1 14 + 1 88 + 1 4881 + 1 577 + 1 1730 + 1 1140 + 1 394 + 1 5343 + 1 1322 + 1 1850 + 1 94 + 1 265 + 1 221 + 1 2875 + 1 1160 + 1 3673 + 1 3788 + 1 2451 + 1 3193 + 1 2067 + 1 3683 + 1 566 + 1 2600 + 1 339 + 1 2681 + 1 5...
result:
wrong answer
Subtask #9:
score: 0
Wrong Answer
Test #153:
score: 0
Wrong Answer
time: 15ms
memory: 6116kb
input:
14707 17215 6756 405 12220 7729 5130 2987 4230 11416 14140 1338 13330 9266 4937 5289 13405 3659 574 4609 5204 3245 4975 2161 11210 3636 10189 10199 7401 9877 2008 6508 4419 4957 7160 9652 1891 6267 5461 1300 94 8088 6141 12560 7026 956 9897 7948 1545 14440 5422 3832 3778 4614 12647 6491 2070 6050 26...
output:
61321 + 1 9799 + 1 77 + 1 2986 + 1 3428 + 1 8475 + 1 9414 + 1 12479 + 1 519 + 1 2327 + 1 3291 + 1 748 + 1 4573 + 1 272 + 1 6800 + 1 11986 + 1 4556 + 1 8114 + 1 33 + 1 1761 + 1 9688 + 1 2727 + 1 3664 + 1 834 + 1 2362 + 1 1064 + 1 14317 + 1 4885 + 1 2450 + 1 4044 + 1 5470 + 1 4589 + 1 8614 + 1 1499 + ...
result:
wrong answer
Subtask #10:
score: 0
Wrong Answer
Test #174:
score: 0
Wrong Answer
time: 23ms
memory: 7668kb
input:
22315 25704 5856 19157 8513 4234 638 5685 19718 9543 10907 170 978 13050 2747 1041 18713 15952 15146 13270 22171 6385 3306 1989 20586 3259 19291 9203 19084 15179 10066 8110 20002 10325 16192 7218 22313 17022 13691 2970 14973 1993 4453 17401 3 3211 6947 8986 19000 20815 20859 21056 7068 14262 1589 21...
output:
92634 + 1 4218 + 1 1544 + 1 1688 + 1 6052 + 1 9138 + 1 10491 + 1 9058 + 1 14052 + 1 20198 + 1 929 + 1 4936 + 1 14451 + 1 10055 + 1 19983 + 1 1418 + 1 1035 + 1 4857 + 1 3665 + 1 6689 + 1 20218 + 1 9450 + 1 7382 + 1 9658 + 1 7173 + 1 7432 + 1 1135 + 1 5175 + 1 14272 + 1 21512 + 1 14641 + 1 5668 + 1 84...
result:
wrong answer