QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#82013#2830. Data StructureAHSFNU_team_0WA 58ms14048kbC++144.0kb2023-02-26 21:36:172023-02-26 21:36:20

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-26 21:36:20]
  • 评测
  • 测评结果:WA
  • 用时:58ms
  • 内存:14048kb
  • [2023-02-26 21:36:17]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,vis[400005],pos[400005],ans;
int ax[500005],ay[500005],cnt;
vector<int> stk[200005];
set<int> s[2][2],t[3],ept;
inline int opp(int u){
	if(u>n)return u-n;
	return u+n;
}
inline void ins(int u,int v){
	if(u!=stk[pos[u]].back())return;
	if(v!=stk[pos[v]].back())return;
	if(pos[u]==pos[v])return;
	if(u>v)swap(u,v);
	if(stk[pos[u]].size()<2 || stk[pos[v]].size()<2)
		s[stk[pos[u]].size()==2][stk[pos[v]].size()==2].insert(u);
	else{
		if(stk[pos[opp(stk[pos[u]][0])]].size()<2)t[0].insert(u);
		else if(stk[pos[opp(stk[pos[v]][0])]].size()<2)t[0].insert(u);
		else if(pos[opp(stk[pos[u]][0])]==pos[v])t[1].insert(u);
		else t[2].insert(u);
	}
}
inline void del(int u,int v){
	if(u!=stk[pos[u]].back())return;
	if(v!=stk[pos[v]].back())return;
	if(pos[u]==pos[v])return;
	if(u>v)swap(u,v);
	if(stk[pos[u]].size()<2 || stk[pos[v]].size()<2)
		s[stk[pos[u]].size()==2][stk[pos[v]].size()==2].erase(u);
	else{
		if(stk[pos[opp(stk[pos[u]][0])]].size()<2)t[0].erase(u);
		else if(stk[pos[opp(stk[pos[v]][0])]].size()<2)t[0].erase(u);
		else if(pos[opp(stk[pos[u]][0])]==pos[v])t[1].erase(u);
		else t[2].erase(u);
	}
}
inline void oper(int x,int y){
	ax[++cnt]=x,ay[cnt]=y;
	if(stk[x].empty())ept.erase(x);
	if(stk[y].empty())ept.erase(y);
	for(int i=0,u,v,V;i<(int)stk[x].size();++i){
		u=stk[x][i],v=opp(u);
		del(u,v),V=pos[v];
		for(auto u:stk[V])del(u,opp(u));
	}
	for(int i=0,u,v,V;i<(int)stk[y].size();++i){
		u=stk[y][i],v=opp(u);
		del(u,v),V=pos[v];
		for(auto u:stk[V])del(u,opp(u));
	}
	pos[stk[x].back()]=y;
	stk[y].push_back(stk[x].back());
	stk[x].pop_back();
	if(stk[x].empty())ept.insert(x);
	if(stk[y].empty())ept.insert(y);
	for(int i=0,u,v,V;i<(int)stk[x].size();++i){
		u=stk[x][i],v=opp(u);
		ins(u,v),V=pos[v];
		for(auto u:stk[V])ins(u,opp(u));
	}
	for(int i=0,u,v,V;i<(int)stk[y].size();++i){
		u=stk[y][i],v=opp(u);
		ins(u,v),V=pos[v];
		for(auto u:stk[V])ins(u,opp(u));
	}
}
inline bool work(int u){
	if(ept.empty())return 0;
	int t=*ept.begin();
	oper(pos[u],t),oper(pos[u+n],t);
	return 1;
}
int main(){
	while(~scanf("%d%d",&n,&m)){
		for(int i=1;i<=m;++i)stk[i].clear();
		for(int i=1;i<=n;++i)vis[i]=0;
		for(int i=1,k;i<=m;++i){
			scanf("%d",&k);
			stk[i].resize(k);
			for(int j=0,x;j<k;++j){
				scanf("%d",&x);
				if(vis[x])x+=n;
				else vis[x]=1;
				stk[i][j]=x,pos[x]=i;
			}
		}
		for(int i=0;i<2;++i)
			for(int j=0;j<2;++j)s[i][j].clear();
		for(int i=0;i<3;++i)t[i].clear();
		ept.clear();
		for(int i=1,u,v;i<=m;++i){
			if(stk[i].empty()){
				ept.insert(i);
				continue;
			}
			u=stk[i].back(),v=opp(u);
			if(stk[pos[v]].back()==v)ins(u,v);
		}
		cnt=0,ans=1;
		while(1){
			bool fg=0;
			for(int i=0;i<2;++i){
				for(int j=0,u;j<2;++j){
					if(s[i][j].empty())continue;
					u=*s[i][j].begin();
					if(stk[pos[u]].size()==1)oper(pos[u+n],pos[u]);
					else oper(pos[u],pos[u+n]);
					fg=1;break;
				}
				if(fg)break;
			}
			if(fg)continue;
			for(int i=0;i<3;++i){
				if(t[i].empty())continue;
				if(work(*t[i].begin())){fg=1;break;}
				else{fg=0;break;}
			}
			if(!fg)break;
		}
		bool ok=0;
		for(int i=1;i<=m;++i){
			if(stk[i].size()==1)ans=0;
			if(stk[i].size()==2 && stk[i][0]!=opp(stk[i][1]))ok=1;
		}
		if(!ans){puts("-1");continue;}
		if(ok){
			for(int i=1;i<=m;++i){
				if(stk[i].empty())continue;
				if(stk[i].size()!=2)return 0;
				if(stk[i][0]==opp(stk[i][1]))continue;
				if(ept.empty()){ans=0;break;}
				oper(i,*ept.begin());
				while(1){
					bool fg=0;
					for(int i=0;i<2;++i){
						for(int j=0,u;j<2;++j){
							if(s[i][j].empty())continue;
							u=*s[i][j].begin();
							if(stk[pos[u]].size()==1)oper(pos[u+n],pos[u]);
							else oper(pos[u],pos[u+n]);
							fg=1;break;
						}
						if(fg)break;
					}
					if(!fg)break;
				}
			}
		}
		if(!ans){puts("-1");continue;}
		printf("%d\n",cnt);
		for(int i=1;i<=cnt;++i)
			printf("%d %d\n",ax[i],ay[i]);
	}
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 14048kb

input:

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

output:

3
1 3
2 3
2 1
0
-1

result:

ok 3 cases passed. max #moves/#balls = 1.500000000

Test #2:

score: 0
Accepted
time: 1ms
memory: 13072kb

input:

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

output:

1
2 1
1
3 1
1
2 1
0
0
0

result:

ok 6 cases passed. max #moves/#balls = 1.000000000

Test #3:

score: 0
Accepted
time: 0ms
memory: 11716kb

input:

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

output:

2
4 1
3 2
2
4 1
5 2
2
4 2
6 5
2
3 2
4 1
2
5 1
4 3
2
5 3
6 1
2
4 1
3 2
2
4 3
5 2
2
6 1
4 3
2
1 2
3 1
2
1 2
4 1
2
4 3
4 1
2
2 1
3 2
2
2 1
3 2
2
1 3
4 1
-1
3
2 1
3 1
3 2
3
2 1
4 1
4 2
-1
3
1 3
2 1
2 3
3
1 3
2 1
2 3
1
3 2
1
4 3
1
4 1
0
0
0

result:

ok 27 cases passed. max #moves/#balls = 1.500000000

Test #4:

score: 0
Accepted
time: 2ms
memory: 13300kb

input:

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

output:

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

result:

ok 180 cases passed. max #moves/#balls = 1.333333333

Test #5:

score: 0
Accepted
time: 2ms
memory: 10904kb

input:

4 8
1 3
1 3
1 4
1 1
1 2
1 1
1 4
1 2
4 9
1 3
0
1 2
1 1
1 4
1 1
1 4
1 2
1 3
4 10
1 1
1 3
1 3
1 2
1 2
0
1 1
1 4
1 4
0
4 8
1 4
1 3
1 2
1 2
1 1
1 4
1 1
1 3
4 9
1 4
1 3
1 1
1 3
1 4
1 2
1 1
1 2
0
4 10
1 4
1 1
1 2
1 3
0
0
1 2
1 1
1 3
1 4
4 8
1 2
1 4
1 3
1 4
1 2
1 3
1 1
1 1
4 9
1 1
1 4
1 3
1 2
1 3
1 2
0
1 4
...

output:

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

result:

ok 1575 cases passed. max #moves/#balls = 1.500000000

Test #6:

score: 0
Accepted
time: 47ms
memory: 8236kb

input:

5 10
1 1
1 4
1 2
1 4
1 5
1 2
1 3
1 5
1 1
1 3
5 11
1 1
1 3
1 1
1 2
1 5
1 2
0
1 5
1 4
1 3
1 4
5 12
1 2
0
1 1
1 5
1 2
1 4
1 3
1 4
0
1 5
1 3
1 1
5 10
1 3
1 5
1 1
1 1
1 2
1 4
1 4
1 5
1 2
1 3
5 11
1 3
1 5
1 2
1 2
1 4
1 3
1 1
1 1
0
1 4
1 5
5 12
1 3
1 4
1 2
0
1 5
1 1
1 2
1 1
1 4
1 5
0
1 3
5 10
1 4
1 5
1 3
1...

output:

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

result:

ok 17010 cases passed. max #moves/#balls = 1.400000000

Test #7:

score: 0
Accepted
time: 51ms
memory: 8868kb

input:

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

output:

6
11 5
7 4
6 1
9 2
10 8
10 3
5
5 4
5 1
7 5
9 5
9 7
-1
8
7 3
5 6
8 6
2 8
5 2
1 5
4 1
4 5
7
9 4
8 1
5 8
7 8
5 3
6 7
6 2
5
4 1
2 7
5 2
3 5
4 3
5
6 3
7 1
8 7
2 6
8 2
5
9 1
6 2
10 3
7 5
11 8
6
1 6
5 1
3 5
4 5
2 4
3 2
-1
6
12 7
3 2
11 1
10 5
8 6
9 4
3
7 6
5 7
5 3
8
1 2
7 2
9 1
4 7
4 3
5 4
8 4
8 5
6
9 5
14...

result:

ok 14285 cases passed. max #moves/#balls = 1.500000000

Test #8:

score: 0
Accepted
time: 54ms
memory: 8168kb

input:

7 10
2 4 3
1 1
2 2 2
2 4 3
2 7 7
2 6 6
2 5 5
0
1 1
0
7 12
1 2
1 6
1 6
1 5
2 4 1
1 1
2 4 3
1 7
1 5
1 3
1 2
1 7
7 15
1 4
1 6
1 2
1 4
1 6
1 5
1 7
1 1
1 3
0
1 7
1 5
1 1
1 3
1 2
7 7
2 7 3
2 2 3
2 5 7
2 1 1
2 6 6
2 2 5
2 4 4
7 12
2 3 2
1 7
2 6 3
1 4
1 2
1 5
1 1
1 4
1 5
1 1
1 6
1 7
7 14
2 3 5
0
1 2
1 6
1 4...

output:

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

result:

ok 12500 cases passed. max #moves/#balls = 1.428571429

Test #9:

score: 0
Accepted
time: 54ms
memory: 9064kb

input:

8 16
1 2
0
1 5
1 8
1 1
1 5
2 4 4
1 8
1 6
1 1
1 2
0
2 7 7
1 3
1 6
1 3
8 13
1 8
1 4
1 2
1 6
2 1 3
2 1 3
1 7
1 2
1 5
1 6
1 8
2 4 5
1 7
8 9
2 1 3
2 4 5
2 7 2
2 7 8
2 4 8
2 1 6
2 5 2
2 6 3
0
8 17
1 1
1 4
1 3
1 7
1 2
1 2
1 7
1 5
1 3
1 4
1 6
1 8
1 5
1 6
1 8
1 1
0
8 15
1 6
1 4
0
1 5
1 7
1 3
1 2
1 8
1 6
1 7
...

output:

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

result:

ok 11111 cases passed. max #moves/#balls = 1.500000000

Test #10:

score: 0
Accepted
time: 49ms
memory: 9492kb

input:

9 13
1 2
2 4 5
2 5 4
2 2 9
1 8
1 3
1 1
1 3
1 1
2 7 6
1 9
1 8
2 7 6
9 13
1 4
2 5 6
2 7 5
2 9 3
1 4
2 9 7
0
2 8 6
2 1 3
0
1 2
1 2
2 8 1
9 18
1 4
1 7
1 7
1 9
1 8
1 8
1 2
1 3
1 6
1 2
1 1
1 3
1 5
1 1
1 6
1 5
1 4
1 9
9 13
0
2 6 7
2 2 2
1 3
2 6 8
2 9 1
2 1 4
1 9
2 8 7
0
1 4
1 3
2 5 5
9 17
1 9
2 1 3
1 2
1 5...

output:

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

result:

ok 10000 cases passed. max #moves/#balls = 1.444444444

Test #11:

score: 0
Accepted
time: 58ms
memory: 9424kb

input:

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

output:

9
5 1
8 7
14 2
15 6
11 9
13 10
18 4
19 16
17 3
7
11 7
15 4
13 5
12 9
19 1
10 6
16 2
-1
10
17 7
16 13
3 1
12 2
14 9
18 8
15 10
11 6
5 4
19 5
11
19 4
12 10
16 15
17 3
9 1
14 8
5 6
13 5
7 2
18 7
18 2
7
16 8
18 12
13 6
14 10
3 1
19 17
9 5
10
16 9
6 4
12 8
14 7
17 10
15 2
18 11
3 13
5 3
5 1
10
12 8
13 10...

result:

ok 9090 cases passed. max #moves/#balls = 1.500000000

Test #12:

score: 0
Accepted
time: 57ms
memory: 9592kb

input:

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

output:

9
10 9
6 3
15 12
15 11
5 4
8 4
7 8
13 7
13 5
13
15 12
8 7
9 6
5 4
13 2
3 5
16 5
16 11
17 3
1 8
14 8
17 1
14 10
10
17 6
21 3
18 10
9 7
14 2
20 16
11 5
12 4
8 1
15 13
11
9 2
10 1
15 3
12 11
8 12
15 8
13 6
14 6
7 14
5 7
13 5
10
10 7
18 14
6 3
17 12
15 4
19 2
13 9
16 8
5 11
16 5
11
7 10
12 7
1 12
4 12
3...

result:

ok 8333 cases passed. max #moves/#balls = 1.363636364

Test #13:

score: -100
Wrong Answer
time: 55ms
memory: 11180kb

input:

12 25
1 9
1 10
1 4
1 7
1 5
1 3
1 6
1 1
1 12
1 3
1 2
1 9
1 11
1 2
0
1 10
1 7
1 12
1 11
1 4
1 6
1 5
1 1
1 8
1 8
12 19
1 2
1 12
2 8 8
2 1 3
0
2 3 4
1 5
2 11 11
2 1 5
2 9 6
1 12
1 7
1 7
2 6 9
1 2
1 4
1 10
1 10
0
12 14
2 2 4
2 8 8
2 1 3
2 9 9
2 6 12
2 6 1
0
2 10 10
2 5 5
2 3 12
0
2 4 7
2 7 2
2 11 11
12 1...

output:

12
23 8
14 11
10 6
20 3
22 5
21 7
17 4
25 24
12 1
16 2
19 13
18 9
11
15 1
13 12
18 17
11 2
9 7
6 16
4 6
9 4
10 5
14 10
14 5
9
5 7
10 7
3 10
6 3
6 5
1 6
13 1
12 13
12 6
10
8 5
14 5
3 8
1 3
7 13
12 13
7 1
4 12
6 4
14 6
12
24 11
14 7
19 5
10 1
21 12
25 16
6 2
20 4
22 8
17 9
13 3
18 15
11
12 2
5 4
8 5
1...

result:

wrong answer Should find solution [Case 5542]