QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#845971 | #3172. Tomb Raider | ASnown | WA | 5ms | 19560kb | C++17 | 2.7kb | 2025-01-06 20:40:42 | 2025-01-06 20:40:42 |
Judging History
answer
#include<bits/stdc++.h>
#define file(F) freopen(#F".in","r",stdin),freopen(#F".out","w",stdout)
#define lowbit(x) ((x)&-(x))
#define ALL(x) (x).begin(),(x).end()
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define popc(x) (__builtin_popcountll((x)))
#define abs(x) ((x)>=0?(x):-(x))
using namespace std;
using ll=long long;
using uint=uint32_t;
namespace asnown {
using i32=int32_t; using u32=uint32_t;
using i64=int64_t; using u64=uint64_t;
using i128=__int128_t; using u128=__uint128_t; };
template<typename T>
inline bool Max(T &x,T y) { return std::less<T>()(x,y)&&(x=y,true); }
template<typename T>
inline bool Min(T &x,T y) { return std::less<T>()(y,x)&&(x=y,true); }
void Solve();
const int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
const int N = 5e2+52,M = 2*N*N;
int n,m,k;
int id[N][N];
char mp[N][N];
vector<int> e[M];
ll cost[N];
int p[N];
int Find(int x) { return x==p[x]?x:p[x]=Find(p[x]); }
void Union(int x,int y) { if((x=Find(x))!=(y=Find(y))) p[y]=x; }
void dfs(int x,int y,int t,int rt) {
if(mp[x][y]=='#') return void(cost[rt]=1e9);
if(x<1||x>n||y<1||y>m) t^=1,x+=dx[t],y+=dy[t];
if(mp[x][y]=='V'||mp[x][y]=='H') {
int u=id[x][y];
if(bool(t&2)==(mp[x][y]=='V')) u+=k;
Union(rt,u);
return ;
}
int tx=x+dx[t],ty=y+dy[t];
if(mp[tx][ty]=='/') t^=3;
if(mp[tx][ty]=='\\') t^=2;
dfs(tx,ty,t,rt);
}
int col[N]; ll c[2];
bool check(int u) {
c[col[u]]+=cost[u];
for(auto v:e[u]) if(!~col[v]) {
col[v]=col[u]^1;
if(!check(v)) return false;
} else if(col[v]==col[u]) return false;
return true;
}
signed main() {
#ifndef ONLINE_JUDGE
#endif
cin.tie(nullptr)->sync_with_stdio(false);
Solve();
}
void Solve() {
cin>>n>>m;
vector<pair<int,int>> lion;
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) {
cin>>mp[i][j];
if(mp[i][j]=='V'||mp[i][j]=='H')
lion.emplace_back(i,j),id[i][j]=++k;
}
fill(cost+k+1,cost+k+k+1,1);
iota(p+1,p+k+k+1,1);
for(auto [x,y]:lion) {
dfs(x+1,y,0,id[x][y]+(mp[x][y]=='V'?0:k));
dfs(x-1,y,1,id[x][y]+(mp[x][y]=='V'?0:k));
dfs(x,y+1,2,id[x][y]+(mp[x][y]=='H'?0:k));
dfs(x,y-1,3,id[x][y]+(mp[x][y]=='H'?0:k));
}
for(int i=1;i<=k+k;i++) if(i!=Find(i)) cost[Find(i)]+=cost[i];
for(int i=1;i<=k;i++) {
e[Find(i)].emplace_back(Find(k+i));
e[Find(k+i)].emplace_back(Find(i));
}
ll res=0;
fill(col+1,col+k+k+1,-1);
for(int i=1;i<=k+k;i++) if(!~col[i]) {
col[i]=0; c[0]=c[1]=0;
if(!check(i)) return void(puts("-1"));
res+=min(c[0],c[1]);
}
if(res>k) puts("-1");
else printf("%lld\n",res);
}
/*
5 5
/.V.\
./.V.
..#..
.V.#.
\.V./
2 5
V...\
H...V
2 2
VV
VV
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 5ms
memory: 19560kb
input:
5 5 /.V.\ ./.V. ..#.. .V.#. \.V./
output:
3
result:
ok single line: '3'
Test #2:
score: 0
Accepted
time: 0ms
memory: 18752kb
input:
2 5 V...\ H...V
output:
-1
result:
ok single line: '-1'
Test #3:
score: 0
Accepted
time: 0ms
memory: 18132kb
input:
2 2 VV VV
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 4ms
memory: 18164kb
input:
4 3 /.\ H.. \H. ..H
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 2ms
memory: 18432kb
input:
5 5 ..... .H.V. ..... .H.H. .....
output:
1
result:
ok single line: '1'
Test #6:
score: 0
Accepted
time: 0ms
memory: 17876kb
input:
4 12 ./.....\/.\. .V\#/V./.#V\ /H/#\H../#H/ \........./.
output:
-1
result:
ok single line: '-1'
Test #7:
score: -100
Wrong Answer
time: 0ms
memory: 18636kb
input:
4 12 ./.....\/.\. .V\#/V./.#V\ /H/#\H../#H/ \\......../.
output:
-1
result:
wrong answer 1st lines differ - expected: '3', found: '-1'