QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#845971#3172. Tomb RaiderASnownWA 5ms19560kbC++172.7kb2025-01-06 20:40:422025-01-06 20:40:42

Judging History

This is the latest submission verdict.

  • [2025-01-06 20:40:42]
  • Judged
  • Verdict: WA
  • Time: 5ms
  • Memory: 19560kb
  • [2025-01-06 20:40:42]
  • Submitted

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'