QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#845677#3172. Tomb RaiderAlicXWA 1ms5892kbC++206.1kb2025-01-06 18:02:212025-01-06 18:02:22

Judging History

This is the latest submission verdict.

  • [2025-01-06 18:02:22]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 5892kb
  • [2025-01-06 18:02:21]
  • Submitted

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'