QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #17128 | #1184. Space Gophers | Qingyu | AC ✓ | 9678ms | 38952kb | C++20 | 3.5kb | 2022-01-04 02:09:40 | 2022-05-04 13:23:40 |
Judging History
answer
#include <stdlib.h>
#include <string.h>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
typedef pair<int,int> PI;
struct hole
{
int c[3];
int k;
};
bool cmp(hole g, hole h)
{
return g.c[0]<h.c[0];
}
const int MAXN = 300000;
int parent[MAXN+2];
int find(int x)
{
if (parent[x]!=x)
parent[x] = find(parent[x]);
return parent[x];
}
void link(int x, int y)
{
x = find(x);
y = find(y);
parent[x] = y;
}
int main()
{
int TT;
scanf("%d",&TT);
while(TT--)
{
int n;
scanf("%d",&n);
vector<hole> H(n);
for(int i=0; i<n; i++)
{
scanf("%d %d %d",&H[i].c[0],&H[i].c[1],&H[i].c[2]);
H[i].k = i;
parent[i] = i;
}
map<PI,int> M[3];
for(int r=0; r<3; r++)
{
// fprintf(stderr,"%d:\n",r);
sort(H.begin(),H.end(),cmp);
for (auto &h : H)
{
if (h.c[0]!=-1)
continue;
M[r][PI(h.c[1],h.c[2])] = h.k;
// fprintf(stderr,"[%d] %d,%d -> %d\n",r,h.c[1],h.c[2],h.k);
}
int j = 0;
while(j<n && H[j].c[0]==-1)
j++;
while(j<n)
{
bool horiz = false, vert = false;
int k = j;
vector<PI> A,B,C;
while(k<n && H[k].c[0]<=H[j].c[0]+1)
{
int q = 2;
if (H[k].c[1]==-1)
horiz = true;
else
{
vert = true;
q = 1;
}
PI p = PI(H[k].c[q],H[k].k);
C.push_back(p);
if (H[k].c[0]==H[j].c[0])
A.push_back(p);
else
B.push_back(p);
k++;
}
sort(A.begin(),A.end());
sort(B.begin(),B.end());
sort(C.begin(),C.end());
for(int i=0; i+1<C.size(); i++)
if ((horiz && vert) || C[i].first==C[i+1].first)
link(C[i].second,C[i+1].second);
for(int i=0; i+1<A.size(); i++)
if (A[i+1].first<=A[i].first+1)
link(A[i].second,A[i+1].second);
for(int i=0; i+1<B.size(); i++)
if (B[i+1].first<=B[i].first+1)
link(B[i].second,B[i+1].second);
k = j;
while (j<n && H[j].c[0]==H[k].c[0])
j++;
// fprintf(stderr,"\n");
}
for(auto &x : H)
{
int t = x.c[0];
x.c[0] = x.c[1];
x.c[1] = x.c[2];
x.c[2] = t;
}
}
int q;
scanf("%d",&q);
for(int j=0; j<q; j++)
{
int h[2];
h[0] = h[1] = -1;
for(int s=0; s<2; s++)
{
int x[3];
scanf("%d %d %d",&x[0],&x[1],&x[2]);
for(int r = 0; r < 3; r++)
if (M[r].find(PI(x[(r+1)%3],x[(r+2)%3]))!=M[r].end())
h[s] = M[r][PI(x[(r+1)%3],x[(r+2)%3])];
}
// fprintf(stderr,"%d %d\n",h[0],h[1]);
printf((h[0]!=-1 && h[1]!=-1 && find(h[0])==find(h[1])) ? "YES\n" : "NO\n");
}
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 3272kb
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: 7577ms
memory: 27812kb
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: 9678ms
memory: 38952kb
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