QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#708194 | #9170. Cycle Game | 11d10xy | WA | 8ms | 34816kb | C++14 | 2.5kb | 2024-11-03 20:11:40 | 2024-11-03 20:11:40 |
Judging History
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'