QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#383999#7769. Axium Crisiszhouhuanyi100 ✓9261ms1900844kbC++144.7kb2024-04-09 19:49:062024-04-09 19:49:08

Judging History

你现在查看的是最新测评结果

  • [2024-04-09 19:49:08]
  • 评测
  • 测评结果:100
  • 用时:9261ms
  • 内存:1900844kb
  • [2024-04-09 19:49:06]
  • 提交

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) 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)
		{
			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: 10
Accepted

Test #1:

score: 10
Accepted
time: 16ms
memory: 158080kb

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
4
2
1 1 0 
0 2
1 3
4
2
1 0 0 
0 2
1 3
4
2
1 0 1 
0 2
3 1
4
1
0 0 0 
1 3
3
1
1 1 1 
1 2
4
1
0 0 0 
0 2
4
2
1 1 0 
0 3
2 1
4
1
0 0 0 
1 3
4
1
0 0 0 
0 1
3
1
0 1 
1 0
4
2
1 1 0 
0 3
3 1
4
1
0 1 1 
2 3
4
1
1 1 1 
0 2
4
2
1 0 1 
0 3
3 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 ...

result:

ok Accepted. Good Job!

Test #2:

score: 10
Accepted
time: 18ms
memory: 159228kb

input:

1000 0
4
2 0 0
2 1 0
0 3 0
4
2 1 0
2 0 0
1 3 0
4
1 3 0
1 0 0
2 1 0
4
0 1 2
2 1 2
1 3 2
4
0 2 2
3 2 0
1 3 1
4
1 3 0
2 3 0
3 0 0
4
1 2 1
3 0 0
0 2 0
4
3 2 1
2 1 1
0 1 0
4
2 1 0
3 2 0
2 0 0
4
1 3 0
2 3 0
3 0 2
4
2 0 0
3 0 1
1 2 1
4
0 2 2
3 1 2
2 1 2
4
1 3 2
3 0 2
2 0 2
4
2 0 0
2 1 2
2 3 1
4
0 1 2
2 3 1...

output:

1
4
1
0 0 0 
1 3
4
1
0 0 0 
0 3
3
1
0 0 0 
0 3
4
2
1 0 0 
0 1
2 3
4
1
0 0 1 
0 1
3
1
0 0 0 
0 1
4
1
1 0 0 
3 1
4
1
1 1 0 
0 3
3
1
0 0 0 
0 1
4
2
0 0 1 
0 3
1 2
4
2
0 1 1 
0 3
0 1
4
1
0 0 0 
0 3
4
1
0 0 0 
1 2
4
2
0 1 1 
1 2
0 3
4
1
0 1 0 
0 2
3
1
0 0 0 
0 2
4
1
0 1 0 
2 3
4
1
0 0 0 
1 3
4
2
0 0 1 
1...

result:

ok Accepted. Good Job!

Subtask #2:

score: 10
Accepted

Test #3:

score: 10
Accepted
time: 28ms
memory: 157800kb

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
4
2
1 1 0 
0 1
2 3
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
4
2
1 0 1 
1 3
0 2
4
1
0 0 1 
1 3
4
1
1 0 1 
3 0
4
1
0 1 0 
0 1
5
2
0 1 1 1 1 
0 4
1 2
4
2
1 0 0 
0 1
2 3
4
2
1 0 1 
0 2
2 3
3
1
1 1 1 
0 2
3
1
0 1 
0 2
4
...

result:

ok Accepted. Good Job!

Test #4:

score: 10
Accepted
time: 16ms
memory: 158560kb

input:

3000 3
3
0 1 0
1 2 0
4
2 1 1
0 2 0
0 3 1
6
3 4 1
1 4 0
1 5 1
2 1 1
3 0 0
4
0 2 1
1 2 0
1 3 1
4
0 3 1
2 0 1
1 2 0
6
1 2 0
0 3 0
2 5 0
0 2 1
4 2 0
4
2 0 0
2 1 1
3 1 1
4
1 0 1
1 2 0
3 0 1
4
1 3 0
2 1 1
0 2 0
4
1 3 0
2 1 0
1 0 0
4
3 1 0
2 3 0
0 1 1
4
1 0 0
2 0 0
3 0 0
4
2 1 1
1 0 1
2 3 0
4
3 0 1
1 0 0
2...

output:

1
3
1
0 0 
0 2
4
2
1 0 1 
0 3
0 1
6
2
1 0 1 1 0 
1 5
0 2
4
2
1 0 1 
0 2
2 3
4
1
1 1 0 
1 3
5
2
0 0 0 1 0 
1 3
4 5
4
1
0 1 1 
0 3
4
1
1 0 1 
2 3
4
1
0 1 0 
0 3
3
1
0 0 0 
0 3
4
1
0 0 1 
2 0
3
1
0 0 0 
1 2
4
1
1 1 0 
3 0
4
1
1 0 0 
1 2
6
1
1 0 0 1 0 
1 3
4
2
0 1 1 
0 3
0 1
4
1
0 1 0 
2 3
4
1
0 0 1 
0 ...

result:

ok Accepted. Good Job!

Subtask #3:

score: 10
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Test #5:

score: 10
Accepted
time: 46ms
memory: 160432kb

input:

3000 4
4
2 0 0
1 2 0
1 3 0
4
1 2 2
0 2 2
3 2 2
4
3 1 2
3 2 0
0 2 0
4
0 3 2
2 1 2
0 1 2
4
0 1 0
3 0 0
0 2 2
4
2 0 0
2 1 0
3 0 0
6
0 3 2
5 0 2
5 2 2
1 4 2
4 3 2
4
0 3 0
3 1 0
0 2 0
4
1 0 2
2 0 2
3 2 2
4
2 1 2
1 0 2
0 3 2
6
5 0 2
0 2 2
0 4 2
1 0 2
0 3 2
6
4 5 2
0 1 2
0 3 2
4 3 2
5 2 2
4
1 3 0
3 2 0
1 0...

output:

1
4
1
0 0 0 
0 3
4
2
0 1 0 
0 2
1 3
4
1
0 0 0 
0 1
4
1
0 0 0 
2 3
4
2
0 0 1 
0 2
1 3
4
1
0 0 0 
1 3
6
1
0 0 0 0 0 
1 2
4
1
0 0 0 
1 2
4
1
0 0 0 
1 3
4
1
0 0 0 
2 3
5
3
1 1 0 0 0 
0 5
1 2
3 4
6
1
0 0 0 0 0 
1 2
4
1
0 0 0 
0 2
6
1
0 0 0 0 0 
1 5
4
1
0 0 0 
0 3
4
1
0 0 0 
0 1
4
1
0 0 0 0 0 
0 5
4
2
0 1...

result:

ok Accepted. Good Job!

Test #6:

score: 10
Accepted
time: 31ms
memory: 162664kb

input:

3000 0
6
1 3 2
0 4 0
1 4 2
3 5 1
0 2 0
6
0 5 0
0 4 1
0 2 0
3 0 0
1 0 0
6
4 1 2
2 1 1
5 0 2
5 3 1
2 3 0
4
2 0 0
1 0 2
1 3 0
4
2 3 1
0 1 1
2 1 0
4
0 3 1
1 0 2
2 3 0
4
1 3 1
2 3 0
0 1 2
6
1 0 1
4 1 1
5 1 1
3 1 1
2 1 2
4
0 3 1
1 3 2
1 2 1
4
1 2 1
0 2 0
3 1 1
6
0 2 1
1 2 1
0 5 0
2 4 1
2 3 1
6
3 2 1
0 2 0...

output:

1
6
1
0 0 0 1 0 
2 5
5
2
0 1 0 0 0 
4 5
1 3
6
1
0 1 0 1 0 
0 4
4
1
0 0 0 
2 3
4
2
1 1 0 
0 1
1 3
4
1
1 0 0 
1 2
4
1
1 0 0 
0 2
5
3
1 1 1 1 0 
0 4
1 5
2 3
4
2
1 0 1 
0 3
3 2
4
1
1 0 1 
0 3
6
2
1 1 0 1 1 
1 4
5 3
6
2
1 0 1 0 1 
0 4
0 1
4
2
1 0 1 
1 2
0 3
4
1
0 0 0 
0 3
6
1
1 0 0 1 1 
1 3
3
1
0 0 0 
0 ...

result:

ok Accepted. Good Job!

Subtask #4:

score: 10
Accepted

Dependency #2:

100%
Accepted

Test #7:

score: 10
Accepted
time: 95ms
memory: 163180kb

input:

3000 3
8
1 2 1
3 7 0
7 0 1
7 4 0
6 5 0
6 4 1
2 0 0
5
3 1 0
3 2 1
0 1 0
4 0 1
5
3 2 0
4 0 0
4 1 0
2 0 1
6
5 4 1
4 1 1
4 2 1
0 4 1
4 3 1
5
4 1 0
4 3 0
2 1 1
3 0 1
8
3 6 0
1 4 1
2 3 1
0 6 1
0 7 1
2 1 0
7 5 0
8
4 5 0
5 7 0
3 0 0
2 4 1
1 2 0
5 6 0
6 3 1
5
4 1 0
4 0 0
4 3 0
2 4 1
5
1 0 0
1 2 0
2 3 1
0 4 1...

output:

1
8
2
1 0 1 0 0 1 0 
1 7
3 5
5
2
0 1 0 1 
0 4
0 2
5
1
0 0 0 1 
1 3
3
1
1 1 1 1 1 
0 5
5
2
0 0 1 1 
0 3
3 2
8
1
0 1 1 1 1 0 0 
5 4
7
2
0 0 0 1 0 0 1 
0 5
7 1
5
2
0 0 0 1 
2 1
0 3
5
2
0 0 1 1 
0 4
0 3
6
2
1 0 1 0 0 
1 5
2 4
6
2
0 1 1 1 0 
0 4
1 2
5
1
0 0 0 0 1 
1 5
8
1
0 1 1 0 0 1 0 
1 7
6
1
0 1 1 1 0...

result:

ok Accepted. Good Job!

Test #8:

score: 10
Accepted
time: 94ms
memory: 164440kb

input:

3000 3
6
3 1 1
1 4 0
1 0 1
1 2 0
5 1 0
6
0 3 1
2 4 1
1 5 1
1 4 0
4 0 0
6
2 5 0
1 5 1
3 4 0
4 0 0
3 2 1
8
2 5 0
6 7 0
0 3 0
6 0 1
1 4 0
7 5 1
3 4 1
11
7 6 1
3 5 1
2 7 1
7 10 0
1 7 0
8 7 0
9 7 0
4 7 0
5 7 0
0 7 1
6
5 1 1
2 4 1
3 0 1
2 0 0
5 4 0
8
3 1 1
1 6 0
0 7 0
2 7 1
4 5 1
4 3 1
0 6 1
6
0 2 0
1 2 0...

output:

1
5
3
1 0 1 0 0 
0 1
2 3
4 5
6
2
1 1 1 0 0 
2 5
4 3
6
1
0 1 0 0 1 
0 1
8
1
0 0 0 1 0 1 1 
1 2
8
4
1 1 1 0 0 0 0 0 0 1 
0 6
3 1
4 2
8 9
6
2
1 1 1 0 0 
0 3
0 1
8
2
1 0 0 1 1 1 1 
2 7
7 5
5
2
0 0 0 0 1 
3 0
4 5
6
1
1 1 0 1 0 
0 5
6
1
0 1 1 0 0 
0 3
6
1
0 0 1 0 1 
0 2
5
1
0 0 0 1 0 
0 4
6
1
1 1 0 1 0 
4...

result:

ok Accepted. Good Job!

Subtask #5:

score: 10
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Test #9:

score: 10
Accepted
time: 166ms
memory: 171424kb

input:

3000 4
6
2 5 2
3 4 0
2 1 0
0 1 0
0 3 2
6
2 0 2
1 4 0
5 3 0
0 4 2
0 3 0
8
4 6 2
2 5 2
1 0 2
5 0 2
1 4 2
4 7 2
3 7 2
6
0 4 0
5 2 0
2 1 0
1 0 2
5 3 2
8
5 6 2
6 3 2
6 7 2
7 4 2
2 6 2
1 4 2
0 4 2
6
1 5 0
2 1 0
3 1 0
5 0 0
2 4 0
6
5 1 2
0 5 0
2 4 2
2 5 0
4 3 0
8
7 6 0
6 1 0
2 0 0
7 3 0
3 2 0
4 0 0
5 1 0
6...

output:

1
6
1
0 0 0 0 0 
4 5
6
2
1 0 0 0 0 
0 2
1 5
8
2
1 0 0 0 0 0 0 
4 6
2 3
6
1
0 0 0 0 0 
3 4
7
3
1 0 0 0 0 0 1 
0 4
2 5
1 3
5
1
0 0 0 0 0 
0 4
6
2
1 0 0 0 0 
1 5
0 3
8
1
0 0 0 0 0 0 0 
4 5
6
1
0 0 0 0 0 
2 5
5
1
0 0 0 0 0 
2 4
8
2
0 1 0 0 0 0 0 
0 1
5 6
8
2
0 0 1 0 0 0 0 
2 3
5 7
6
1
0 0 0 0 0 
3 5
6
1...

result:

ok Accepted. Good Job!

Test #10:

score: 10
Accepted
time: 114ms
memory: 169620kb

input:

3000 0
6
4 0 0
1 4 1
5 3 0
3 2 1
0 5 1
8
1 7 0
6 1 0
4 2 0
4 1 1
5 4 0
4 3 0
0 4 1
8
3 1 0
2 3 0
3 0 0
4 7 0
5 7 0
7 6 0
7 3 0
6
5 2 2
4 0 2
0 3 2
5 4 2
1 3 2
4
2 3 1
3 0 1
1 3 1
5
0 2 1
2 4 0
1 4 2
3 4 0
6
1 0 0
4 2 0
4 5 0
3 5 0
2 0 0
5
0 1 0
0 2 0
0 3 0
0 4 0
6
1 4 1
1 3 1
1 5 1
0 2 0
1 2 0
5
0 2...

output:

1
6
2
0 1 0 1 1 
1 4
4 2
6
3
0 0 0 1 0 0 1 
0 4
2 6
3 5
4
1
0 0 0 0 0 0 0 
0 4
6
1
0 0 0 0 0 
1 2
3
1
1 1 1 
0 2
5
2
1 0 1 0 
1 4
3 0
6
1
0 0 0 0 0 
1 3
3
1
0 0 0 0 
1 2
6
2
1 1 1 0 0 
3 4
0 5
5
2
1 0 0 0 
0 1
3 4
5
3
0 1 0 1 0 
2 3
0 5
1 4
6
4
1 1 1 1 1 0 1 
2 7
5 6
0 1
5 4
5
2
0 0 0 1 
1 3
2 4
8
2...

result:

ok Accepted. Good Job!

Subtask #6:

score: 10
Accepted

Dependency #4:

100%
Accepted

Test #11:

score: 10
Accepted
time: 493ms
memory: 224988kb

input:

3000 3
8
3 5 1
4 1 0
4 6 1
5 6 0
7 5 0
3 2 1
3 0 1
8
1 4 1
0 3 0
7 3 1
5 2 1
5 3 1
5 1 0
6 0 1
8
1 4 1
1 2 1
0 1 0
6 7 1
3 5 1
6 4 0
4 5 0
8
7 0 0
1 4 0
3 1 1
4 2 1
2 6 0
4 5 0
7 3 1
8
7 0 0
5 7 1
4 2 0
1 3 0
2 5 0
6 0 0
3 0 1
8
1 3 0
3 4 0
6 3 1
7 5 1
3 0 0
7 3 0
5 2 0
5
1 3 0
3 0 1
1 2 1
2 4 0
8
5...

output:

1
7
2
1 0 1 0 0 1 1 
0 3
1 2
7
3
1 0 1 1 1 0 1 
4 7
2 5
3 6
7
3
1 1 0 1 1 0 0 
3 4
1 2
0 7
8
2
0 0 1 1 0 0 1 
4 6
5 0
8
2
0 1 0 0 0 0 1 
0 1
4 6
7
3
0 0 1 1 0 0 0 
3 6
2 1
0 4
5
1
0 1 1 0 
4 0
7
3
1 0 1 1 1 0 0 
0 1
2 7
3 4
4
1
0 1 0 
0 2
7
3
1 1 1 0 0 1 1 
0 4
1 5
6 3
7
2
0 1 1 0 1 1 
3 6
1 5
5
2
0...

result:

ok Accepted. Good Job!

Test #12:

score: 10
Accepted
time: 412ms
memory: 218472kb

input:

3000 3
8
4 5 1
6 4 0
3 7 1
1 6 1
0 2 1
5 7 0
1 2 0
8
6 1 1
1 4 0
6 7 0
6 0 1
2 1 1
6 3 0
5 0 1
8
1 0 0
7 3 0
1 4 0
2 1 0
6 5 0
3 4 1
5 2 1
8
0 4 1
5 2 1
3 0 0
7 0 1
0 2 0
0 1 1
6 3 1
7
3 6 1
1 0 0
0 4 1
5 2 1
5 4 0
5 6 0
8
0 1 1
7 4 0
1 2 1
0 6 0
4 5 0
6 3 1
1 4 1
11
1 3 0
3 0 0
3 5 1
8 3 0
9 8 1
3 ...

output:

1
8
2
1 0 1 1 1 0 0 
0 2
2 3
7
3
1 0 0 1 1 0 1 
1 2
4 5
3 7
7
2
0 0 0 0 0 1 1 
1 7
0 6
7
3
1 1 0 1 0 1 1 
1 4
5 7
0 6
7
2
1 0 1 1 0 0 
2 5
1 3
7
2
1 0 1 0 0 1 1 
1 2
5 3
8
4
0 0 1 0 1 0 0 1 1 0 
4 5
9 0
2 7
6 10
8
2
0 1 0 0 1 0 0 
1 6
0 7
8
1
0 1 1 1 1 0 0 
7 6
7
3
0 0 0 0 1 0 1 
4 7
0 2
1 6
7
1
1 0...

result:

ok Accepted. Good Job!

Subtask #7:

score: 5
Accepted

Test #13:

score: 5
Accepted
time: 442ms
memory: 252820kb

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: 15
Accepted

Test #14:

score: 15
Accepted
time: 8987ms
memory: 1900844kb

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
3
1 0 0 0 0 1 0 
4 7
5 6
0 2
8
1
0 0 0 0 0 0 0 
2 6
8
2
0 0 0 1 0 0 0 
2 6
1 4
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
3
0 1 0 0 0 1 0 
0 1
3 5
4 7
7
7
1 0 1 1 1 1 1 0 0 0 1 0 0 
0 6
1 8
2 12
5 13
4 7
3 10
9 11
6
1
0 0 0 0 0 
0 5
6
3
1 0 0 0 0 1 
0 4
1 3
2 6
10
3
0 0 1 ...

result:

ok Accepted. Good Job!

Test #15:

score: 15
Accepted
time: 8956ms
memory: 1857296kb

input:

3000 2
8
0 5 2
2 6 2
2 3 2
4 3 2
1 5 2
1 6 2
7 4 2
8
2 3 2
1 5 2
6 7 2
1 4 2
6 0 2
2 5 2
3 7 2
7
4 3 2
0 6 2
6 1 2
2 4 2
4 5 2
5 6 2
6
2 0 2
1 2 2
2 4 2
4 3 2
2 5 2
7
6 4 2
1 4 2
5 4 2
3 6 2
0 2 2
4 2 2
8
3 4 2
6 3 2
2 3 2
5 3 2
0 7 2
3 0 2
1 3 2
8
1 5 2
1 2 2
2 4 2
1 6 2
0 1 2
7 1 2
3 2 2
8
7 5 2
7...

output:

1
8
1
0 0 0 0 0 0 0 
0 7
8
1
0 0 0 0 0 0 0 
0 4
6
3
1 1 0 0 0 0 
0 6
2 3
1 4
6
2
1 0 0 0 0 
0 1
3 5
7
2
0 1 0 0 0 0 
1 5
0 3
7
3
0 1 0 0 0 0 1 
1 4
2 6
5 7
6
3
0 0 0 1 1 0 0 
0 1
5 6
3 7
8
2
0 0 0 0 0 0 1 
6 7
0 3
11
1
0 0 0 0 0 0 0 0 0 0 
5 9
8
2
1 0 0 0 0 0 0 
2 6
3 7
8
2
0 0 0 0 1 0 0 
4 6
2 7
8
...

result:

ok Accepted. Good Job!

Test #16:

score: 15
Accepted
time: 9261ms
memory: 1755316kb

input:

3000 2
8
7 2 2
5 2 2
4 2 2
0 2 2
6 2 2
1 2 2
3 2 2
8
6 4 2
4 7 2
0 4 2
3 2 2
3 4 2
5 3 2
5 1 2
8
0 1 2
4 0 2
3 2 2
6 7 2
6 2 2
5 3 2
7 1 2
10
3 1 2
8 3 2
7 3 2
4 3 2
2 3 2
9 3 2
0 3 2
6 3 2
3 5 2
7
2 5 2
3 2 2
5 0 2
2 1 2
6 2 2
4 2 2
8
2 7 2
2 6 2
2 5 2
2 4 2
0 2 2
2 3 2
2 1 2
7
5 2 2
1 5 2
4 2 2
3 ...

output:

1
6
4
0 1 0 1 0 1 0 
0 7
1 2
3 5
4 6
7
3
1 0 0 1 0 0 0 
2 3
0 6
1 7
8
1
0 0 0 0 0 0 0 
4 5
7
5
1 0 1 0 1 1 1 0 0 
0 1
2 8
3 7
4 9
5 6
6
3
0 0 0 1 1 0 
1 2
3 6
0 4
6
4
0 1 0 0 1 0 1 
0 7
1 2
3 6
4 5
7
1
0 0 0 0 0 0 
0 1
6
3
0 0 1 1 0 0 
0 6
1 4
3 5
8
1
0 0 0 0 0 0 0 
2 3
7
1
0 0 0 0 0 0 
3 5
8
2
0 0 ...

result:

ok Accepted. Good Job!

Subtask #9:

score: 10
Accepted

Dependency #6:

100%
Accepted

Dependency #7:

100%
Accepted

Test #17:

score: 10
Accepted
time: 951ms
memory: 288816kb

input:

3000 3
8
1 2 0
4 6 1
2 4 1
3 4 1
4 0 0
5 6 0
4 7 1
8
6 0 0
2 6 1
5 4 1
0 4 1
2 3 0
7 1 1
5 1 0
17
8 7 0
15 7 0
5 7 1
4 5 1
2 5 1
16 5 1
10 16 0
14 5 1
6 2 0
3 5 1
12 7 0
14 0 0
3 1 0
9 5 1
13 5 1
16 11 0
14
4 3 0
2 10 1
12 1 0
9 7 0
6 13 0
5 11 0
8 12 1
6 3 1
4 1 1
0 10 0
2 8 0
7 5 1
0 11 1
8
7 6 0
...

output:

1
7
3
0 1 1 1 0 0 1 
3 0
4 7
1 5
8
1
0 1 1 1 0 1 0 
3 7
10
6
0 0 1 1 1 1 0 1 0 1 0 0 0 1 1 0 
2 8
4 9
5 11
5 13
0 1
12 15
14
1
0 1 0 0 0 0 1 1 1 0 0 1 1 
9 13
7
2
0 0 1 0 0 1 0 
7 4
2 1
7
3
1 1 1 1 1 1 0 
2 7
3 4
6 0
8
2
1 1 1 0 1 1 0 
2 0
3 5
7
3
1 1 1 0 0 1 1 
0 5
1 2
7 6
8
4
1 0 1 0 0 1 0 0 0 1 
...

result:

ok Accepted. Good Job!

Test #18:

score: 10
Accepted
time: 777ms
memory: 281740kb

input:

3000 3
8
2 7 0
3 4 0
1 0 0
7 5 1
2 3 1
6 5 0
0 4 1
11
10 5 1
2 5 1
5 9 0
5 0 0
4 1 0
3 5 0
5 1 1
6 5 0
7 5 0
8 1 1
8
3 4 1
1 3 1
7 3 0
5 3 0
5 2 0
6 0 0
0 2 1
7
2 5 1
1 3 1
1 5 0
0 6 1
0 2 0
6 4 0
7
0 3 0
2 6 1
0 4 1
5 1 1
4 6 0
1 3 1
11
1 4 0
9 4 0
10 4 1
4 2 0
7 4 0
7 6 1
4 5 0
8 4 1
4 0 0
4 3 1
6...

output:

1
8
1
0 0 0 1 1 0 1 
1 6
8
4
1 1 0 0 0 0 1 0 0 1 
8 9
2 0
3 10
6 7
8
2
1 1 0 0 0 0 1 
1 7
6 4
7
1
1 1 0 1 0 0 
4 3
7
2
0 1 1 1 0 1 
2 6
6 5
8
4
0 0 1 0 0 1 0 1 0 1 
3 10
6 9
0 8
2 5
6
2
0 1 1 1 0 
0 2
4 5
7
3
1 0 0 0 0 0 1 
4 1
3 5
0 2
11
1
0 1 0 1 0 1 1 0 0 1 
0 5
7
3
1 0 0 0 1 0 0 
6 4
0 1
3 5
7
2...

result:

ok Accepted. Good Job!

Subtask #10:

score: 10
Accepted

Dependency #5:

100%
Accepted

Dependency #8:

100%
Accepted

Dependency #9:

100%
Accepted

Test #19:

score: 10
Accepted
time: 2220ms
memory: 809272kb

input:

3000 0
8
3 2 0
0 2 1
4 1 1
5 4 0
3 6 1
7 5 1
6 1 0
8
3 1 2
4 5 0
1 6 2
5 0 0
3 2 0
7 5 2
2 4 0
8
4 7 1
5 3 0
4 0 1
6 5 1
3 1 2
2 4 1
3 4 2
11
3 2 0
8 2 0
1 5 2
0 8 2
3 9 2
0 7 2
4 3 0
6 9 2
6 5 0
10 9 2
11
10 1 2
8 4 2
8 7 2
0 4 2
8 6 2
3 9 2
2 9 2
2 1 2
0 3 2
5 8 2
7
3 5 0
0 3 1
4 2 0
5 2 1
1 4 1
1...

output:

1
8
2
0 1 1 0 1 1 0 
0 2
2 7
8
2
0 0 0 0 0 1 0 
5 7
0 6
7
3
1 0 1 1 0 1 0 
0 7
2 3
1 6
10
3
0 0 0 0 1 0 0 1 0 0 
3 9
10 1
4 7
11
2
0 0 0 0 0 0 0 0 0 1 
5 7
6 10
7
2
0 1 0 1 1 1 
0 3
3 6
8
1
0 1 0 0 0 0 1 
2 0
8
1
0 0 0 0 1 1 1 
0 1
7
3
1 1 0 1 1 1 0 
5 3
1 2
7 6
7
2
1 1 1 0 1 0 
3 5
1 4
5
1
0 1 0 1 ...

result:

ok Accepted. Good Job!

Test #20:

score: 10
Accepted
time: 1352ms
memory: 426844kb

input:

3000 0
8
0 3 0
7 1 0
0 5 0
1 4 0
2 5 0
6 2 0
4 6 0
8
1 5 0
6 0 1
2 3 1
5 7 1
4 1 1
6 4 0
3 0 0
7
4 0 0
4 6 1
6 5 0
1 4 0
6 2 1
3 4 0
8
0 5 0
4 6 2
3 7 0
1 6 0
5 1 0
0 7 0
2 4 0
11
1 4 2
6 1 0
1 0 0
2 1 0
9 8 2
8 1 0
1 7 2
1 5 2
1 3 0
10 1 0
11
1 8 1
4 9 2
4 2 0
4 10 0
3 1 0
8 5 0
4 6 0
7 5 1
0 3 1
4...

output:

1
8
1
0 0 0 0 0 0 0 
3 7
8
2
0 1 1 1 1 0 0 
2 3
3 7
6
3
0 1 0 0 1 0 
2 6
0 5
1 3
8
1
0 0 0 0 0 0 0 
2 3
8
4
1 0 0 0 1 0 1 1 0 0 
4 7
9 0
2 5
3 10
10
3
1 1 0 0 0 0 0 1 1 0 
9 2
4 7
6 10
7
3
1 0 0 0 1 0 0 
1 7
2 4
0 6
8
1
0 0 0 0 0 1 1 
2 4
6
1
1 1 0 1 0 
5 1
8
3
1 0 1 0 0 0 0 0 0 0 
1 7
3 9
6 8
9
3
0...

result:

ok Accepted. Good Job!