QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#39713#1184. Space GophersFroggyguaAC ✓15381ms350680kbC++172.0kb2022-07-12 22:16:062022-07-12 22:16:09

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-07-12 22:16:09]
  • 评测
  • 测评结果:AC
  • 用时:15381ms
  • 内存:350680kb
  • [2022-07-12 22:16:06]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define N 1000030
typedef long long ll;
const int m=1e6;
int n,Q,t[N];
array<int,3> a[N];
map<array<int,3>,int> mp;
vector<int> c[3][3][N];
class Union_Set{
public:
	int f[N];
	void init(int n){
		for(int i=1;i<=n;++i){
			f[i]=i;
		}
	}
	inline int getf(int x){
		return f[x]==x?x:f[x]=getf(f[x]);
	}
	void Merge(int x,int y){
		int fx=getf(x),fy=getf(y);
		if(fx==fy)return;
		f[fy]=fx;
	}
}S;
void Solve(){
	cin>>n;
	mp.clear();
	for(int i=0;i<3;++i)
		for(int j=0;j<3;++j)
			for(int k=1;k<=m;++k)
				c[i][j][k].clear();
	for(int i=1;i<=n;++i){
		for(int j=0;j<3;++j){
			cin>>a[i][j];
			if(a[i][j]==-1)t[i]=j;
		}
		mp[a[i]]=i;
		for(int j=0;j<3;++j){
			if(t[i]==j)continue;
			c[j][t[i]][a[i][j]].push_back(i);
		}
	}
	S.init(n);
	for(int i=1;i<=n;++i){
		for(int j=0;j<3;++j){
			if(t[i]==j)continue;
			auto z=a[i];
			--z[j];
			if(mp.count(z))S.Merge(mp[z],i);
			++z[j],++z[j];
			if(mp.count(z))S.Merge(mp[z],i);
		}
	}
	cin>>Q;
	for(int z=0;z<3;++z){
		int x=(z+1)%3,y=(z+2)%3;
		for(int i=1;i<=m;++i){
			for(int j=max(1,i-1);j<=min(m,i+1);++j){
				if(!c[z][x][i].empty()&&!c[z][y][j].empty()){
					int o=-1;
					for(auto u:c[z][x][i]){
						if(~o)S.Merge(u,o);
						else o=u;
					}
					for(auto u:c[z][y][j]){
						if(~o)S.Merge(u,o);
						else o=u;
					}
				}
			}
		}
	}
	while(Q--){
		array<int,3> s,t;
		for(int i=0;i<3;++i){
			cin>>s[i];
		}
		for(int i=0;i<3;++i){
			cin>>t[i];
		}
		auto check=[&](array<int,3> s,array<int,3> t)->bool{
			for(int i=0;i<3;++i){
				auto tS=s;
				tS[i]=-1;
				int u=mp[tS];
				if(u){
					for(int j=0;j<3;++j){
						auto tT=t;
						tT[j]=-1;
						int v=mp[tT];
						if(v){
							if(S.getf(u)==S.getf(v))return true;
						}
					}
				}
			}
			return false;
		};
		cout<<(check(s,t)?"YES\n":"NO\n");
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T;
	cin>>T;
	while(T--)Solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 86ms
memory: 216592kb

input:

1
6
-1 1 1
3 -1 2
1 5 -1
5 5 -1
-1 5 5
-1 5 9
6
1 1 1 6 1 1
8 1 1 3 2 2
1 1 1 5 5 5
1 5 5 5 5 9
1 5 10 10 1 1
1 5 9 5 5 9

output:

YES
YES
NO
YES
NO
YES

result:

ok 6 tokens

Test #2:

score: 0
Accepted
time: 14140ms
memory: 333736kb

input:

6
198684
133726 -1 133718
309065 309059 -1
197284 -1 197283
398533 398535 -1
28970 28970 -1
89096 -1 89092
-1 379216 379222
137222 137217 -1
-1 137572 137568
24503 24500 -1
115679 115682 -1
-1 28060 28056
-1 378896 378904
-1 212252 212248
96643 96643 -1
228530 228526 -1
-1 76567 76567
128789 -1 1287...

output:

NO
NO
NO
YES
NO
NO
NO
YES
NO
YES
NO
NO
NO
YES
NO
NO
NO
YES
YES
YES
YES
NO
NO
NO
NO
YES
NO
NO
YES
NO
YES
YES
NO
NO
YES
NO
NO
NO
NO
NO
YES
YES
NO
NO
YES
NO
YES
NO
NO
NO
YES
NO
YES
NO
NO
NO
NO
NO
YES
NO
YES
NO
NO
NO
NO
YES
YES
NO
YES
YES
NO
YES
NO
NO
NO
YES
NO
NO
NO
NO
YES
YES
YES
YES
NO
YES
NO
NO
NO
Y...

result:

ok 1683632 tokens

Test #3:

score: 0
Accepted
time: 15381ms
memory: 350680kb

input:

5
290330
343767 -1 706239
146 -1 500134
146 -1 946276
145 -1 904565
-1 520688 984507
146 -1 889982
524887 -1 192647
146 -1 909289
449999 -1 195697
145 -1 671702
146 -1 992002
695546 -1 197856
310887 339216 -1
146 -1 104064
609792 140311 -1
146 -1 349153
146 -1 262605
145 -1 61480
781718 698227 -1
14...

output:

YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
NO
YES
YE...

result:

ok 1973149 tokens