QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#489726#9155. 集合qiaozhh100 ✓479ms65136kbC++142.9kb2024-07-24 23:48:282024-07-24 23:48:28

Judging History

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

  • [2024-07-24 23:48:28]
  • 评测
  • 测评结果:100
  • 用时:479ms
  • 内存:65136kb
  • [2024-07-24 23:48:28]
  • 提交

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