QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#384007 | #7769. Axium Crisis | zhouhuanyi | 5 | 1002ms | 531172kb | C++14 | 4.8kb | 2024-04-09 19:52:58 | 2024-04-09 19:53:00 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#define N 18
#define M 1048518
using namespace std;
const int inf=(int)(1e9);
int read()
{
char c=0;
int sum=0;
while (c<'0'||c>'9') c=getchar();
while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
return sum;
}
struct reads
{
int num,data,snum;
};
struct rds
{
int x,y,d,st,st2;
};
rds tong[M+1];
struct dst
{
int num,data;
};
inline dst max(dst a,dst b)
{
return a.data>b.data?a:b;
}
struct node
{
int num;
dst data;
};
node v[1<<N][N+1];
struct path
{
int x,y;
};
path rd[N+1];
int T,o,sx,sy,n,length,cater,len[1<<N],cl[N+1],fa[N+1],st[N+1],leng,lg[M+1],h[M+1],ST[M+1][21],ans;
dst maxn[1<<N];
vector<reads>E[N+1];
vector<rds>p[N+1][1<<N];
vector<dst>pv[M+1];
bool used[N+1];
void add(int x,int y,int z,int w)
{
E[x].push_back((reads){y,z,w}),E[y].push_back((reads){x,z,w});
return;
}
void dfs(int x)
{
used[x]=1;
for (int i=0;i<E[x].size();++i)
if (!used[E[x][i].num])
fa[E[x][i].num]=x,dfs(E[x][i].num);
return;
}
void dfs2(int rt,int x,int d,int st,int st2)
{
if (d&&E[x].size()==1) ans=max(ans,d-1),p[d][st2].push_back((rds){rt,x,d,st,st2});
for (int i=0;i<E[x].size();++i)
if (fa[E[x][i].num]==x)
{
if (E[x][i].data!=1) dfs2(rt,E[x][i].num,d+1,st|(1<<(E[x][i].snum-1)),st2);
if (E[x][i].data!=0) dfs2(rt,E[x][i].num,d+1,st|(1<<(E[x][i].snum-1)),st2|(1<<d));
}
return;
}
void dfs3(int d,int st)
{
if (d)
{
for (int i=0;i<p[d][st].size();++i) tong[++length]=p[d][st][i];
}
if (d!=n-1) dfs3(d+1,st),dfs3(d+1,st|(1<<d));
return;
}
int lcp(rds a,rds b)
{
for (int i=0;i<min(a.d,b.d);++i)
if (((a.st2>>i)&1)!=((b.st2>>i)&1))
return i;
return min(a.d,b.d);
}
int query(int x,int y)
{
int lw=lg[y-x];
return min(ST[x+1][lw],ST[y-(1<<lw)+1][lw]);
}
dst calc(int x,int d)
{
dst res=(dst){-inf,-inf};
int wst;
if (len[x])
{
wst=query(v[x][len[x]].data.num,d);
while (len[x]&&v[x][len[x]].num>=wst) res=max(res,v[x][len[x]].data),len[x]--;
if (res.data!=-inf)
{
if (res.data>maxn[x].data) v[x][++len[x]]=(node){wst,res};
if (!x||res.data-wst>0) maxn[x]=max(maxn[x],(dst){res.num,res.data-wst});
}
}
return maxn[x];
}
void insert(int x,int d,int ds)
{
dst res=(dst){-inf,-inf};
int wst;
if (len[x])
{
wst=query(v[x][len[x]].data.num,d);
while (len[x]&&v[x][len[x]].num>=wst) res=max(res,v[x][len[x]].data),len[x]--;
if (res.data!=-inf)
{
if (res.data>maxn[x].data) v[x][++len[x]]=(node){wst,res};
if (!x||res.data-wst>0) maxn[x]=max(maxn[x],(dst){res.num,res.data-wst});
}
}
if (ds>maxn[x].data) v[x][++len[x]]=(node){inf,(dst){d,ds}};
return;
}
void adder(int x,int d1,int d2)
{
dst ds=calc(d1,x);
pv[x].push_back((dst){d2,ds.num});
if (ds.data!=-inf&&ds.data+tong[x].d+n-1-__builtin_popcount(d2)>ans)
{
insert(d2,x,ds.data+tong[x].d);
if (ds.data+tong[x].d>ans) ans=ds.data+tong[x].d,sx=x,sy=d2;
}
return;
}
int get_pv(int x,int d)
{
for (int i=0;i<pv[x].size();++i)
if (pv[x][i].num==d)
return pv[x][i].data;
return -1;
}
void get_path(int x,int y,int d)
{
for (int i=1;i<=n;++i) used[i]=fa[i]=0;
rd[++cater]=(path){x,y},dfs(x),leng=0;
while (y) st[++leng]=y,y=fa[y];
reverse(st+1,st+leng+1);
for (int i=1;i<=leng-1;++i)
for (int j=0;j<E[st[i]].size();++j)
if (E[st[i]][j].num==st[i+1])
cl[E[st[i]][j].snum]=(d>>(i-1))&1;
return;
}
int main()
{
int x,y,z,d;
for (int i=2;i<=M;++i) lg[i]=lg[i>>1]+1;
T=read(),o=read(),puts("1");
for (int qt=1;qt<=T;++qt)
{
n=read(),length=ans=sx=sy=cater=0;
for (int i=1;i<=n;++i) E[i].clear();
for (int i=0;i<(1<<(n-1));++i) len[i]=0,maxn[i]=(dst){-inf,-inf};
for (int i=1;i<=n-1;++i)
for (int j=0;j<(1<<i);++j)
p[i][j].clear();
for (int i=1;i<=n-1;++i)
{
x=read()+1,y=read()+1,z=read(),add(x,y,z,i);
if (z!=2) cl[i]=z;
else cl[i]=0;
}
for (int i=1;i<=n;++i)
if (E[i].size()==1)
{
for (int j=1;j<=n;++j) used[j]=fa[j]=0;
dfs(i),dfs2(i,i,0,0,0);
}
dfs3(0,0),h[1]=0;
for (int i=2;i<=length;++i) h[i]=lcp(tong[i-1],tong[i]);
for (int i=1;i<=length;++i) ST[i][0]=h[i];
for (int i=1;i<=lg[length];++i)
for (int j=1;j+(1<<i)-1<=length;++j)
ST[j][i]=min(ST[j][i-1],ST[j+(1<<(i-1))][i-1]);
for (int i=1;i<=length;++i) pv[i].clear();
insert(0,0,0);
for (int i=1;i<=length;++i)
{
d=((1<<(n-1))-1)^tong[i].st;
for (int j=d;j>0;j=(j-1)&d) adder(i,j,j|tong[i].st);
adder(i,0,tong[i].st);
}
while (sx) d=get_pv(sx,sy),get_path(tong[sx].x,tong[sx].y,tong[sx].st2),sy^=tong[sx].st,sx=d;
printf("%d\n%d\n",ans+1,cater);
for (int i=1;i<=n-1;++i) printf("%d ",cl[i]);
puts("");
for (int i=1;i<=cater;++i) printf("%d %d\n",rd[i].x-1,rd[i].y-1);
}
return 0;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 16ms
memory: 154380kb
input:
1000 0 4 0 2 0 2 3 0 2 1 0 4 3 2 1 0 2 1 1 2 2 4 0 2 2 0 1 0 3 0 0 4 1 2 1 3 2 0 2 0 1 4 0 2 0 0 3 0 2 1 0 4 0 2 1 0 3 1 0 1 1 4 3 1 0 2 1 2 3 0 2 4 3 1 1 3 0 1 2 3 0 4 1 0 0 2 0 2 2 3 2 4 1 2 0 3 0 0 2 3 2 3 2 1 0 0 2 1 4 3 0 1 1 2 1 2 3 0 4 2 1 0 3 0 1 1 0 1 4 3 2 1 3 1 1 0 1 1 4 1 2 1 1 3 0 3 0 1...
output:
1 3 1 0 0 0 0 3 3 1 1 1 0 1 3 3 1 0 0 0 1 2 3 1 1 0 1 3 1 4 1 0 0 0 1 3 3 1 1 1 1 1 2 4 1 0 0 0 0 2 3 1 1 1 0 2 1 4 1 0 0 0 1 3 4 1 0 0 0 0 1 3 1 0 1 1 0 4 1 1 1 0 0 1 4 1 0 1 1 2 3 4 1 1 1 1 0 2 4 1 1 0 1 0 2 4 1 1 0 0 0 1 4 1 0 0 0 1 2 4 1 0 1 0 0 3 3 1 0 0 0 0 3 4 1 0 0 0 1 2 ...
result:
wrong answer Wrong Answer.
Subtask #2:
score: 0
Wrong Answer
Test #3:
score: 0
Wrong Answer
time: 19ms
memory: 149484kb
input:
3000 3 4 0 1 1 0 3 1 0 2 0 4 3 2 0 0 1 1 1 2 0 4 1 0 0 2 3 1 3 1 0 4 2 1 0 2 0 1 3 0 0 4 2 3 1 3 0 1 2 1 0 4 2 3 1 2 1 1 2 0 1 4 0 2 0 1 0 0 3 0 0 4 3 1 1 0 2 0 2 3 0 6 4 0 0 3 1 1 2 3 0 0 5 1 1 5 0 4 2 3 1 3 0 0 3 1 1 4 0 3 0 1 2 0 0 2 1 4 0 2 1 3 1 0 2 1 1 4 2 0 0 2 3 1 1 3 0 6 3 1 0 3 4 1 4 0 1 2...
output:
1 3 1 1 1 0 2 1 4 1 0 1 0 3 0 4 1 0 1 0 0 2 4 1 0 1 0 1 3 4 1 1 1 0 1 0 3 1 1 1 1 0 3 3 1 0 0 0 1 2 4 1 1 0 0 0 1 6 1 0 1 0 1 0 2 4 3 1 1 0 1 0 2 4 1 0 0 1 1 3 4 1 1 0 1 3 0 4 1 0 1 0 0 1 5 1 0 1 1 1 1 5 0 3 1 1 0 0 2 3 4 1 1 0 1 0 3 3 1 1 1 1 0 2 3 1 0 1 0 2 3 1 0 1 0 0 1 5 2 0 0...
result:
wrong answer Wrong Answer.
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #2:
0%
Subtask #5:
score: 0
Skipped
Dependency #3:
0%
Subtask #6:
score: 0
Skipped
Dependency #4:
0%
Subtask #7:
score: 5
Accepted
Test #13:
score: 5
Accepted
time: 107ms
memory: 202028kb
input:
3000 1 11 2 5 0 10 2 0 6 2 0 2 8 0 0 2 0 2 1 0 2 4 0 2 9 0 2 3 0 7 2 0 11 7 8 0 6 4 0 1 6 0 2 8 0 8 0 0 6 3 0 9 5 0 5 8 0 1 2 0 9 10 0 8 1 4 0 2 3 0 6 5 0 6 7 0 2 4 0 7 3 0 1 0 0 8 4 0 0 0 5 0 7 2 0 0 2 0 0 6 0 0 1 0 0 3 0 11 5 1 0 7 2 0 9 2 0 4 9 0 0 2 0 8 5 0 0 6 0 3 6 0 4 10 0 1 7 0 7 6 2 0 0 5 0...
output:
1 3 1 0 0 0 0 0 0 0 0 0 0 0 5 8 1 0 0 0 0 0 0 0 0 0 0 3 10 8 1 0 0 0 0 0 0 0 0 5 4 1 0 0 0 0 0 0 0 1 7 8 1 0 0 0 0 0 0 0 0 0 0 3 8 7 1 0 0 0 0 0 0 1 3 5 1 0 0 0 0 0 4 7 1 0 0 0 0 0 0 2 4 11 1 0 0 0 0 0 0 0 0 0 0 5 7 4 1 0 0 0 0 0 0 0 1 4 8 1 0 0 0 0 0 0 0 5 6 4 1 0 0 0 0 0 0 0 0 0 0 0 3 ...
result:
ok Accepted. Good Job!
Subtask #8:
score: 0
Wrong Answer
Test #14:
score: 0
Wrong Answer
time: 1002ms
memory: 531172kb
input:
3000 2 8 4 7 2 4 3 2 3 2 2 4 5 2 1 4 2 6 4 2 0 1 2 8 1 5 2 0 7 2 3 2 2 3 1 2 5 7 2 4 0 2 6 4 2 8 1 3 2 5 3 2 7 6 2 2 6 2 0 7 2 4 6 2 0 5 2 8 5 7 2 2 6 2 1 6 2 4 5 2 4 0 2 0 1 2 7 3 2 11 2 7 2 0 9 2 8 9 2 10 7 2 6 9 2 9 3 2 4 10 2 7 5 2 7 9 2 1 9 2 8 2 6 2 1 5 2 4 1 2 1 3 2 6 1 2 0 1 2 6 7 2 14 2 6 2...
output:
1 7 2 0 0 0 1 0 0 0 5 7 0 2 8 1 0 0 0 0 0 0 0 2 6 7 1 0 0 0 0 0 0 0 1 2 8 1 0 0 0 0 0 0 0 2 3 9 4 0 1 1 0 0 0 0 1 0 1 0 8 1 6 2 5 3 4 6 2 0 0 0 0 0 1 0 0 5 3 7 7 6 1 0 0 1 1 1 1 0 0 0 1 0 0 0 6 1 12 5 13 4 7 3 10 9 11 6 1 0 0 0 0 0 0 5 6 2 0 0 0 0 0 1 0 3 1 6 10 2 0 0 1 0 0 0 0 0 0 0 0 3 7...
result:
wrong answer Wrong Answer.
Subtask #9:
score: 0
Skipped
Dependency #6:
0%
Subtask #10:
score: 0
Skipped
Dependency #5:
0%