oj.uz

Submission #400930

# Submission time Handle Problem Language Result Execution time Memory
400930 2021-05-08T20:52:11 Z 12tqian Stray Cat (JOI20_stray) C++17
15 / 100
 71 ms 17484 KB 
#include "Anthony.h"
#include <bits/stdc++.h>

using namespace std;

#define f1r(i, a, b) for (int i = a; i < b; ++i)
#define f0r(i, a) f1r(i, 0, a)
#define each(t, a) for (auto& t : a)

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define f first
#define s second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

using vi = vector<int>;
using pi = pair<int, int>;
using vpi = vector<pi>;
using ll = long long;

// 0 -> 1 -> 2

vi Mark(int n, int m, int a, int b, vi U, vi V) {
    vector<vi> g(n);
    auto cp = [&](int u, int v) -> pi {
        if (u > v) swap(u, v);
        return mp(u, v);
    };
    map<pi, int> conv;
    vpi ed;
    vi res(m);
    f0r(i, m) {
        int u = U[i];
        int v = V[i];
        assert(u < n);
        assert(v < n);
        conv[cp(u, v)] = i;
        g[u].pb(v);
        g[v].pb(u);
        ed.pb(cp(u, v));
    }
    if (a >= 3) { // bfs work
        vi dist(n, -1);
        list<int> que;
        dist[0] = 0;
        que.pb(0);
        while (!que.empty()) {
            int u = que.front();
            que.pop_front();
            each(v, g[u]) {
                if (dist[v] != -1) continue;
                dist[v] = dist[u] + 1;
                que.push_back(v);
            }
        }
        each(e, ed) {
            int u = e.f;
            int v = e.s;
            int id = conv[cp(u, v)];
            if (dist[u] == dist[v]) {
                res[id] = dist[u] % 3;
            } else {
                if (dist[u] > dist[v]) {
                    swap(u, v);
                }
                res[id] = dist[u] % 3;
            }
        }
    } else {
        assert(n - 1 == m);
        vi par(n);
        int cnt = 0;
        function<void(int, int)> dfs_precomp = [&](int u, int p) {
            assert(u < n);
            par[u] = p;
            each(v, g[u]) {
                if (v == p) continue;
                dfs_precomp(v, u);
            }
        };
        dfs_precomp(0, -1);
        vi lab(n);
        function<void(int, int, int)> dfs_label = [&](int u, int p, int d) {
            if (u == 0) {
                each(v, g[u]) {
                    if (v == p) continue;
                    lab[v] = 0;
                    dfs_label(v, u, 0);
                }
                return;
            }
            if (sz(g[u]) == 1) return;
            if (sz(g[u]) > 2) {
                each(v, g[u])  {
                    if (v == p) continue;
                    lab[v] = lab[u] ^ 1;
                    dfs_label(v, u, 0);
                }
            } else {
                each(v, g[u]) {
                    if (v == p) continue;
                    if (d == 0 || d == 2 || d == 5) {
                        lab[v] = lab[u] ^ 1;
                    } else {
                        lab[v] = lab[u];
                    }
                    dfs_label(v, u, (d + 1) % 6);
                }
            }
        };
        dfs_label(0, -1, -1);
        f1r(i, 1, n) {
            int id = conv[cp(i, par[i])];
            res[id] = lab[i];
        }
    }
    return res;
}


#include "Catherine.h"
#include <bits/stdc++.h>

using namespace std;

#define f1r(i, a, b) for (int i = a; i < b; ++i)
#define f0r(i, a) f1r(i, 0, a)
#define each(t, a) for (auto& t : a)

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define f first
#define s second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

using vi = vector<int>;
using pi = pair<int, int>;
using vpi = vector<pi>;
using ll = long long;

namespace {

int a, b;
vi moves; 
vpi seen;
bool oriented = false;

}  // namespace

void Init(int A, int B) {
    ::a = A;
    ::b = B;
}

