QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#489726 | #9155. 集合 | qiaozhh | 100 ✓ | 479ms | 65136kb | C++14 | 2.9kb | 2024-07-24 23:48:28 | 2024-07-24 23:48:28 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int n,m,q,ind=0;
int a[300010][3],b[300010][3],pa[600010],pb[600010],s[300010];
vector<int> G[900010];
int fa[900010],ord[900010],num[900010],to[900010];
int root[600010];
void he(int node1,int node2) {
num[node2]+=num[node1];
to[node1]=node2;
for(int i=0;i<G[node1].size();i++) {
bool boo=0;
for(int j=0;j<G[node2].size();j++) {
if(ord[G[node1][i]]==ord[G[node2][j]]) {
boo=1;he(G[node1][i],G[node2][j]);break;
}
}
if(!boo) {
G[node2].push_back(G[node1][i]);
fa[G[node1][i]]=node2;
}
}
}
int cmpa[3],cmpb[3];
void sortt(int i,bool boo) {
if(boo) {
if(cmpa[0]>cmpa[1]) swap(cmpa[0],cmpa[1]),swap(a[i][0],a[i][1]);
if(cmpa[1]>cmpa[2]) swap(cmpa[1],cmpa[2]),swap(a[i][1],a[i][2]);
if(cmpa[0]>cmpa[1]) swap(cmpa[0],cmpa[1]),swap(a[i][0],a[i][1]);
} else {
if(cmpb[0]>cmpb[1]) swap(cmpb[0],cmpb[1]),swap(b[i][0],b[i][1]);
if(cmpb[1]>cmpb[2]) swap(cmpb[1],cmpb[2]),swap(b[i][1],b[i][2]);
if(cmpb[0]>cmpb[1]) swap(cmpb[0],cmpb[1]),swap(b[i][0],b[i][1]);
}
}
int main()
{
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++) scanf("%d%d%d",&a[i][0],&a[i][1],&a[i][2]);
for(int i=1;i<=n;i++) scanf("%d%d%d",&b[i][0],&b[i][1],&b[i][2]);
for(int i=0;i<=3*n+2;i++) to[i]=-1;
int l=1,r=0;
while(l<=n) {
if(r==n) {
s[l]=r;break;
}
r++;
bool boo=0;
for(int i=0;i<3;i++) {
while(to[pa[a[r][i]]]!=-1) pa[a[r][i]]=to[pa[a[r][i]]];
while(to[pb[b[r][i]]]!=-1) pb[b[r][i]]=to[pb[b[r][i]]];
cmpa[i]=pa[a[r][i]],cmpb[i]=pb[b[r][i]];
}
sortt(r,1);sortt(r,0);
for(int i=0;i<3;i++) if(cmpa[i]!=cmpb[i]) boo=1;
if(!boo) {
s[l]=r;
for(int i=0;i<3;i++) {
if(i>0) {if(cmpa[i]==cmpa[i-1]) {
pa[a[r][i]]=ind;pb[b[r][i]]=ind;
num[cmpa[i]]--;num[ind]++;continue;
}}
G[cmpa[i]].push_back(++ind);
if(cmpa[i]==0) root[r]=ind;
fa[ind]=cmpa[i];pa[a[r][i]]=ind;pb[b[r][i]]=ind;
num[cmpa[i]]--;num[ind]=1;ord[ind]=r;
}
} else {
r--;
to[root[l]]=0;
for(int i=0;i<G[root[l]].size();i++) {
int yu=G[root[l]][i];
if(root[ord[ yu ]]==0) {
root[ord[yu]]=yu;continue;
} else {
he(yu,root[ord[yu]]);
}
}
l++;s[l]=r;
}
}
while(l<=n) {s[l]=r;l++;}
for(int i=1;i<=q;i++) {
scanf("%d%d",&l,&r);
if(s[l]>=r) cout << "Yes" << endl;
else cout << "No" << endl;
}
return 0;
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 0ms
memory: 38644kb
Pretest #2:
score: 5
Accepted
time: 3ms
memory: 38456kb
Pretest #3:
score: 5
Accepted
time: 0ms
memory: 40500kb
Pretest #4:
score: 5
Accepted
time: 3ms
memory: 38440kb
Pretest #5:
score: 5
Accepted
time: 0ms
memory: 40560kb
Pretest #6:
score: 5
Accepted
time: 0ms
memory: 40692kb
Pretest #7:
score: 5
Accepted
time: 0ms
memory: 38640kb
Pretest #8:
score: 5
Accepted
time: 2ms
memory: 38596kb
Pretest #9:
score: 5
Accepted
time: 67ms
memory: 38656kb
Pretest #10:
score: 5
Accepted
time: 64ms
memory: 38640kb
Pretest #11:
score: 5
Accepted
time: 123ms
memory: 59080kb
Pretest #12:
score: 5
Accepted
time: 120ms
memory: 61048kb
Pretest #13:
score: 5
Accepted
time: 0ms
memory: 40636kb
Pretest #14:
score: 5
Accepted
time: 5ms
memory: 40824kb
Pretest #15:
score: 5
Accepted
time: 319ms
memory: 38660kb
Pretest #16:
score: 5
Accepted
time: 311ms
memory: 40840kb
Pretest #17:
score: 5
Accepted
time: 17ms
memory: 42240kb
Pretest #18:
score: 5
Accepted
time: 12ms
memory: 41676kb
Pretest #19:
score: 5
Accepted
time: 451ms
memory: 65136kb
Pretest #20:
score: 5
Accepted
time: 479ms
memory: 64064kb
Final Tests
Test #1:
score: 5
Accepted
time: 0ms
memory: 40552kb
Test #2:
score: 5
Accepted
time: 6ms
memory: 38556kb
Test #3:
score: 5
Accepted
time: 0ms
memory: 38604kb
Test #4:
score: 5
Accepted
time: 0ms
memory: 38596kb
Test #5:
score: 5
Accepted
time: 0ms
memory: 38644kb
Test #6:
score: 5
Accepted
time: 0ms
memory: 38436kb
Test #7:
score: 5
Accepted
time: 0ms
memory: 38464kb
Test #8:
score: 5
Accepted
time: 5ms
memory: 38572kb
Test #9:
score: 5
Accepted
time: 67ms
memory: 38508kb
Test #10:
score: 5
Accepted
time: 79ms
memory: 38656kb
Test #11:
score: 5
Accepted
time: 144ms
memory: 59024kb
Test #12:
score: 5
Accepted
time: 163ms
memory: 57592kb
Test #13:
score: 5
Accepted
time: 4ms
memory: 38800kb
Test #14:
score: 5
Accepted
time: 0ms
memory: 38660kb
Test #15:
score: 5
Accepted
time: 307ms
memory: 40844kb
Test #16:
score: 5
Accepted
time: 347ms
memory: 40812kb
Test #17:
score: 5
Accepted
time: 10ms
memory: 40088kb
Test #18:
score: 5
Accepted
time: 8ms
memory: 41444kb
Test #19:
score: 5
Accepted
time: 415ms
memory: 61440kb
Test #20:
score: 5
Accepted
time: 404ms
memory: 64248kb
Extra Test:
score: 0
Extra Test Passed