Submission #786022

#	Time	Username	Problem	Language	Result	Execution time	Memory
786022		sadsa	Stray Cat (JOI20_stray)	C++17	85 / 100	42 ms	16056 KiB

Anthony

#include "Anthony.h"
#include <bits/stdc++.h>
using namespace std;

using vi = vector<int>;
using ii = pair<int, int>;
using vii = vector<ii>;

using i64 = int64_t;
using vl = vector<i64>;
using ll = pair<i64, i64>;
using vll = vector<ll>;

constexpr int iINF = numeric_limits<int>::max();
constexpr i64 lINF = numeric_limits<i64>::max();

#define RANGE(x) begin(x), end(x)

template <typename... T>
void DBG(T&&... args) {
    //((cerr << args << ' '), ...) << '\n';
}

template <typename T>
ostream &operator<<(ostream &out, const vector<T> &vec) {
    out << '{';
    for (size_t i = 0; i < vec.size()-1; ++i)
        out << vec[i] << ", ";
    out << vec.back() << '}';
    return out;
}

template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &pr) {
    out << '(' << pr.first << ", " << pr.second << ')';
    return out;
}

namespace {

vi Mark2d(int N, vi &U, vi &V) {
    int M = N-1;
    vi X(M, -1);

    vector<vector<pair<int,int>>> adj(N);

    for (int i = 0; i < M; ++i) {
        adj[U[i]].emplace_back(V[i], i);
        adj[V[i]].emplace_back(U[i], i);
    }

    DBG(adj);

    const vi sequence {1,0,1,0,0,1};

    queue<tuple<int, int, int>> q;

    for (auto [nxt, edge] : adj[0]) {
        X[edge] = sequence[0];
        q.emplace(nxt, 1, sequence[0]);
    }

    DBG("Mark");

    while (!q.empty()) {
        auto [crt, counter, prv] = q.front();
        q.pop();

        DBG(crt, counter);

        if (adj[crt].size() == 1) continue;
        if (adj[crt].size() == 2) {
            for (auto [nxt, edge] : adj[crt]) {
                if (X[edge] == -1) {
                    X[edge] = sequence[counter % sequence.size()];
                    q.emplace(nxt, counter+1, X[edge]);
                }
            }
        } else {
            for (auto [nxt, edge] : adj[crt]) {
                if (X[edge] == -1) {
                    X[edge] = !prv;
                    q.emplace(nxt, X[edge]? 1: 2, X[edge]);
                }
            }
        }
    }

    DBG(X);
    return X;

}

}  // namespace

std::vector<int> Mark(int N, int M, int A, int B,
                      std::vector<int> U, std::vector<int> V) {
    if (N == M+1) return Mark2d(N, U, V);
    while (1);
}

/*
7 6 2 6 3
6 5
5 0
0 1
1 2
2 3
3 4

12 11 2 6 4
6 5
5 0
0 1
1 2
2 3
3 4
4 7
7 8
8 9
9 10
10 11

19 18 2 12 11
0 2
1 2
2 3
3 4
4 5
4 6
6 7
3 8
8 9
8 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18

*/

Catherine

#include "Catherine.h"
#include <bits/stdc++.h>
using namespace std;

using vi = vector<int>;
using ii = pair<int, int>;
using vii = vector<ii>;

using i64 = int64_t;
using vl = vector<i64>;
using ll = pair<i64, i64>;
using vll = vector<ll>;

constexpr int iINF = numeric_limits<int>::max();
constexpr i64 lINF = numeric_limits<i64>::max();

#define RANGE(x) begin(x), end(x)

template <typename... T>
void DBG(T&&... args) {
    //((cerr << args << ' '), ...) << '\n';
}

template <typename T>
ostream &operator<<(ostream &out, const vector<T> &vec) {
    out << '{';
    for (size_t i = 0; i < vec.size()-1; ++i)
        out << vec[i] << ", ";
    out << vec.back() << '}';
    return out;
}

template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &pr) {
    out << '(' << pr.first << ", " << pr.second << ')';
    return out;
}

namespace {

int A, B;

bool found = false, first = true;
string current_path;
const string incr_way = "1101001101001";
const string decr_way = "1100101100101";

int prv = -1;

//             0      1
int move2d(int a, int b) {
    if (first) {
        DBG("FIRST!");
        int r;
        if (a+b == 1) {
            DBG("FOUND! by endpoint");
            found = true;
            r = a? 0: 1;
        } else if (a+b==2) {
            if (a == 2) {
                current_path = "00";
                r = 0;
            } else if (b == 2) {
                current_path = "11";
                r = 1;
            } else {
                current_path = "10";
                r = 0;
            }
        } else {
            DBG("FOUND! by intersection");

            r=-2;// not possible!
            if (a == 1) r = 0;
            if (b == 1) r = 1;
        }

        DBG("DONE FIRST:", r);
        first = false;
        return r;
    }

    if (a+b == 0) { // end point
        DBG("FOUND! by endpoint");
        found = true;
        return -1;
    }

    if (a+b >= 2) {
        DBG("FOUND! by intersection");
        found = true;
        if (a == 0 || b == 0) return -1;

        if (prv) b++;
        else a++;

        if (a == 1) return 0;
        if (b == 1) return 1;

        return -2; // not possible!
    }

    if (!found) {
        current_path += a? '0': '1';

        int correct = decr_way.find(current_path) != string::npos;
        int wrong = incr_way.find(current_path) != string::npos;

        DBG(current_path);
        found = true;
        if (correct + wrong == 2) found = false;
        else if (wrong) {
            DBG("FOUND! by wrong direction");
            return -1;
        }

        if (found) DBG("FOUND! by good direction");
    }

    if (a) return 0;
    else return 1;
}

}  // namespace

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

int Move(std::vector<int> y) {
    return prv = move2d(y[0], y[1]);
}

• Subtask 1: 0 / 2
• Subtask 2: 0 / 2
• Subtask 3: 0 / 2
• Subtask 4: 0 / 9
• Subtask 5: 5 / 5
• Subtask 6: 71 / 71
• Subtask 7: 9 / 9