10443 | 2024. 04. 02 17:06:39 | 111 | Labirintus | cpp17 | Elfogadva 100/100 | 365ms | 93532 KiB |
#include<bits/stdc++.h>
using namespace std;
// #define int long long
struct DSU{
vector<int>v;
vector<pair<int,int>>s;
DSU(){
}
DSU(int n):v(n,-1){
}
int find(int i){
return v[i]<0?i:find(v[i]);
}
void unite(int a,int b){
a=find(a);
b=find(b);
if(a==b){
s.emplace_back(-1,-1);
s.emplace_back(-1,-1);
return;
}
if(a>b){
swap(a,b);
}
s.emplace_back(a,v[a]);
s.emplace_back(b,v[b]);
v[a]+=v[b];
v[b]=a;
}
void undo(){
for(int i=0;i<2;i++){
auto[a,aa]=s.back();
s.pop_back();
if(a!=-1){
v[a]=aa;
}
}
}
};
int R,C;
DSU d;
int x(int r,int c){
return r*(C+1)+c;
}
void init_labyrinth(int R_,int C_,std::vector<std::vector<int>>L){
R=R_,C=C_;
d=DSU((R+1)*(C+1));
for(int i=0;i+1<C;i++){
d.unite(x(R,i),x(R,i+1));
}
for(int i=0;i+1<R;i++){
d.unite(x(i,C),x(i+1,C));
}
for(int i=1;i+1<=C;i++){
d.unite(x(0,i),x(0,i+1));
}
for(int i=1;i+1<=R;i++){
d.unite(x(i,0),x(i+1,0));
}
for(int i=0;i<R;i++){
for(int j=0;j<C;j++){
if(L[i][j]){
d.unite(x(i,j),x(i,j+1));
d.unite(x(i,j),x(i+1,j));
d.unite(x(i,j),x(i+1,j+1));
}
}
}
}
bool can_escape(int N,std::vector<int>U,std::vector<int>V){
for(int k=0;k<N;k++){
int i=U[k],j=V[k];
d.unite(x(i,j),x(i,j+1));
d.unite(x(i,j),x(i+1,j));
d.unite(x(i,j),x(i+1,j+1));
}
int ans=d.find(x(R,C-1))!=d.find(x(R-1,C));
for(int k=0;k<N;k++){
d.undo();
d.undo();
d.undo();
}
return ans;
}
#ifdef LOCAL
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int R,C,Q;
cin>>R>>C>>Q;
vector<vector<int>>L(R,vector<int>(C));
for(int i=0;i<R;i++){
for(int j=0;j<C;j++){
char c;
cin>>c;
L[i][j]=c-'0';
}
}
init_labyrinth(R,C,L);
while(Q--){
int N;
cin>>N;
vector<int>U(N),V(N);
for(int i=0;i<N;i++){
cin>>U[i]>>V[i];
}
cout<<can_escape(N,U,V)<<'\n';
}
return 0;
}
#endif
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Elfogadva | 3ms | 1996 KiB | ||||
2 | Elfogadva | 185ms | 91432 KiB | ||||
subtask2 | 15/15 | ||||||
3 | Elfogadva | 28ms | 5400 KiB | ||||
4 | Elfogadva | 8ms | 5360 KiB | ||||
5 | Elfogadva | 120ms | 3508 KiB | ||||
6 | Elfogadva | 120ms | 3084 KiB | ||||
7 | Elfogadva | 79ms | 5836 KiB | ||||
8 | Elfogadva | 81ms | 5920 KiB | ||||
subtask3 | 18/18 | ||||||
9 | Elfogadva | 170ms | 4436 KiB | ||||
10 | Elfogadva | 158ms | 4012 KiB | ||||
11 | Elfogadva | 365ms | 92560 KiB | ||||
12 | Elfogadva | 337ms | 92732 KiB | ||||
13 | Elfogadva | 344ms | 92672 KiB | ||||
14 | Elfogadva | 360ms | 92632 KiB | ||||
subtask4 | 28/28 | ||||||
15 | Elfogadva | 257ms | 92672 KiB | ||||
16 | Elfogadva | 257ms | 92668 KiB | ||||
17 | Elfogadva | 266ms | 92804 KiB | ||||
18 | Elfogadva | 164ms | 92808 KiB | ||||
19 | Elfogadva | 256ms | 92804 KiB | ||||
20 | Elfogadva | 133ms | 92808 KiB | ||||
21 | Elfogadva | 145ms | 93072 KiB | ||||
22 | Elfogadva | 256ms | 93072 KiB | ||||
23 | Elfogadva | 254ms | 93080 KiB | ||||
subtask5 | 39/39 | ||||||
24 | Elfogadva | 35ms | 3948 KiB | ||||
25 | Elfogadva | 17ms | 3780 KiB | ||||
26 | Elfogadva | 122ms | 4588 KiB | ||||
27 | Elfogadva | 120ms | 3988 KiB | ||||
28 | Elfogadva | 119ms | 4232 KiB | ||||
29 | Elfogadva | 120ms | 3984 KiB | ||||
30 | Elfogadva | 356ms | 92908 KiB | ||||
31 | Elfogadva | 340ms | 93108 KiB | ||||
32 | Elfogadva | 231ms | 93208 KiB | ||||
33 | Elfogadva | 328ms | 93224 KiB | ||||
34 | Elfogadva | 230ms | 93300 KiB | ||||
35 | Elfogadva | 230ms | 93308 KiB | ||||
36 | Elfogadva | 277ms | 93300 KiB | ||||
37 | Elfogadva | 273ms | 93184 KiB | ||||
38 | Elfogadva | 291ms | 93320 KiB | ||||
39 | Elfogadva | 284ms | 93532 KiB |