QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#845677 | #3172. Tomb Raider | AlicX | WA | 1ms | 5892kb | C++20 | 6.1kb | 2025-01-06 18:02:21 | 2025-01-06 18:02:22 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define re register
#define il inline
#define pii pair<int,pair<int,int>>
#define x first
#define y second
#define gc getchar()
#define rd read()
#define debug() puts("------------")
namespace yzqwq{
il int read(){
int x=0,f=1;char ch=gc;
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=gc;}
while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=gc;
return x*f;
}
il int qmi(int a,int b,int p){
int ans=1;
while(b){
if(b&1) ans=ans*a%p;
a=a*a%p,b>>=1;
}
return ans;
}
il int gcd(int a,int b){
if(!b) return a;
return gcd(b,a%b);
}
il int lcm(int a,int b){
return a/gcd(a,b)*b;
}
il void exgcd(int a,int b,int &x,int &y){
if(!b) return x=1,y=0,void(0);
exgcd(b,a%b,x,y);
int t=x;
x=y,y=t-a/b*x;
return ;
}
il int F(int n,int a,int b,int c){
//sum{|_ (ai+b)/c _| i:0~n}
if(!n) return b/c;
if(!a) return (n+1)*(b/c);
if(a>=c||b>=c){
int x=a/b,y=b/c;
return n*(n+1)/2*x+(n+1)*y+F(n,a%c,b%c,c);
}
int m=(a*n+b)/c;
return n*m+F(m-1,c,c-b+1,a);
}
struct lb{
int d[64];
il void print(){
for(re int i=0;i<63;++i)
if(d[i]) printf("%lld:%lld\n",i,d[i]);
return ;
}
lb(){memset(d,0,sizeof(d));}
il void operator +=(int x){
for(re int i=62;i>=0;--i){
if(!(x&(1ll<<i))) continue;
if(d[i]) x^=d[i];
else return d[i]=x,void(0);
}
return ;
}
int& operator [](int x){
return d[x];
}
il void operator +=(lb &x){
for(re int i=62;i>=0;--i)
if(x[i]) *this+=x[i];
return ;
}
il friend lb operator +(lb &x,lb &y){
lb z=x;
for(re int i=62;i>=0;--i)
if(y[i]) z+=y[i];
return z;
}
il int Max_calc(){
int ans=0;
for(re int i=62;i>=0;--i)
if((ans^d[i])>ans) ans^=d[i];
return ans;
}
};
mt19937 rnd(time(0));
}
using namespace yzqwq;
const int N=2e5+10,M=2e5+10,inf=1e18;
int n,m;
char ch[505][505];
int Col[N],vis[N],fl;
vector<int> V;
vector<int> e[N];
int Val[N];
il void dfs(int u,int col){
V.push_back(u);
Col[u]=col,vis[u]=1;
// cout<<u<<" "<<Col[u]<<"\n";
for(auto v:e[u])
if(!vis[v]) dfs(v,col^1);
else if(Col[v]!=(col^1)&&v!=u) fl=1;
return ;
}
#define id(x,y) ((x-1)*m+y)
il pii run(int x,int y,int px,int py){
if(ch[x][y]=='#') return {-1,{-1,-1}};
if(x==0) return run(x+1,y,1,0);
if(x==n+1) return run(x-1,y,-1,0);
if(y==0) return run(x,y+1,0,1);
if(y==m+1) return run(x,y-1,0,-1);
if(ch[x][y]=='V'||ch[x][y]=='H') return {x,{y,(px!=0?0:1)}};
if(ch[x][y]=='.') return run(x+px,y+py,px,py);
if(ch[x][y]=='/'){
if(px==-1) return run(x,y+1,0,1);
if(px==+1) return run(x,y-1,0,-1);
if(py==-1) return run(x+1,y,1,0);
if(py==+1) return run(x-1,y,-1,0);
}
if(ch[x][y]=='\\'){
if(px==-1) return run(x,y-1,0,-1);
if(px==+1) return run(x,y+1,0,1);
if(py==-1) return run(x-1,y,-1,0);
if(py==+1) return run(x+1,y,1,0);
}
}
il void solve(){
n=rd,m=rd;
for(re int i=1;i<=n;++i)
for(re int j=1;j<=m;++j) cin>>ch[i][j];
for(re int i=1;i<=n;++i)
for(re int j=1;j<=m;++j)
if(ch[i][j]=='V'||ch[i][j]=='H'){
if(ch[i][j]=='V') Val[id(i,j)]=1,Val[id(i,j)+n*m]=0;
else Val[id(i,j)]=0,Val[id(i,j)+n*m]=1;
int Cnt=0;
// add(id(i,j),id(i,j)+n*m,inf);
pii to1=run(i,j-1,0,-1);
pii to2=run(i,j+1,0,+1);
if(to1.x==-1||to2.x==-1) ++Cnt,Val[id(i,j)]=inf;
else{
e[id(i,j)].push_back(id(to1.x,to1.y.x)+n*m*to1.y.y);
e[id(to1.x,to1.y.x)+n*m*to1.y.y].push_back(id(i,j));
e[id(i,j)].push_back(id(to2.x,to2.y.x)+n*m*to2.y.y);
e[id(to2.x,to2.y.x)+n*m*to2.y.y].push_back(id(i,j));//cout<<id(i,j)<<" "<<id(to2.x,to2.y.x)+n*m*(to2.y.y)<<"\n";
if(id(i,j)==id(to1.x,to1.y.x)&&!to1.y.y) return printf("-1\n"),void(0);
if(id(i,j)==id(to2.x,to2.y.x)&&!to2.y.y) return printf("-1\n"),void(0);
// cout<<id(i,j)<<" "<<id(to1.x,to1.y.x)+n*m*(to1.y.y)<<"\n";
}
to1=run(i-1,j,-1,0);
to2=run(i+1,j,+1,0);
if(to1.x==-1||to2.x==-1) ++Cnt,Val[id(i,j)+n*m]=inf;
else{
e[id(i,j)+n*m].push_back(id(to1.x,to1.y.x)+n*m*to1.y.y);
e[id(to1.x,to1.y.x)+n*m*to1.y.y].push_back(id(i,j)+n*m);
e[id(i,j)+n*m].push_back(id(to2.x,to2.y.x)+n*m*to2.y.y);
e[id(to2.x,to2.y.x)+n*m*to2.y.y].push_back(id(i,j)+n*m);
if(id(i,j)==id(to1.x,to1.y.x)&&to1.y.y) return printf("-1\n"),void(0);
if(id(i,j)==id(to2.x,to2.y.x)&&to2.y.y) return printf("-1\n"),void(0);
// cout<<id(i,j)+n*m<<" "<<id(to1.x,to1.y.x)+n*m*(to1.y.y)<<"\n";
// cout<<id(i,j)+n*m<<" "<<id(to2.x,to2.y.x)+n*m*(to2.y.y)<<"\n";
}
e[id(i,j)].push_back(id(i,j)+n*m);
e[id(i,j)+n*m].push_back(id(i,j));
// cout<<id(i,j)<<" "<<id(i,j)+n*m<<"\n";
if(Cnt==2) return printf("-1\n"),void(0);
}
// debug();return ;
int ans=0;
for(re int i=1;i<=n;++i)
for(re int j=1;j<=m;++j)
if(ch[i][j]=='V'||ch[i][j]=='H'){
// cout<<Val[id(i,j)]<<" "<<id(i,j)<<"\n";
// cout<<Val[id(i,j)+n*m]<<" "<<id(i,j)+n*m<<"\n";
if(!vis[id(i,j)]){
V.clear();
dfs(id(i,j),1);
if(fl) return printf("-1\n"),void(0);
int res1=0,res2=0;
for(auto x:V){
if(Col[x]==0) res1+=Val[x];
else res2+=Val[x];
}
ans+=min(res1,res2);
}
if(!vis[id(i,j)+n*m]){debug();
V.clear();
dfs(id(i,j),1);
if(fl) return printf("-1\n"),void(0);
int res1=0,res2=0;
for(auto x:V){
if(Col[x]==0) res1+=Val[x];
else res2+=Val[x];
}
ans+=min(res1,res2);
}
}
cout<<ans;
return ;
}
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
int t=1;while(t--)
solve();
return 0;
}
/*
1 3
0 28
1 9
0 34
1 17
0 42
1 23
0 48
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5740kb
input:
5 5 /.V.\ ./.V. ..#.. .V.#. \.V./
output:
3
result:
ok single line: '3'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3848kb
input:
2 5 V...\ H...V
output:
-1
result:
ok single line: '-1'
Test #3:
score: 0
Accepted
time: 1ms
memory: 5888kb
input:
2 2 VV VV
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 0ms
memory: 5736kb
input:
4 3 /.\ H.. \H. ..H
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 0ms
memory: 5708kb
input:
5 5 ..... .H.V. ..... .H.H. .....
output:
1
result:
ok single line: '1'
Test #6:
score: 0
Accepted
time: 0ms
memory: 5836kb
input:
4 12 ./.....\/.\. .V\#/V./.#V\ /H/#\H../#H/ \........./.
output:
-1
result:
ok single line: '-1'
Test #7:
score: 0
Accepted
time: 1ms
memory: 5704kb
input:
4 12 ./.....\/.\. .V\#/V./.#V\ /H/#\H../#H/ \\......../.
output:
3
result:
ok single line: '3'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3752kb
input:
2 2 #H V#
output:
-1
result:
ok single line: '-1'
Test #9:
score: 0
Accepted
time: 1ms
memory: 5732kb
input:
2 2 V. \#
output:
1
result:
ok single line: '1'
Test #10:
score: 0
Accepted
time: 1ms
memory: 3904kb
input:
2 2 V# \#
output:
-1
result:
ok single line: '-1'
Test #11:
score: 0
Accepted
time: 1ms
memory: 3844kb
input:
3 5 V.#.\ ./\.. \/\./
output:
-1
result:
ok single line: '-1'
Test #12:
score: 0
Accepted
time: 1ms
memory: 3832kb
input:
2 2 /# H/
output:
-1
result:
ok single line: '-1'
Test #13:
score: 0
Accepted
time: 1ms
memory: 5768kb
input:
1 1 H
output:
0
result:
ok single line: '0'
Test #14:
score: 0
Accepted
time: 1ms
memory: 3688kb
input:
2 1 V #
output:
1
result:
ok single line: '1'
Test #15:
score: 0
Accepted
time: 1ms
memory: 5824kb
input:
1 2 #H
output:
1
result:
ok single line: '1'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
5 5 V\#VH H/#\/ ##### /\#/V VH#\H
output:
4
result:
ok single line: '4'
Test #17:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
4 5 /.\/# .///\ .\V/. \.../
output:
1
result:
ok single line: '1'
Test #18:
score: 0
Accepted
time: 1ms
memory: 3836kb
input:
3 3 /\# \.\ #\H
output:
-1
result:
ok single line: '-1'
Test #19:
score: 0
Accepted
time: 1ms
memory: 3780kb
input:
3 3 /\# \V\ #\/
output:
-1
result:
ok single line: '-1'
Test #20:
score: 0
Accepted
time: 1ms
memory: 3848kb
input:
4 4 /..\ ./\. .H./ \./#
output:
-1
result:
ok single line: '-1'
Test #21:
score: 0
Accepted
time: 1ms
memory: 5892kb
input:
4 6 /.\... ....H\ ..HHH. \..../
output:
-1
result:
ok single line: '-1'
Test #22:
score: 0
Accepted
time: 1ms
memory: 3824kb
input:
4 4 /\/\ \/H/ /H/\ \/\/
output:
-1
result:
ok single line: '-1'
Test #23:
score: 0
Accepted
time: 1ms
memory: 3708kb
input:
6 6 ../\.. ..HH.. /H..V\ \H..H/ ..HV.. ..\/..
output:
2
result:
ok single line: '2'
Test #24:
score: 0
Accepted
time: 1ms
memory: 5816kb
input:
6 6 ../\.. ..HH#. /H..V\ \H..H/ ..HV#. ..\/..
output:
4
result:
ok single line: '4'
Test #25:
score: 0
Accepted
time: 1ms
memory: 5836kb
input:
6 6 ../\.. ..HH.. /H..V\ \H#.H/ ..HV.. ..\/..
output:
4
result:
ok single line: '4'
Test #26:
score: 0
Accepted
time: 1ms
memory: 3788kb
input:
3 2 V\ V. \/
output:
-1
result:
ok single line: '-1'
Test #27:
score: 0
Accepted
time: 1ms
memory: 5876kb
input:
5 4 V.V\ /../ \..\ /../ V.V.
output:
-1
result:
ok single line: '-1'
Test #28:
score: -100
Wrong Answer
time: 1ms
memory: 3776kb
input:
3 2 V# .. VV
output:
1000000000000000000
result:
wrong answer 1st lines differ - expected: '-1', found: '1000000000000000000'