oj.uz

Submission #400883

# Submission time Handle Problem Language Result Execution time Memory
400883 2021-05-08T19:11:18 Z 12tqian Stray Cat (JOI20_stray) C++17
15 / 100
 66 ms 17936 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];
        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 {
        vi dep(n);
        vi par(n);
        function<void(int, int)> dfs_precomp = [&](int u, int p) {
            par[u] = p;
            each(v, g[u]) {
                if (v == p) continue;
                dep[v] = dep[u] + 1;
                dfs_precomp(v, u);
            }
        };
        dfs_precomp(0, -1);
        auto good = [&](int x) -> bool {
            if (x == 0) return true;
            if (sz(g[x]) > 2) return true;
            return false;
        };
        vi lab(n);
        vi leaf;
        function<void(int, int, int)> dfs_label = [&](int u, int p, int d) {
            d %= 6;
            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);
                }
            }
        };
        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};

    seen.pb(use);

    #define R(k) moves.pb(k); return k;
    #define F() if (x) { R(0); } else { R(1); }

    if (oriented) { 
        if (x == 0) {
            R(1);
        } else if (y == 0) {
            R(0);
        }
        if (x > y) {
            R(1);
        } else if (x < y) {
            R(0);
        }
        R(-1); // shouldn't reach here
    }

    if (x == 0 && y == 1) { // leaf nodes
        oriented = true;
        R(1);
    } else if (y == 0 && x == 1) {
        oriented = true;
        R(0);
    } 
    
    if (x > y) { // you already reached a good place
        oriented = true;
        R(1);
    } else if (x < y) {
        oriented = true;
        R(0);
    }

    int did = sz(moves);

    if (did == 0) { // first move
        if (x) { 
            R(0);
        } else {
            R(1);
        }
    } else if (did == 1) { // haven't reached solace
        if (seen[0].f == seen[0].s) { // diff, went 0 before
            if (x) {
                R(0);
            } else {
                R(-1);
            }
        } else { // same 
            if (moves.back() == 0 && x) {
                R(-1);
            } else if (moves.back() == 0 && y) {
                R(-1);
            } else {
                F();
            }
        }
    } else if (did == 2) {
        if (moves.back() == -1) {
            F();
        } else {
            R(-1);
        }
    } else if (did == 3) {
        if (moves.back() == -1) {
            R(-1);
        } else {
            F();
        }
    } else if (did == 4) {
        if (moves.back() == -1) {
            F();
        } else {
            R(-1);
        }
    } else if (did == 5) {
        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[4].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);
        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;
        }
        if (sz(use) == 2) {
            int u = use[0];
            int v = use[1];
            if (u == 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 {
        assert(false);
    }
    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:81:14: warning: variable 'good' set but not used [-Wunused-but-set-variable]
   81 |         auto good = [&](int x) -> bool {
      |              ^~~~

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

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 16724 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 48 ms 16804 KB Output is correct
4 Correct 66 ms 17836 KB Output is correct
5 Correct 66 ms 17936 KB Output is correct
6 Correct 55 ms 16540 KB Output is correct
7 Correct 54 ms 16528 KB Output is correct
8 Correct 61 ms 17336 KB Output is correct
9 Correct 61 ms 17232 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 16724 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 48 ms 16804 KB Output is correct
4 Correct 66 ms 17836 KB Output is correct
5 Correct 66 ms 17936 KB Output is correct
6 Correct 55 ms 16540 KB Output is correct
7 Correct 54 ms 16528 KB Output is correct
8 Correct 61 ms 17336 KB Output is correct
9 Correct 61 ms 17232 KB Output is correct
10 Correct 52 ms 14700 KB Output is correct
11 Correct 53 ms 14628 KB Output is correct
12 Correct 51 ms 14484 KB Output is correct
13 Correct 51 ms 14536 KB Output is correct
14 Correct 58 ms 14712 KB Output is correct
15 Correct 56 ms 15164 KB Output is correct
16 Correct 60 ms 17388 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 14396 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 47 ms 14308 KB Output is correct
4 Correct 63 ms 15716 KB Output is correct
5 Correct 63 ms 15768 KB Output is correct
6 Correct 53 ms 14400 KB Output is correct
7 Correct 52 ms 14432 KB Output is correct
8 Correct 57 ms 14956 KB Output is correct
9 Correct 62 ms 15252 KB Output is correct
10 Correct 55 ms 14736 KB Output is correct
11 Correct 56 ms 14764 KB Output is correct
12 Correct 56 ms 14736 KB Output is correct
13 Correct 55 ms 14744 KB Output is correct
14 Correct 63 ms 15084 KB Output is correct
15 Correct 59 ms 15080 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 14396 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 47 ms 14308 KB Output is correct
4 Correct 63 ms 15716 KB Output is correct
5 Correct 63 ms 15768 KB Output is correct
6 Correct 53 ms 14400 KB Output is correct
7 Correct 52 ms 14432 KB Output is correct
8 Correct 57 ms 14956 KB Output is correct
9 Correct 62 ms 15252 KB Output is correct
10 Correct 55 ms 14736 KB Output is correct
11 Correct 56 ms 14764 KB Output is correct
12 Correct 56 ms 14736 KB Output is correct
13 Correct 55 ms 14744 KB Output is correct
14 Correct 63 ms 15084 KB Output is correct
15 Correct 59 ms 15080 KB Output is correct
16 Correct 49 ms 12936 KB Output is correct
17 Correct 49 ms 13084 KB Output is correct
18 Correct 50 ms 12688 KB Output is correct
19 Correct 50 ms 12620 KB Output is correct
20 Correct 57 ms 13380 KB Output is correct
21 Correct 53 ms 12960 KB Output is correct
22 Correct 57 ms 15260 KB Output is correct
23 Correct 50 ms 12708 KB Output is correct
24 Correct 51 ms 12772 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 880 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 12612 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 12792 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -