QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#373808 | #5208. Jumbled Trees | InfinityNS | TL | 1ms | 4144kb | C++20 | 7.9kb | 2024-04-02 07:36:22 | 2024-04-02 07:36:24 |
Judging History
answer
#include<bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
typedef long long ll;
using namespace std;
typedef pair<int,int> pii;
int mod=998244353;
inline int add(int x,int y){int ret=x+y;if(ret>=mod)ret-=mod;return ret;}
inline int sub(int x,int y){int ret=x-y;if(ret<0)ret+=mod;return ret;}
inline int mul(int x,int y){return ((ll)x*y)%mod;}
inline int step(int base,int pw){int ret=1;while(pw){if(pw&1)ret=mul(ret,base);base=mul(base,base);pw>>=1;}return ret;}
inline int invv(int x){return step(x,mod-2);}
const int maxn=1010;
struct edge{
int a,b,w;
};
vector<edge>e;
vector<int>vect[maxn];
vector<pii>scand;
void add_edge(int a,int b,int w){
vect[a].pb(e.size());
vect[b].pb(e.size());
e.pb({a,b,w});
}
int disc[maxn],mint[maxn],ctm;
int get_nxt(int eid,int x){
if(e[eid].a==x)return e[eid].b;
return e[eid].a;
}
int ecol[maxn],ncnt;
int compsum[maxn];
int pos[maxn];
int s;
int n,m;
void obradi(vector<int>edges){
memset(pos,0,sizeof(pos));
ncnt++;
for(int i=0;i<edges.size();i++){
int id=edges[i];
//printf("%d ",id);
pos[e[id].a]=1;
pos[e[id].b]=1;
ecol[id]=ncnt;
compsum[ncnt]=add(compsum[ncnt],e[id].w);
}
//printf(" OB\n");
int sz=-1;
for(int i=1;i<=n;i++){
sz+=pos[i];
}
scand.pb({compsum[ncnt],sz});
}
void find_bridges(int x,int p,vector<int>&stek){
disc[x]=++ctm;
mint[x]=disc[x];
///printf("%d %d XX\n",x,disc[x]);
for(int i=0;i<vect[x].size();i++){
int id=vect[x][i];
if(id==p)continue;
int nxt=get_nxt(vect[x][i],x);
if(disc[nxt]<disc[x])stek.pb(id);
if(disc[nxt])mint[x]=min(mint[x],disc[nxt]);
else{
find_bridges(nxt,id,stek);
mint[x]=min(mint[x],mint[nxt]);
if(mint[nxt]>=disc[x]){
/*printf("%d %d %d EDGE\n",x,nxt,id);
for(int i=0;i<stek.size();i++)printf("%d ",stek[i]);
printf(" STEK\n");*/
vector<int>edges;
while(stek.back()!=id){
///printf("%d sz\n",stek.size());
edges.pb(stek.back());
stek.pop_back();
}
edges.pb(stek.back());
stek.pop_back();
obradi(edges);
}
}
//printf("%d %d | %d %d AAA\n",x,e[id].b,mint[e[id].b],disc[x]);
}
///printf("%d RET\n",x);
}
bool calc_s(){
int ep=0;
s=0;
for(int i=0;i<scand.size();i++){
int v=scand[i].ff;
int cc=scand[i].ss;
// printf("%d %d \n",v,cc);
if(cc==0){
if(v!=0)return false;
}
else{
int pom=mul(v,invv(cc));
if(ep==0){
ep=1;
s=pom;
}
else{
if(s!=pom)return false;
}
}
}
return true;
}
vector<pair<int,vector<int>>>ops;
void apply_mst(int v,vector<int>o){
assert(o.size()==n-1);
ops.pb({v,o});
for(int i=0;i<o.size();i++){
int id=o[i];
e[id].w=sub(e[id].w,v);
//printf("%d ",id);
}
/*printf(" | %d APPLIED\n",v);
for(int i=0;i<e.size();i++){
printf("%d ",e[i].w);
}
printf(" STATE\n");*/
}
void dfs(int x,int p,vector<int>&es){
pos[x]=1;
///printf("%d dOSO\n",x);
for(int i=0;i<vect[x].size();i++){
int id=get_nxt(vect[x][i],x);
if(pos[id])continue;
es.pb(vect[x][i]);
dfs(id,vect[x][i],es);
}
}
void apply_rand_mst(){
vector<int>edges;
memset(pos,0,sizeof(pos));
dfs(1,-1,edges);
apply_mst(s,edges);
}
int dfs2(int x,int p,vector<int>&es){
//printf("%d XX\n",x);
if(pos[x]==2){
pos[x]=1;
return 1;
}
pos[x]=1;
for(int i=0;i<vect[x].size();i++){
int id=vect[x][i];
int v=get_nxt(vect[x][i],x);
if(pos[v]==1)continue;
if(pos[v]==2){
es.pb(id);
return 1;
}
if(dfs2(v,id,es)){
es.pb(id);
return 1;
}
}
return 0;
}
vector<int>nadji_ciklus(int e1,int e2){
memset(pos,0,sizeof(pos));
pos[e[e2].a]=2;
pos[e[e2].b]=1;
pos[e[e1].b]=1;
vector<int>ret;
int epe=dfs2(e[e1].a,-1,ret);
///if(!epe)while(1){}
if(!epe){
vector<int>ret;
return ret;
}
/*printf("%d ADA\n",ret.size());
for(int i=0;i<ret.size();i++){
int id=ret[i];
printf("%d %d EDGE\n",e[id].a,e[id].b);
}*/
memset(pos,0,sizeof(pos));
///pos[e[e2].a]=2;
pos[e[e2].b]=2;
for(int i=0;i<ret.size();i++){
pos[e[ret[i]].a]=pos[e[ret[i]].b]=1;
}
pos[e[e1].a]=1;
epe=dfs2(e[e1].b,-1,ret);
if(!epe){
vector<int>ret;
return ret;
}
/*if(!epe){
printf("%d %d | %d %d %d %d LOS CIKLUS\n",e1,e2,e[e1].a,e[e1].b,e[e2].a,e[e2].b);
}*/
//printf("%d ADA\n",ret.size());
ret.pb(e1);
ret.pb(e2);
return ret;
}
void solve_comp(int c){
vector<int>cand;
for(int i=0;i<e.size();i++){
if(ecol[i]==c)cand.pb(i);
}
while(cand.size()){
int id=cand.back();
cand.pop_back();
if(e[id].w==0)continue;
int id2=cand.back();
//printf("%d %d AA\n",id,id2);
vector<int>es=nadji_ciklus(id,id2);
if(es.size()==0){
swap(e[id].a,e[id].b);
es=nadji_ciklus(id,id2);
if(es.size()==0){
swap(e[id2].a,e[id2].b);
es=nadji_ciklus(id,id2);
if(es.size()==0){
swap(e[id].a,e[id].b);
es=nadji_ciklus(id,id2);
}
}
}
if(es.size()==0){
printf("%d %d LOSEE\n",id,id2);
while(1){}
}
/*for(int i=0;i<es.size();i++){
int id=es[i];
printf("%d %d |",e[id].a,e[id].b);
}
printf(" -> %d %d | %d %d CIKLUS\n",e[id].a,e[id].b,e[id2].a,e[id2].b);*/
memset(pos,0,sizeof(pos));
for(int j=0;j<es.size();j++){
int id=es[j];
pos[e[id].b]=1;
pos[e[id].a]=1;
}
vector<int>qry,qry2;
for(int j=0;j<es.size();j++){
int id=es[j];
dfs(e[id].a,-1,qry);
dfs(e[id].b,-1,qry);
}
qry2=qry;
/*for(int j=0;j<qry.size();j++){
int id=qry[j];
printf("%d %d |",e[id].a,e[id].b);
}
printf(" TREE\n");*/
for(int j=0;j<es.size();j++){
int idc=es[j];
if(idc==id)qry.pb(idc);
else if(idc==id2)qry2.pb(idc);
else{
qry.pb(idc);
qry2.pb(idc);
}
}
///printf("%d %d %d SIZES\n",qry.size(),qry2.size(),es.size());
///if(qry.size()!=n-1)while(1){}
int goal=e[id].w;
apply_mst(goal,qry);
apply_mst(sub(0,goal),qry2);
}
}
int main(){
///freopen("test.txt","r",stdin);
scanf("%d %d %d",&n,&m,&mod);
for(int i=1;i<=m;i++){
int u,v,w;
scanf("%d %d %d",&u,&v,&w);
add_edge(u,v,w);
}
vector<int>stek;
find_bridges(1,-1,stek);
if(!calc_s()){
printf("-1\n");
return 0;
}
///printf("%d SS\n",s);
apply_rand_mst();
for(int i=1;i<=ncnt;i++){
solve_comp(i);
}
printf("%d\n",ops.size());
for(int i=0;i<ops.size();i++){
printf("%d ",ops[i].ff);
vector<int>&pom=ops[i].ss;
for(auto x:pom)printf("%d ",x+1);
printf("\n");
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3776kb
input:
3 3 101 1 2 30 2 3 40 3 1 50
output:
5 60 1 2 50 1 3 51 1 2 30 3 2 71 3 1
result:
ok Participant found an answer (5 trees) and jury found an answer (5 trees)
Test #2:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
2 2 37 1 2 8 1 2 15
output:
3 23 1 15 2 22 1
result:
ok Participant found an answer (3 trees) and jury found an answer (3 trees)
Test #3:
score: 0
Accepted
time: 1ms
memory: 4000kb
input:
5 4 5 1 3 1 2 3 2 2 5 3 4 1 4
output:
-1
result:
ok Both jury and participant did not find an answer
Test #4:
score: 0
Accepted
time: 0ms
memory: 4044kb
input:
10 15 997 4 3 459 9 7 94 9 8 767 10 2 877 5 8 258 3 4 166 8 5 621 8 10 619 9 1 316 10 5 516 3 10 125 1 7 961 3 6 500 4 10 976 3 4 842
output:
-1
result:
ok Both jury and participant did not find an answer
Test #5:
score: 0
Accepted
time: 1ms
memory: 3828kb
input:
20 30 9973 1 10 696 3 8 2905 12 7 6609 20 10 1962 11 9 8430 19 2 412 6 3 6936 19 7 9113 14 15 5635 15 7 1770 13 10 3182 3 16 2625 17 1 7387 11 5 3700 9 15 1048 2 3 7717 12 10 8625 7 13 8141 5 14 2245 6 4 2819 18 19 8709 18 5 6191 17 10 7606 9 20 8626 17 4 8848 4 13 1073 10 8 2277 14 2 7714 11 8 5318...
output:
59 9375 1 4 24 5 14 19 9 10 3 8 6 16 2 7 20 25 26 12 21 9860 5 15 9 28 6 8 3 17 1 13 25 20 26 4 21 14 2 12 30 113 5 15 9 28 6 8 3 17 1 13 25 20 26 4 21 14 2 12 29 5205 19 22 30 24 3 9 15 5 6 8 18 11 1 13 25 20 7 2 29 4768 19 22 30 24 3 9 15 5 6 8 18 11 1 13 25 20 7 2 28 2946 1 13 25 20 7 12 26 ...
result:
ok Participant found an answer (59 trees) and jury found an answer (59 trees)
Test #6:
score: 0
Accepted
time: 0ms
memory: 3756kb
input:
50 80 99991 6 5 67664 39 4 74944 11 9 13035 13 48 81979 40 20 57943 20 31 72081 1 6 39307 48 39 3550 28 48 41071 18 28 42935 37 32 7538 37 29 3815 50 37 88043 38 41 7283 40 26 66278 37 34 60696 47 19 80875 4 26 67 20 32 91858 39 24 83485 45 25 12241 48 46 61691 37 44 47541 39 40 70034 37 42 25006 27...
output:
-1
result:
ok Both jury and participant did not find an answer
Test #7:
score: 0
Accepted
time: 0ms
memory: 3856kb
input:
100 150 999983 84 10 999545 69 48 930138 48 13 303468 36 6 668122 91 84 115623 62 71 59711 12 37 749281 86 49 281976 26 46 624831 91 8 450475 92 55 460900 50 63 513056 72 2 477622 26 96 11359 31 82 953946 6 71 406339 24 7 177090 70 4 67359 31 39 795565 47 32 407459 26 35 760698 22 37 508175 8 93 612...
output:
-1
result:
ok Both jury and participant did not find an answer
Test #8:
score: 0
Accepted
time: 1ms
memory: 3784kb
input:
200 250 9999991 170 185 3242943 70 17 6083198 137 55 4000889 15 171 1113989 108 65 7988488 192 37 8812990 53 143 8707264 80 180 2504807 55 163 2706048 67 64 6210980 87 165 7693967 155 122 8550804 56 99 7228534 114 138 7047731 190 196 6684929 86 197 8866886 38 195 6717874 112 133 7257617 160 104 3210...
output:
-1
result:
ok Both jury and participant did not find an answer
Test #9:
score: 0
Accepted
time: 1ms
memory: 3872kb
input:
500 600 99999989 265 416 47066772 354 266 16969437 195 415 7917612 354 136 43128175 163 191 58723996 144 84 65835385 157 45 94124747 232 441 17509499 70 397 64101208 223 387 7043647 320 47 84970673 100 2 87310855 87 131 75042257 101 391 27645446 79 26 68547739 390 185 92142961 257 15 80922292 276 48...
output:
-1
result:
ok Both jury and participant did not find an answer
Test #10:
score: 0
Accepted
time: 1ms
memory: 3924kb
input:
500 700 99999989 250 2 71289880 454 447 70661327 328 253 57519343 11 201 67456781 294 99 23392419 215 322 61059212 411 389 69899684 488 429 89579827 437 79 60564061 413 380 34922641 477 372 14858185 156 44 3101349 88 8 52225146 115 26 8582010 171 237 33206748 237 495 31192017 146 32 62712576 209 352...
output:
-1
result:
ok Both jury and participant did not find an answer
Test #11:
score: 0
Accepted
time: 1ms
memory: 3912kb
input:
500 800 99999989 258 304 1237432 159 152 6684056 8 47 64155938 436 265 83092505 204 302 3892712 142 302 77925167 37 15 20298972 202 395 35856655 284 260 96812598 365 172 48834835 196 101 64871741 174 45 37729972 302 206 90932677 305 275 27712443 443 157 81820535 16 248 22708463 461 479 64749118 105 ...
output:
-1
result:
ok Both jury and participant did not find an answer
Test #12:
score: 0
Accepted
time: 1ms
memory: 3916kb
input:
500 900 99999989 122 188 44796717 73 121 56798468 334 358 95823235 485 453 96779071 209 391 45946094 332 168 91056077 481 483 81268636 148 393 25213027 107 214 99281713 493 46 61525618 472 355 74320568 258 482 99615552 159 393 20311839 411 121 5207095 20 131 65269699 45 339 51772607 195 292 64556504...
output:
-1
result:
ok Both jury and participant did not find an answer
Test #13:
score: 0
Accepted
time: 0ms
memory: 4144kb
input:
500 1000 99999989 75 20 25003980 292 19 89418683 353 246 74910681 183 201 97535184 254 421 50614221 15 396 86624029 82 13 67776336 86 70 62843451 279 3 55801636 29 425 30024776 176 243 16631048 498 363 77415492 55 305 80862521 213 110 30693079 432 358 99667002 201 30 44433122 97 203 16284993 118 490...
output:
-1
result:
ok Both jury and participant did not find an answer
Test #14:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
500 499 999999937 287 228 350409600 392 107 350409600 458 22 350409600 362 425 350409600 368 136 350409600 364 71 350409600 211 265 350409600 167 116 350409600 195 353 350409600 489 477 350409600 380 85 350409600 281 15 350409600 263 247 350409600 453 122 350409600 104 187 350409600 331 223 35040960...
output:
1 350409600 214 267 66 113 137 376 28 30 432 370 389 364 42 399 117 272 241 35 285 232 329 483 227 244 11 419 333 47 24 171 83 306 258 61 324 19 298 231 216 280 464 249 439 206 134 336 383 43 158 86 179 436 470 135 192 475 366 388 265 72 348 368 458 484 401 130 136 235 450 52 3 199 417 266 477 166 4...
result:
ok Participant found an answer (1 trees) and jury found an answer (1 trees)
Test #15:
score: -100
Time Limit Exceeded
input:
500 510 999999937 417 280 770450784 207 303 770450784 472 396 770450784 345 191 964169440 164 67 770450784 492 302 770450784 5 71 770450784 386 22 770450784 77 25 487491058 430 467 770450784 148 95 770450784 288 215 770450784 55 451 10190666 215 69 770450784 267 195 770450784 487 283 770450784 435 3...