QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#412326 | #3172. Tomb Raider | frizzfrizz | ML | 3ms | 16032kb | C++14 | 5.7kb | 2024-05-16 11:53:09 | 2024-05-16 11:53:10 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define A first
#define B second
#define SZ(x) (int)(x.size())
#define FR(i, a, b) for (int i = (a); i < (b); i++)
#define FOR(i, n) FR(i, 0, n)
int N, M, back = (int)('\\'), forw = (int)('/'), garN, gars[250005][2], dirs[4][2], mir[100][4], allVis[250005], ret[3];
int wheMem[505][505][4][3]; // [i][j][d] is -1, -1, -1 if uninitialized, if sees gargoyle, 1, garg ind, dir of ins, else 0, -1, -2
map<pair<int, int>, int> locToGar;
LL cost[2];
char grid[505][505], garDir[250005];
unordered_map<int, char> curVis; // maps vertices currently visited to 'H' or 'V'
vector<pair<int, int> > adj[250005];
bool valid(int i, int j)
{
return 0 <= i && i < N && 0 <= j && j < M;
}
char opp(char ori)
{
if (ori == 'H')
return 'V';
return 'H';
}
void assign(int garI, char ori)
{
curVis[garI] = ori;
allVis[garI] = 1;
FOR(j, adj[garI].size())
{
if (curVis.find(adj[garI][j].A) != curVis.end())
continue;
if (adj[garI][j].B == 0)
assign(adj[garI][j].A, ori);
else
assign(adj[garI][j].A, opp(ori));
}
}
void whereTo(int i, int j, int d)
{
if (wheMem[i][j][d][0] != -1)
{
FOR(k, 3)
ret[k] = wheMem[i][j][d][k];
return;
}
int moveI = i + dirs[d][0], moveJ = j + dirs[d][1];
if (valid(moveI, moveJ))
{
if (grid[moveI][moveJ] == '#')
{
wheMem[i][j][d][0] = 0;
wheMem[i][j][d][1] = -1;
wheMem[i][j][d][1] = -2;
ret[0] = 0;
ret[1] = -1;
ret[2] = -2;
return;
}
if (grid[moveI][moveJ] == 'V' || grid[moveI][moveJ] == 'H')
{
wheMem[i][j][d][0] = 1;
wheMem[i][j][d][1] = locToGar[{moveI, moveJ}];
wheMem[i][j][d][2] = d;
ret[0] = wheMem[i][j][d][0];
ret[1] = wheMem[i][j][d][1];
ret[2] = wheMem[i][j][d][2];
return;
}
if (grid[moveI][moveJ] == '.')
{
whereTo(moveI, moveJ, d);
FOR(k, 3)
wheMem[i][j][d][k] = ret[k];
return;
}
whereTo(moveI, moveJ, mir[grid[moveI][moveJ]][d]);
FOR(k, 3)
wheMem[i][j][d][k] = ret[k];
return;
}
else
{
if (grid[i][j] == '#')
{
wheMem[i][j][d][0] = 0;
wheMem[i][j][d][1] = -1;
wheMem[i][j][d][1] = -2;
ret[0] = 0;
ret[1] = -1;
ret[2] = -2;
return;
}
if (grid[i][j] == 'V' || grid[i][j] == 'H')
{
wheMem[i][j][d][0] = 1;
wheMem[i][j][d][1] = locToGar[{i, j}];
wheMem[i][j][d][2] = (d + 2) % 4;
ret[0] = wheMem[i][j][d][0];
ret[1] = wheMem[i][j][d][1];
ret[2] = wheMem[i][j][d][2];
return;
}
if (grid[i][j] == '.')
{
whereTo(i, j, (d + 2) % 4);
FOR(k, 3)
wheMem[i][j][d][k] = ret[k];
return;
}
whereTo(i, j, mir[grid[moveI][moveJ]][(d + 2) % 4]);
FOR(k, 3)
wheMem[i][j][d][k] = ret[k];
return;
}
}
void calcCost(int i)
{
for (auto p: curVis)
{
int x = p.A;
char ori = p.B;
FOR(d2, 4)
{
if (ori == 'H' && (d2 == 0 || d2 == 2))
continue;
if (ori == 'V' && (d2 == 1 || d2 == 3))
continue;
if (wheMem[gars[x][0]][gars[x][1]][d2][0] != 1)
cost[i] += 1e9;
else
{
int neiG = wheMem[gars[x][0]][gars[x][1]][d2][1], inDir = wheMem[gars[x][0]][gars[x][1]][d2][2];
if ((curVis[neiG] == 'H') != (inDir == 1 || inDir == 3))
cost[i] += 1e9;
}
}
if (ori != grid[gars[x][0]][gars[x][1]])
cost[i]++;
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> N >> M;
dirs[0][0] = -1;
dirs[0][1] = 0;
dirs[1][0] = 0;
dirs[1][1] = 1;
dirs[2][0] = 1;
dirs[2][1] = 0;
dirs[3][0] = 0;
dirs[3][1] = -1;
mir[back][0] = 3;
mir[back][1] = 2;
mir[back][2] = 1;
mir[back][3] = 0;
mir[forw][0] = 1;
mir[forw][1] = 0;
mir[forw][2] = 3;
mir[forw][3] = 2;
FOR(i, N)
{
FOR(j, M)
{
cin >> grid[i][j];
if (grid[i][j] == 'H' || grid[i][j] == 'V')
{
gars[garN][0] = i;
gars[garN][1] = j;
garDir[garN] = grid[i][j];
locToGar[{i, j}] = garN;
garN++;
}
FOR(d, 4)
{
wheMem[i][j][d][0] = -1;
wheMem[i][j][d][1] = -1;
wheMem[i][j][d][2] = -1;
}
}
}
FOR(m, garN)
{
FOR(d, 4)
{
int x = gars[m][0], y = gars[m][1];
whereTo(x, y, d);
if (wheMem[x][y][d][0] == 1)
adj[m].push_back({wheMem[x][y][d][1], (d - wheMem[x][y][d][2] + 4) % 2});
}
}
LL ans = 0;
FOR(m, garN)
{
if (allVis[m])
continue;
cost[0] = 0;
cost[1] = 0;
curVis.clear();
assign(m, 'H');
calcCost(0);
curVis.clear();
assign(m, 'V');
calcCost(1);
ans += min(cost[0], cost[1]);
}
if (ans >= 1e9)
cout << -1;
else
cout << ans;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 14640kb
input:
5 5 /.V.\ ./.V. ..#.. .V.#. \.V./
output:
3
result:
ok single line: '3'
Test #2:
score: 0
Accepted
time: 3ms
memory: 13548kb
input:
2 5 V...\ H...V
output:
-1
result:
ok single line: '-1'
Test #3:
score: 0
Accepted
time: 0ms
memory: 13916kb
input:
2 2 VV VV
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 0ms
memory: 15852kb
input:
4 3 /.\ H.. \H. ..H
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 2ms
memory: 13192kb
input:
5 5 ..... .H.V. ..... .H.H. .....
output:
1
result:
ok single line: '1'
Test #6:
score: 0
Accepted
time: 0ms
memory: 15808kb
input:
4 12 ./.....\/.\. .V\#/V./.#V\ /H/#\H../#H/ \........./.
output:
-1
result:
ok single line: '-1'
Test #7:
score: 0
Accepted
time: 3ms
memory: 13540kb
input:
4 12 ./.....\/.\. .V\#/V./.#V\ /H/#\H../#H/ \\......../.
output:
3
result:
ok single line: '3'
Test #8:
score: 0
Accepted
time: 2ms
memory: 13368kb
input:
2 2 #H V#
output:
-1
result:
ok single line: '-1'
Test #9:
score: 0
Accepted
time: 0ms
memory: 12504kb
input:
2 2 V. \#
output:
1
result:
ok single line: '1'
Test #10:
score: 0
Accepted
time: 2ms
memory: 12916kb
input:
2 2 V# \#
output:
-1
result:
ok single line: '-1'
Test #11:
score: 0
Accepted
time: 2ms
memory: 12972kb
input:
3 5 V.#.\ ./\.. \/\./
output:
-1
result:
ok single line: '-1'
Test #12:
score: 0
Accepted
time: 3ms
memory: 13052kb
input:
2 2 /# H/
output:
-1
result:
ok single line: '-1'
Test #13:
score: 0
Accepted
time: 3ms
memory: 14424kb
input:
1 1 H
output:
0
result:
ok single line: '0'
Test #14:
score: 0
Accepted
time: 3ms
memory: 12840kb
input:
2 1 V #
output:
1
result:
ok single line: '1'
Test #15:
score: 0
Accepted
time: 0ms
memory: 12712kb
input:
1 2 #H
output:
1
result:
ok single line: '1'
Test #16:
score: 0
Accepted
time: 0ms
memory: 14256kb
input:
5 5 V\#VH H/#\/ ##### /\#/V VH#\H
output:
4
result:
ok single line: '4'
Test #17:
score: 0
Accepted
time: 2ms
memory: 14132kb
input:
4 5 /.\/# .///\ .\V/. \.../
output:
1
result:
ok single line: '1'
Test #18:
score: 0
Accepted
time: 2ms
memory: 16032kb
input:
3 3 /\# \.\ #\H
output:
-1
result:
ok single line: '-1'
Test #19:
score: 0
Accepted
time: 2ms
memory: 13772kb
input:
3 3 /\# \V\ #\/
output:
-1
result:
ok single line: '-1'
Test #20:
score: 0
Accepted
time: 0ms
memory: 13116kb
input:
4 4 /..\ ./\. .H./ \./#
output:
-1
result:
ok single line: '-1'
Test #21:
score: 0
Accepted
time: 0ms
memory: 14060kb
input:
4 6 /.\... ....H\ ..HHH. \..../
output:
-1
result:
ok single line: '-1'
Test #22:
score: 0
Accepted
time: 2ms
memory: 14096kb
input:
4 4 /\/\ \/H/ /H/\ \/\/
output:
-1
result:
ok single line: '-1'
Test #23:
score: 0
Accepted
time: 2ms
memory: 12992kb
input:
6 6 ../\.. ..HH.. /H..V\ \H..H/ ..HV.. ..\/..
output:
2
result:
ok single line: '2'
Test #24:
score: 0
Accepted
time: 0ms
memory: 13388kb
input:
6 6 ../\.. ..HH#. /H..V\ \H..H/ ..HV#. ..\/..
output:
4
result:
ok single line: '4'
Test #25:
score: 0
Accepted
time: 0ms
memory: 12740kb
input:
6 6 ../\.. ..HH.. /H..V\ \H#.H/ ..HV.. ..\/..
output:
4
result:
ok single line: '4'
Test #26:
score: 0
Accepted
time: 0ms
memory: 13184kb
input:
3 2 V\ V. \/
output:
-1
result:
ok single line: '-1'
Test #27:
score: 0
Accepted
time: 0ms
memory: 15588kb
input:
5 4 V.V\ /../ \..\ /../ V.V.
output:
-1
result:
ok single line: '-1'
Test #28:
score: 0
Accepted
time: 0ms
memory: 14012kb
input:
3 2 V# .. VV
output:
-1
result:
ok single line: '-1'
Test #29:
score: 0
Accepted
time: 3ms
memory: 13144kb
input:
4 4 #V.. .VV. ..VV ...#
output:
-1
result:
ok single line: '-1'
Test #30:
score: 0
Accepted
time: 3ms
memory: 12548kb
input:
4 5 #V... .VV\. ...VV #...V
output:
-1
result:
ok single line: '-1'
Test #31:
score: -100
Memory Limit Exceeded
input:
4 7 #V.../\ .VV..// ....//. ...VV.#