QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#509213	#6315. 填数游戏	kymmykym	0	871ms	282744kb	C++14	2.1kb	2024-08-08 12:12:07	2024-08-08 12:12:08

Judging History

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

[2024-08-08 12:12:08]
评测

测评结果：0
用时：871ms
内存：282744kb

查看

[2024-08-08 12:12:07]
提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long 
const int maxn=2000005;
int n,m;
vector<int> S[maxn], T[maxn]; 
typedef pair<int,int>pi;
vector<pi>adj[maxn];
bool vis[maxn];
bool slf[maxn];
int in[maxn];
void solve(){
	cin >> n >> m;
	for(int i=1;i<=n;i++){
		T[i].clear();
		S[i].clear();
	}
	for(int i=1;i<=2*m;i++){
		adj[i].clear();
		vis[i]=slf[i]=in[i]=0;
	}
	for(int i=1;i<=n;i++){
		int num; cin >> num;
		for(int j=1;j<=num;j++){
			int x; cin >> x;
			S[i].push_back(x);
		}
	}
	for(int i=1;i<=n;i++){
		int num; cin >> num;
		for(int j=1;j<=num;j++){
			int x; cin >> x;
			T[i].push_back(x);
		}
	}
	
	for(int i=1;i<=n;i++){
		if(T[i].size() == 1){
			if(slf[T[i][0]]){
				cout<<-1<<"\n";return;
			}
			slf[T[i][0]]=1;
			adj[T[i][0]].push_back({T[i][0]+m,i});
			adj[T[i][0]].push_back({T[i][0]+m,i});
			in[T[i][0]]+=2;
			adj[T[i][0]+m].push_back({T[i][0],i});
			adj[T[i][0]+m].push_back({T[i][0],i});
			in[T[i][0]+m]+=2;
		} else{
			adj[T[i][0]].push_back({T[i][1],i});
			in[T[i][0]]++;
			adj[T[i][1]].push_back({T[i][0],i});
			in[T[i][1]]++;
		}
	}
	queue<int>qu;
	for(int i=1;i<=2*m;i++){
		if(in[i] == 0){
			vis[i]=1;
		}
		if(in[i] == 1){
			qu.push(i);
			vis[i]=1;
		}
	}
	while(qu.size()){
		int cur=qu.front();qu.pop();
		for(auto v:adj[cur]){
			if(!vis[v.first]){
				in[v.first]--;
				if(in[v.first]==1){
					qu.push(v.first);
					vis[v.first]=1;
				}
			}
		}
	}
	bool can=1;
	for(int i=1;i<=2*m;i++){
		if(!vis[i]){
			assert(in[i] != 1);
			can&=(in[i]==2);
		}
	}
	if(!can){
		cout<<-1<<"\n";
		return;
	}
	// property B
	int X=0,Y=0,XY=0;
	for(int i=1;i<=n;i++){
		sort(S[i].begin(),S[i].end());
		if(S[i][0] == i && S[i][1] == i+1){
			++XY;
		} else if(S[i][0] == i  || S[i][1] == i){
			++X;
		} else if(S[i][0] == i+1 || S[i][1] == i+1){
			++Y;
		}
	}
	if(X>Y)swap(X,Y);//X<=Y
	int diff=Y-X;
	if(diff<=XY){
		X+=diff;
		XY-=diff;
		cout<<X+XY/2<<"\n";
	} else{
		cout<<X+XY<<"\n";
	}
}
int32_t main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int tc; cin >> tc;
	while(tc--)solve();
}

源文件, 语言: C++14

详细

Pretests

Final Tests

Test #1:

score: 0

Wrong Answer

time: 16ms

memory: 148676kb

input:

output:

result:

wrong answer 1st numbers differ - expected: '4', found: '2'

Test #2:

score: 0

Wrong Answer

time: 11ms

memory: 148856kb

input:

output:

result:

wrong answer 1st numbers differ - expected: '3', found: '2'

Test #3:

score: 0

Wrong Answer

time: 23ms

memory: 148500kb

input:

output:

result:

wrong answer 1st numbers differ - expected: '6', found: '1'

Test #4:

score: 0

Wrong Answer

time: 25ms

memory: 149248kb

input:

output:

result:

wrong answer 1st numbers differ - expected: '3', found: '1'

Test #5:

score: 0

Wrong Answer

time: 19ms

memory: 148532kb

input:

