QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#509221	#6315. 填数游戏	kymmykym	0	809ms	282760kb	C++14	2.4kb	2024-08-08 12:15:58	2024-08-08 12:15:59

Judging History

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

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

测评结果：0
用时：809ms
内存：282760kb

查看

[2024-08-08 12:15:58]
提交

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];
const int inf = 1'000'000'000ll;
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++){
		if(i!=n){
			sort(S[i].begin(),S[i].end());
			if(S[i].size() == 1)S[i].push_back(inf);
			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;
			}
		} else{
			if(S[i][0] == 1 && S[i][1] == n){
				++XY;
			} else if(S[i][0]==i || S[i][1] == i){
				++X;
			} else if(S[i][0] == 1 || S[i][1] == 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: 8ms

memory: 144172kb

input:

output:

result:

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

Test #2:

score: 0

Wrong Answer

time: 32ms

memory: 144172kb

input:

output:

result:

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

Test #3:

score: 0

Wrong Answer

time: 19ms

memory: 144392kb

input:

output:

result:

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

Test #4:

score: 0

Wrong Answer

time: 28ms

memory: 148780kb

input:

output:

result:

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

Test #5:

score: 0

Wrong Answer

time: 11ms

memory: 144904kb

input:

output:

result:

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

Test #6:

score: 0

Wrong Answer

time: 21ms

memory: 145520kb

input:

output:

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

result:

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

Test #7:

score: 0

Wrong Answer

time: 20ms

memory: 146132kb

input:

output:

result:

wrong answer 8th numbers differ - expected: '3', found: '2'

Test #8:

score: 0

Wrong Answer

time: 15ms

memory: 145656kb

input:

output:

result:

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

Test #9:

score: 0

Wrong Answer

time: 19ms

memory: 146236kb

input:

output:

result:

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

Test #10:

score: 0

Wrong Answer

time: 21ms

memory: 145736kb

input:

output:

result:

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

Test #11:

score: 0

Wrong Answer

time: 19ms

memory: 144472kb

input:

output:

result:

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

Test #12:

score: 0

Wrong Answer

time: 44ms

memory: 146172kb

input:

output:

result:

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

Test #13:

score: 0

Wrong Answer

time: 35ms

memory: 146184kb

input:

output:

result:

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

Test #14:

score: 0

Wrong Answer

time: 133ms

memory: 166408kb

input:

output:

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

result:

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

Test #15:

score: 0

Wrong Answer

time: 107ms

memory: 163872kb

input:

output:

result:

wrong answer 15th numbers differ - expected: '33', found: '32'

Test #16:

score: 0

Wrong Answer

time: 110ms

memory: 164404kb

input:

output:

result:

wrong answer 32nd numbers differ - expected: '26', found: '27'

Test #17:

score: 0

Wrong Answer

time: 130ms

memory: 165428kb

input:

output:

result:

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

Test #18:

score: 0

Wrong Answer

time: 109ms

memory: 166256kb

input:

output:

result:

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

Test #19:

score: 0

Wrong Answer

time: 92ms

memory: 160004kb

input:

output:

result:

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

Test #20:

score: 0

Wrong Answer

time: 91ms

memory: 159760kb

input:

output:

result:

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

Test #21:

score: 0

Wrong Answer

time: 116ms

memory: 166596kb

input:

output:

result:

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

Test #22:

score: 0

Wrong Answer

time: 136ms

memory: 165344kb

input:

output:

result:

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

Test #23:

score: 0

Wrong Answer

time: 775ms

memory: 282760kb

input:

output:

result:

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

Test #24:

score: 0

Wrong Answer

time: 809ms

memory: 282432kb

input:

output:

result:

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

Test #25:

score: 0

Wrong Answer

time: 804ms

memory: 282408kb

input:

output:

result:

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