QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#373809 | #5208. Jumbled Trees | InfinityNS | RE | 0ms | 0kb | C++20 | 7.9kb | 2024-04-02 07:37:10 | 2024-04-02 07:37:11 |
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].b]=1;
pos[e[e1].b]=1;
pos[e[e2].a]=2;
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;
for(int i=0;i<ret.size();i++){
pos[e[ret[i]].a]=pos[e[ret[i]].b]=1;
}
pos[e[e1].a]=1;
pos[e[e2].b]=2;
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: 0
Runtime Error
input:
3 3 101 1 2 30 2 3 40 3 1 50