int MoveT(vi& v) { 
    int x = v[0]; 
    int y = v[1];
    
    pi use = {x, y};
   
    if (sz(moves)) {
        if (moves.back() == 0) use.f++;
        else use.s++;
    }

    seen.pb(use);

    #define R(k) moves.pb(k); return k;
    #define F() if (x) { R(0); } else { R(1); }
    // R is for moving to a color
    // F is if you're on a line, move forward

    if (oriented) { // if you're already oriented
        // assert(x || y);
        if (x == 0) {
            R(1);
        } else if (y == 0) {
            R(0);
        }

        if (sz(moves)) {
            if (moves.back() == 0) x++;
            else y++;
        }
        
        if (x > y) {
            assert(y == 1);
            R(1);
        } else if (x < y) {
            assert(x == 1);
            R(0);
        }

        assert(false);
        R(-1); // shouldn't reach here
    }

    { // checking if you're already at a good place
        if (x == 0 && y == 0) { // dead end leaf node
            oriented = true;
            R(-1);
        }

        if (sz(moves)) {
            if (moves.back() == 0) x++;
            else y++;
        }
        
        if (x == 0 && y == 1) { // leaf nodes
            oriented = true;
            R(1);
        } else if (y == 0 && x == 1) {
            oriented = true;
            R(0);
        } 
        
        if (x > y && y) { // you already reached a good place
            oriented = true;
            assert(y == 1);
            if (sz(moves)) {
                if (moves.back() == 0) x--;
                else y--;
            }
            if (y == 0) {
                R(-1);
            }
            else {
                R(1);
            } 
        } else if (x < y && x) {
            oriented = true;
            assert(x == 1);
            if (sz(moves)) {
                if (moves.back() == 0) x--;
                else y--;
            }
            if (x == 0) {
                R(-1); 
            } else {
                R(0);
            }
        }

        if (sz(moves)) {
            if (moves.back() == 0) x--;
            else y--;
        }
    }
    // each(x, moves) cout << x << " ";
    // cout << endl;
    // each(x, seen) cout << "(" << x.f << ", " << x.s << ") ";
    // cout << endl;

    int did = sz(moves);

    if (did == 0) { // first move
        F();
    } else if (did == 1) { 
        if (seen[0].f == seen[0].s) { // 0 1, went 0 before
            if (x) { // go 0 if possible
                R(0);
            } else {
                R(-1);
            }
        } else { // same things
            if (moves.back() == 0 && x) {
                R(-1);
            } else if (moves.back() == 1 && y) {
                R(-1);
            } else {
                F();
            }
        }
    } else if (did == 2) {
        if (moves.back() == -1) {
            F();
        } else {
            R(-1);
        }
    } else if (did == 3) {
        F();
    } else if (did == 4) {
        if (moves[2] == -1) {
            F();
        } else {
            R(-1);
        }
    } else if (did == 5) {
        if (moves.back() == -1) {
            F();
        } else {
            R(-1);
        }
    } else if (did == 6) {
        oriented = true;
        vi came; // direction just came from
        vi other; // other direction
        { // came
            if (moves[4] == -1 && moves[5] != -1) {
                came.pb(moves[2]);
                came.pb(moves[3]);
                if (seen[4].f >= 2) {
                    came.pb(0);
                } else if (seen[4].s >= 2) {
                    came.pb(1);
                } else {
                    came.pb(came.back() ^ 1);
                }
            } else {
                came.pb(moves[4]); 
                if (seen[5].f >= 2) {
                    came.pb(0);
                } else if (seen[5].s >= 2) {
                    came.pb(1);
                } else {
                    came.pb(came.back() ^ 1);
                }
            }
        }
        { // other
            if (moves[0] != -1 && moves[1] != -1) {
                other.pb(moves[0]);
                other.pb(moves[1]);
                if (seen[2].f >= 2) {
                    other.pb(0);
                } else if (seen[2].s >= 2) {
                    other.pb(1);
                } else {
                    other.pb(other.back() ^ 1);
                }
            } else {
                other.pb(moves[0]);
                if (seen[1].f >= 2) {
                    other.pb(0);
                } else if (seen[1].s >= 2) {
                    other.pb(1);
                } else {
                    other.pb(other.back() ^ 1);
                }
            }
        }
        vi comb = came;
        reverse(all(comb));
        each(x, other) comb.pb(x);
        // cout << "COMB" << endl;
        // each(x, comb) cout << x << " ";
        // cout << endl;
        vi use;
        int i1 = 0;
        int i2 = 0;
        int sz = sz(comb);
        while (i1 != sz) {
            while (i2 < sz - 1 && comb[i2 + 1] == comb[i2]) ++i2;
            use.pb(i2 - i1 + 1);
            i1 = ++i2;
        }
        int num = 0;
        each(x, use) num += x;
        
        assert(num == 5);

        if (sz(use) == 2) {
            int x = use[0];
            int y = use[1];
            if (x == 2) {
                R(-1);
            } else {
                F();
            } 
        } else if (sz(use) == 3) {
            int x = use[0];
            int y = use[1];
            int z = use[2];
            if (x == 1) {
                if (y == 2) {
                    R(-1);
                } else if (y == 1) {
                    F();
                } else {
                    assert(false);
                }
            } else if (x == 2) {
                if (y == 2) {
                    F();
                } else {
                    assert(false);
                }
            } else if (x == 3) {
                R(-1);
            }
        } else {
            if (use[1] == 2) {
                F();
            } else {
                R(-1);
            }
        }
    } else {
        assert(false);
    }
    // cout << did << endl;
    // cout << "YA" << endl;
    assert(false);
    R(-1);
}

