QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#409448#3172. Tomb RaiderMassachusetts Institute of Terriers (Yi Du, Mutiraj Laksanawisit)#WA 1ms3752kbC++208.8kb2024-05-12 06:26:312024-05-12 06:26:32

Judging History

This is the latest submission verdict.

  • [2024-05-12 06:26:32]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3752kb
  • [2024-05-12 06:26:31]
  • Submitted

answer

#include <bits/stdc++.h>
#define ll long long
#define pb push_back

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n, m;
	cin >> n >> m;

	vector<string> S(n);
	for(int i=0; i<n; i++) cin >> S[i];

	vector<vector<pair<int, int>>> adj(n*m);
	vector<bool> canV(n*m, true), canH(n*m, true);
	for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            if(S[i][j] == 'V' || S[i][j] == 'H')
            {
                //0 -> U, 1 -> R, 2 -> D, 3 -> L
                for(int d = 0; d < 4; d++)
                {
                    int curi = i, curj = j, dir = d;
                    bool cont = true;

                    while(cont)
                    {
                        switch(dir)
                        {
                            case 0:
                                if(curi - 1 >= 0)
                                {
                                    curi--;
                                    if(S[curi][curj] == '#')
                                    {
                                        if(dir%2==0) canV[i*m+j] = false;
                                        else canH[i*m+j] = false;

                                        cont = false;
                                    }
                                    else if(S[curi][curj] == '/') dir = 1;
                                    else if(S[curi][curj] == '\\') dir = 3;
                                    else if(S[curi][curj] == 'V' || S[curi][curj] == 'H')
                                    {
                                        adj[i*m+j].pb({curi*m+curj, (d + dir) % 2});
                                        cont = false;
                                    }
                                }
                                else
                                {
                                    if(S[curi][curj] == 'V' || S[curi][curj] == 'H')
                                    {
                                        adj[i*m+j].pb({curi*m+curj, (d + dir) % 2});
                                        cont = false;
                                    }
                                    dir = 2;
                                }
                            break;

                            case 1:
                                if(curj + 1 < m)
                                {
                                    curj++;
                                    if(S[curi][curj] == '#')
                                    {
                                        if(dir%2==0) canV[i*m+j] = false;
                                        else canH[i*m+j] = false;

                                        cont = false;
                                    }
                                    else if(S[curi][curj] == '/') dir = 0;
                                    else if(S[curi][curj] == '\\') dir = 2;
                                    else if(S[curi][curj] == 'V' || S[curi][curj] == 'H')
                                    {
                                        adj[i*m+j].pb({curi*m+curj, (d + dir) % 2});
                                        cont = false;
                                    }
                                }
                                else
                                {
                                    if(S[curi][curj] == 'V' || S[curi][curj] == 'H')
                                    {
                                        adj[i*m+j].pb({curi*m+curj, (d + dir) % 2});
                                        cont = false;
                                    }
                                    dir = 3;
                                }
                            break;

                            case 2:
                                if(curi + 1 < n)
                                {
                                    curi++;
                                    if(S[curi][curj] == '#')
                                    {
                                        if(dir%2==0) canV[i*m+j] = false;
                                        else canH[i*m+j] = false;

                                        cont = false;
                                    }
                                    else if(S[curi][curj] == '/') dir = 3;
                                    else if(S[curi][curj] == '\\') dir = 1;
                                    else if(S[curi][curj] == 'V' || S[curi][curj] == 'H')
                                    {
                                        adj[i*m+j].pb({curi*m+curj, (d + dir) % 2});
                                        cont = false;
                                    }
                                }
                                else
                                {
                                    if(S[curi][curj] == 'V' || S[curi][curj] == 'H')
                                    {
                                        adj[i*m+j].pb({curi*m+curj, (d + dir) % 2});
                                        cont = false;
                                    }
                                    dir = 0;
                                }
                            break;

                            case 3:
                                if(curj - 1 >= 0)
                                {
                                    curj--;
                                    if(S[curi][curj] == '#')
                                    {
                                        if(dir%2==0) canV[i*m+j] = false;
                                        else canH[i*m+j] = false;

                                        cont = false;
                                    }
                                    else if(S[curi][curj] == '/') dir = 2;
                                    else if(S[curi][curj] == '\\') dir = 0;
                                    else if(S[curi][curj] == 'V' || S[curi][curj] == 'H')
                                    {
                                        adj[i*m+j].pb({curi*m+curj, (d + dir) % 2});
                                        cont = false;
                                    }
                                }
                                else
                                {
                                    if(S[curi][curj] == 'V' || S[curi][curj] == 'H')
                                    {
                                        adj[i*m+j].pb({curi*m+curj, (d + dir) % 2});
                                        cont = false;
                                    }
                                    dir = 1;
                                }
                            break;
                        }
                    }
                }
            }
        }
    }

    /*for(vector<pair<int, int>> vp: adj)
    {
        for(pair<int, int> p: vp)
        {
            cout << "(" << p.first << ", " << p.second << ") ";
        }
        cout << "\n";
    }*/

    bool valid = true;
    int ans = 0;
    vector<int> c(n*m, -1);
    for(int i=0; i<n*m; i++)
    {
        if(c[i]==-1 && (S[i/m][i%m] == 'V' || S[i/m][i%m] == 'H'))
        {
            c[i] = 0;
            vector<int> cc;
            queue<int> Q;
            Q.push(i);

            while(valid && !Q.empty())
            {
                int p = Q.front();
                cc.pb(p);
                Q.pop();

                for(pair<int, int> x: adj[p])
                {
                    int v = x.first, d = x.second;

                    if(c[v]==-1)
                    {
                        c[v] = (c[p] + d) % 2;
                        Q.push(v);
                    }
                    else if(c[v] != (c[p] + d) % 2)
                    {
                        valid = false;
                    }
                }
            }

            if(!valid) break;

            bool H = true, V = true;
            int cH = 0, cV = 0;
            for(int x: cc)
            {
                if(c[x] == 0)
                {
                    if(canH[x]) cH += S[x/m][x%m] == 'V';
                    else H = false;

                    if(canV[x]) cV += S[x/m][x%m] == 'H';
                    else V = false;
                }
                else
                {
                    if(canV[x]) cH += S[x/m][x%m] == 'H';
                    else H = false;

                    if(canH[x]) cV += S[x/m][x%m] == 'V';
                    else V = false;
                }
            }

            //cout << i << " : " << H << " -> " << cH << " " << V << " -> " << cV << "\n";

            if(!H && !V) valid = false;
            else if(H && V) ans += min(cH, cV);
            else if(H) ans += cH;
            else ans += cV;
        }
    }

    if(valid) cout << ans;
    else cout << -1;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3516kb

input:

5 5
/.V.\
./.V.
..#..
.V.#.
\.V./

output:

3

result:

ok single line: '3'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3752kb

input:

2 5
V...\
H...V

output:

-1

result:

ok single line: '-1'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3552kb

input:

2 2
VV
VV

output:

0

result:

ok single line: '0'

Test #4:

score: 0
Accepted
time: 1ms
memory: 3752kb

input:

4 3
/.\
H..
\H.
..H

output:

1

result:

ok single line: '1'

Test #5:

score: 0
Accepted
time: 1ms
memory: 3504kb

input:

5 5
.....
.H.V.
.....
.H.H.
.....

output:

1

result:

ok single line: '1'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3468kb

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: 3520kb

input:

4 12
./.....\/.\.
.V\#/V./.#V\
/H/#\H../#H/
\\......../.

output:

-1

result:

wrong answer 1st lines differ - expected: '3', found: '-1'