output:

result:

wrong answer 1st numbers differ - expected: '3', found: '0'

Test #6:

score: 0

Wrong Answer

time: 23ms

memory: 149568kb

input:

output:

-1
-1
-1
-1
-1
-1
2
1
0
-1
-1
0
-1
1
2
2
1
-1
1
1
-1
-1
-1
-1
-1
-1
-1
-1
0
3
-1
-1
-1
1
1
-1
-1
-1
0
0
1
-1
-1
-1
1
1
0
-1
1
-1
0
1
2
1
1
0
-1
0
-1
0
0
-1
-1
2
2
-1
1
2
-1
2
2
1
-1
0
-1
0
0
-1
-1
-1
0
1
0
1
-1
-1
1
-1
-1
-1
-1
2
2
1
-1
1
2
-1
-1
-1
-1
1
-1
2
-1
0
2
0
1
-1
2
1
-1
1
2
3
-1
-1
0
1
-1
...

result:

wrong answer 7th numbers differ - expected: '0', found: '2'

Test #7:

score: 0

Wrong Answer

time: 25ms

memory: 148452kb

input:

output:

result:

wrong answer 3rd numbers differ - expected: '3', found: '4'

Test #8:

score: 0

Wrong Answer

time: 26ms

memory: 149648kb

input:

output:

result:

wrong answer 1st numbers differ - expected: '1', found: '0'

Test #9:

score: 0

Wrong Answer

time: 12ms

memory: 150016kb

input:

output:

result:

wrong answer 1st numbers differ - expected: '3', found: '0'

Test #10:

score: 0

Wrong Answer

time: 20ms

memory: 149076kb

input:

output:

result:

wrong answer 1st numbers differ - expected: '6', found: '0'

Test #11:

score: 0

Wrong Answer

time: 15ms

memory: 150008kb

input:

output:

result:

wrong answer 1st numbers differ - expected: '3', found: '0'

Test #12:

score: 0

Wrong Answer

time: 40ms

memory: 149808kb

input:

output:

result:

wrong answer 1st numbers differ - expected: '38', found: '2'

Test #13:

score: 0

Wrong Answer

time: 50ms

memory: 150212kb

input:

output:

result:

wrong answer 1st numbers differ - expected: '41', found: '0'

Test #14:

score: 0

Wrong Answer

time: 153ms

memory: 170260kb

input:

output:

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

result:

wrong answer 2nd numbers differ - expected: '0', found: '1'

Test #15:

score: 0

Wrong Answer

time: 108ms

memory: 169932kb

input:

output:

result:

wrong answer 2nd numbers differ - expected: '25', found: '29'

Test #16:

score: 0

Wrong Answer

time: 114ms

memory: 170140kb

input:

output:

result:

wrong answer 3rd numbers differ - expected: '29', found: '38'

Test #17:

score: 0

Wrong Answer

time: 122ms

memory: 169352kb

input:

output:

result:

wrong answer 1st numbers differ - expected: '28', found: '2'

Test #18:

score: 0

Wrong Answer

time: 129ms

memory: 169632kb

input:

output:

result:

wrong answer 1st numbers differ - expected: '32', found: '0'

Test #19:

score: 0

Wrong Answer

time: 91ms

memory: 163712kb

input:

output:

result:

wrong answer 1st numbers differ - expected: '48', found: '1'

Test #20:

score: 0

Wrong Answer

time: 101ms

memory: 165840kb

input:

output:

result:

wrong answer 1st numbers differ - expected: '48', found: '0'

Test #21:

score: 0

Wrong Answer

time: 130ms

memory: 169560kb

input:

output:

result:

wrong answer 1st numbers differ - expected: '34', found: '0'

Test #22:

score: 0

Wrong Answer

time: 134ms

memory: 171352kb

input:

output:

result:

wrong answer 1st numbers differ - expected: '33', found: '1'

Test #23:

score: 0

Wrong Answer

time: 871ms

memory: 282688kb

input:

output:

result:

wrong answer 1st numbers differ - expected: '32', found: '1'

Test #24:

score: 0

Wrong Answer

time: 862ms

memory: 282192kb

input:

output:

result:

wrong answer 1st numbers differ - expected: '37', found: '0'

Test #25:

score: 0

Wrong Answer

time: 863ms

memory: 282744kb

input:

output:

result:

wrong answer 1st numbers differ - expected: '38', found: '0'