int MoveG(vi& y) {
    int a0 = y[0];
    int a1 = y[1];
    int a2 = y[2];
    if (a0 && a1) {
        return 0;
    } else if (a1 && a2) {
        return 1;
    } else if (a2 && a0) {
        return 2;
    } else if (a0) {
        return 0;
    } else if (a1) {
        return 1;
    } else if (a2) {
        return 2;
    }
    return -1;
}

int Move(vi y) {
    if (a >= 3) {
        return MoveG(y);
    } else {
        return MoveT(y);    
    }
}

Compilation message

Anthony.cpp: In function 'vi Mark(int, int, int, int, vi, vi)':
Anthony.cpp:74:13: warning: unused variable 'cnt' [-Wunused-variable]
   74 |         int cnt = 0;
      |             ^~~

Catherine.cpp: In function 'int MoveT(vi&)':
Catherine.cpp:246:17: warning: unused variable 'y' [-Wunused-variable]
  246 |             int y = use[1];
      |                 ^
Catherine.cpp:255:17: warning: unused variable 'z' [-Wunused-variable]
  255 |             int z = use[2];
      |                 ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 16360 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 48 ms 16396 KB Output is correct
4 Correct 71 ms 17484 KB Output is correct
5 Correct 67 ms 17460 KB Output is correct
6 Correct 56 ms 16152 KB Output is correct
7 Correct 56 ms 16156 KB Output is correct
8 Correct 62 ms 16916 KB Output is correct
9 Correct 62 ms 16832 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 16360 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 48 ms 16396 KB Output is correct
4 Correct 71 ms 17484 KB Output is correct
5 Correct 67 ms 17460 KB Output is correct
6 Correct 56 ms 16152 KB Output is correct
7 Correct 56 ms 16156 KB Output is correct
8 Correct 62 ms 16916 KB Output is correct
9 Correct 62 ms 16832 KB Output is correct
10 Correct 59 ms 14336 KB Output is correct
11 Correct 53 ms 14224 KB Output is correct
12 Correct 55 ms 14084 KB Output is correct
13 Correct 53 ms 14108 KB Output is correct
14 Correct 54 ms 14324 KB Output is correct
15 Correct 57 ms 14820 KB Output is correct
16 Correct 61 ms 17040 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 13940 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 48 ms 13792 KB Output is correct
4 Correct 64 ms 15372 KB Output is correct
5 Correct 65 ms 15348 KB Output is correct
6 Correct 53 ms 13972 KB Output is correct
7 Correct 53 ms 13972 KB Output is correct
8 Correct 61 ms 14692 KB Output is correct
9 Correct 60 ms 14648 KB Output is correct
10 Correct 56 ms 14340 KB Output is correct
11 Correct 56 ms 14252 KB Output is correct
12 Correct 56 ms 14412 KB Output is correct
13 Correct 55 ms 14360 KB Output is correct
14 Correct 60 ms 14620 KB Output is correct
15 Correct 62 ms 14676 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 13940 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 48 ms 13792 KB Output is correct
4 Correct 64 ms 15372 KB Output is correct
5 Correct 65 ms 15348 KB Output is correct
6 Correct 53 ms 13972 KB Output is correct
7 Correct 53 ms 13972 KB Output is correct
8 Correct 61 ms 14692 KB Output is correct
9 Correct 60 ms 14648 KB Output is correct
10 Correct 56 ms 14340 KB Output is correct
11 Correct 56 ms 14252 KB Output is correct
12 Correct 56 ms 14412 KB Output is correct
13 Correct 55 ms 14360 KB Output is correct
14 Correct 60 ms 14620 KB Output is correct
15 Correct 62 ms 14676 KB Output is correct
16 Correct 49 ms 12588 KB Output is correct
17 Correct 50 ms 12608 KB Output is correct
18 Correct 50 ms 12340 KB Output is correct
19 Correct 50 ms 12308 KB Output is correct
20 Correct 55 ms 12764 KB Output is correct
21 Correct 55 ms 12688 KB Output is correct
22 Correct 61 ms 14860 KB Output is correct
23 Correct 53 ms 12196 KB Output is correct
24 Correct 52 ms 12488 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 884 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 876 KB Output is correct
4 Correct 2 ms 876 KB Output is correct
5 Correct 2 ms 876 KB Output is correct
6 Correct 2 ms 872 KB Output is correct
7 Correct 2 ms 876 KB Output is correct
8 Correct 2 ms 876 KB Output is correct
9 Correct 2 ms 876 KB Output is correct
10 Correct 3 ms 876 KB Output is correct
11 Correct 2 ms 884 KB Output is correct
12 Correct 2 ms 948 KB Output is correct
13 Correct 2 ms 884 KB Output is correct
14 Correct 2 ms 876 KB Output is correct
15 Correct 2 ms 884 KB Output is correct
16 Correct 2 ms 884 KB Output is correct
17 Correct 2 ms 876 KB Output is correct
18 Correct 2 ms 872 KB Output is correct
19 Correct 2 ms 876 KB Output is correct
20 Correct 2 ms 876 KB Output is correct
21 Correct 2 ms 876 KB Output is correct
22 Correct 2 ms 876 KB Output is correct
23 Correct 2 ms 880 KB Output is correct
24 Correct 2 ms 880 KB Output is correct
25 Correct 2 ms 876 KB Output is correct
26 Correct 2 ms 884 KB Output is correct
27 Correct 2 ms 884 KB Output is correct
28 Incorrect 2 ms 888 KB Wrong Answer [5]

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 12184 KB Output is correct
2 Correct 57 ms 13948 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 44 ms 11972 KB Output is correct
5 Correct 62 ms 15996 KB Output is correct
6 Correct 61 ms 15988 KB Output is correct
7 Correct 52 ms 14908 KB Output is correct
8 Correct 53 ms 14920 KB Output is correct
9 Correct 63 ms 16016 KB Output is correct
10 Correct 64 ms 16128 KB Output is correct
11 Correct 66 ms 15888 KB Output is correct
12 Correct 62 ms 15856 KB Output is correct
13 Correct 61 ms 15888 KB Output is correct
14 Correct 61 ms 15972 KB Output is correct
15 Correct 63 ms 15960 KB Output is correct
16 Correct 67 ms 16004 KB Output is correct
17 Correct 59 ms 15552 KB Output is correct
18 Correct 59 ms 15448 KB Output is correct
19 Correct 60 ms 15436 KB Output is correct
20 Correct 63 ms 15500 KB Output is correct
21 Correct 59 ms 15620 KB Output is correct
22 Correct 60 ms 15664 KB Output is correct
23 Incorrect 47 ms 12236 KB Wrong Answer [5]
24 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 12232 KB Output is correct
2 Correct 55 ms 13708 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 44 ms 12084 KB Output is correct
5 Correct 60 ms 15940 KB Output is correct
6 Correct 61 ms 15960 KB Output is correct
7 Incorrect 51 ms 14820 KB Wrong Answer [5]
8 Halted 0 ms 0 KB -