oj.uz

답안 #400920

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
400920 2021-05-08T20:23:55 Z 12tqian 길고양이 (JOI20_stray) C++17
15 / 100
 72 ms 23792 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 par(n);
        function<void(int, int)> dfs_precomp = [&](int u, int p) {
            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.back() == -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 {
        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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 16388 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 49 ms 16272 KB Output is correct
4 Correct 69 ms 17512 KB Output is correct
5 Correct 72 ms 17664 KB Output is correct
6 Correct 56 ms 16192 KB Output is correct
7 Correct 57 ms 16084 KB Output is correct
8 Correct 65 ms 16828 KB Output is correct
9 Correct 64 ms 16880 KB Output is correct

Subtask #2
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 16388 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 49 ms 16272 KB Output is correct
4 Correct 69 ms 17512 KB Output is correct
5 Correct 72 ms 17664 KB Output is correct
6 Correct 56 ms 16192 KB Output is correct
7 Correct 57 ms 16084 KB Output is correct
8 Correct 65 ms 16828 KB Output is correct
9 Correct 64 ms 16880 KB Output is correct
10 Correct 53 ms 14268 KB Output is correct
11 Correct 53 ms 14232 KB Output is correct
12 Correct 53 ms 14224 KB Output is correct
13 Correct 52 ms 14224 KB Output is correct
14 Correct 55 ms 14316 KB Output is correct
15 Correct 63 ms 14716 KB Output is correct
16 Correct 65 ms 17032 KB Output is correct

Subtask #3
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 13992 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 48 ms 13844 KB Output is correct
4 Correct 64 ms 15376 KB Output is correct
5 Correct 65 ms 15364 KB Output is correct
6 Correct 60 ms 13888 KB Output is correct
7 Correct 55 ms 13944 KB Output is correct
8 Correct 60 ms 14536 KB Output is correct
9 Correct 60 ms 14628 KB Output is correct
10 Correct 56 ms 14288 KB Output is correct
11 Correct 56 ms 14364 KB Output is correct
12 Correct 62 ms 14288 KB Output is correct
13 Correct 56 ms 14404 KB Output is correct
14 Correct 61 ms 14724 KB Output is correct
15 Correct 61 ms 14588 KB Output is correct

Subtask #4
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 13992 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 48 ms 13844 KB Output is correct
4 Correct 64 ms 15376 KB Output is correct
5 Correct 65 ms 15364 KB Output is correct
6 Correct 60 ms 13888 KB Output is correct
7 Correct 55 ms 13944 KB Output is correct
8 Correct 60 ms 14536 KB Output is correct
9 Correct 60 ms 14628 KB Output is correct
10 Correct 56 ms 14288 KB Output is correct
11 Correct 56 ms 14364 KB Output is correct
12 Correct 62 ms 14288 KB Output is correct
13 Correct 56 ms 14404 KB Output is correct
14 Correct 61 ms 14724 KB Output is correct
15 Correct 61 ms 14588 KB Output is correct
16 Correct 50 ms 12560 KB Output is correct
17 Correct 57 ms 12644 KB Output is correct
18 Correct 52 ms 12188 KB Output is correct
19 Correct 55 ms 12280 KB Output is correct
20 Correct 56 ms 12852 KB Output is correct
21 Correct 56 ms 12716 KB Output is correct
22 Correct 59 ms 14904 KB Output is correct
23 Correct 54 ms 12416 KB Output is correct
24 Correct 53 ms 12308 KB Output is correct

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 888 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 884 KB Output is correct
6 Correct 2 ms 876 KB Output is correct
7 Correct 2 ms 880 KB Output is correct
8 Runtime error 3 ms 1264 KB Execution killed with signal 6
9 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 12160 KB Output is correct
2 Correct 56 ms 13824 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 43 ms 12440 KB Output is correct
5 Correct 63 ms 16352 KB Output is correct
6 Runtime error 57 ms 23792 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 12180 KB Output is correct
2 Correct 56 ms 13872 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 44 ms 12032 KB Output is correct
5 Correct 63 ms 15984 KB Output is correct
6 Runtime error 57 ms 23492 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -