QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#708194#9170. Cycle Game11d10xyWA 8ms34816kbC++142.5kb2024-11-03 20:11:402024-11-03 20:11:40

Judging History

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

  • [2024-11-03 20:11:40]
  • 评测
  • 测评结果:WA
  • 用时:8ms
  • 内存:34816kb
  • [2024-11-03 20:11:40]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int n,m,qn;
inline int id(int i,int j){
   return (i-1)*m+j;
}
inline pair<int,int>pos(int u){
   return{(u-1)/m+1,(u-1)%m+1};
}
inline bool valid(int i,int j){
   return 1<=i&&i<=n&&1<=j&&j<=m;
}
inline int id2(int i,int j){return valid(i,j)?id(i,j):n*m+1;}
inline array<pair<int,int>,4>adj(int i,int j){
   return{{{i-1,j},{i,j-1},{i+1,j},{i,j+1}}};
}
namespace dsu{
int fa[300010],sz[300010],stk[300010],tp,tot;
void init(){
   for(int i=1;i<=n*m+1;i++)sz[i]=1;
   tot=n*m+1;
}
int fr(int u){return fa[u]?fr(fa[u]):u;}
inline bool merge(int x,int y){
   if((x=fr(x))==(y=fr(y)))return false;
   if(sz[x]>sz[y])swap(x,y);
   fa[x]=y,sz[y]+=sz[x],stk[++tp]=x,tot--;
   return true;
}
void clear(int T){
   while(tp>T){
      int u=stk[tp--];
      sz[fa[u]]-=sz[u],fa[u]=0,tot++;
   }
}
}
vector<int>node[300010<<2];
bool active[300010];
int q[300010];
void put(int u,int l,int r,int L,int R,int x){
   if(L<=l&&r<=R)return node[u].push_back(x),void();
   int mid=l+r>>1;
   if(L<=mid)put(u<<1,l,mid,L,R,x);
   if(R>mid)put(u<<1|1,mid+1,r,L,R,x);
}
void solve(int u,int l,int r){
   int cur=dsu::tp;
   for(int x:node[u]){
      active[x]=true;
      auto X=pos(x);
      for(auto Y:adj(X.first,X.second)){
         int y=id2(Y.first,Y.second);
         if(active[y])dsu::merge(x,y);
      }
   }
   if(l==r){
      auto X=pos(q[l]);
      bool flag=true;
      for(auto Y:adj(X.first,X.second))if(valid(Y.first,Y.second)){
         int t0=dsu::tp,y=id(Y.first,Y.second);
         if(active[y]){if(dsu::tot>2)flag=false;}
         else{
            for(auto Z:adj(Y.first,Y.second)){
               int z=id2(Z.first,Z.second);
               if(active[z])dsu::merge(y,z);
            }
            if(dsu::tot>1)flag=false;
         }
         dsu::clear(t0);
      }
      if(flag)dsu::tot--,putchar('1');
      else{
         putchar('0');
         if(l<qn)put(1,1,qn,l+1,qn,q[l]);
      }
   }
   else{
      int mid=l+r>>1;
      solve(u<<1,l,mid);
      solve(u<<1|1,mid+1,r);
   }
   dsu::clear(cur);
   for(int x:node[u])active[x]=false;
}
int main(){
   scanf("%d%d%d",&n,&m,&qn);
   dsu::init();
   vector<int>vis(n*m+2);
   for(int i=1,x,y;i<=qn;i++){
      scanf("%d%d",&x,&y),q[i]=id(x,y);
      vis[q[i]]=1;
      if(i>1)put(1,1,qn,1,i-1,q[i]);
   }
   for(int i=1;i<=n*m;i++)if(!vis[i])node[1].push_back(i);
   active[n*m+1]=true;
   solve(1,1,qn);
   return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 8ms
memory: 34672kb

input:

4 3 7
2 1
2 2
2 3
3 1
3 2
4 1
4 2

output:

1111111

result:

ok "1111111"

Test #2:

score: 0
Accepted
time: 0ms
memory: 34816kb

input:

3 3 8
1 1
1 2
1 3
2 3
3 3
3 2
3 1
2 1

output:

11111110

result:

ok "11111110"

Test #3:

score: 0
Accepted
time: 0ms
memory: 34400kb

input:

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

output:

1111111

result:

ok "1111111"

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 34776kb

input:

9 10 50
1 9
1 6
2 3
3 1
7 4
9 4
1 3
2 5
9 2
7 9
5 6
8 10
9 5
5 5
4 10
9 7
5 9
3 2
4 5
1 1
4 7
3 6
2 8
4 3
8 6
5 10
4 8
5 4
7 2
9 6
4 2
7 8
5 2
3 5
9 1
6 1
1 5
9 9
5 8
6 3
8 8
8 4
7 7
7 1
3 7
2 2
3 10
6 9
8 3
7 6

output:

11111111111111111111101111111111111111100111111101

result:

wrong answer 1st words differ - expected: '11111111111111111111111111111111111111111111111111', found: '11111111111111111111101111111111111111100111111101'