Submission #904051

#	Time	Username	Problem	Language	Result	Execution time	Memory
904051		guechotjrhh	Stray Cat (JOI20_stray)	C++14	15 / 100	50 ms	16724 KiB

Anthony

#include "Anthony.h"
#include <vector>
#include<queue>
#include<iostream>
using namespace std;
#define pi pair<int,int>
#define x first
#define y second


vector<int> sequ = { 0, 1, 0, 0, 1, 1 };
int n, m;
void dfs(int i, int col, int seq, int f, vector<vector<pi>>& g, vector<int>&res) {
    if (g[i].size() == 1 && f != -1) return;
    if ((g[i].size() == 2 && f != -1) || g[i].size() == 1) {
        if (seq == -1) seq = (col == 0) ? 0 : 5;
        (seq += 1) %= 6;
        int ni = (g[i][0].x == f) ? 1 : 0;
        res[g[i][ni].y] = sequ[seq];
        dfs(g[i][ni].x, sequ[seq], seq, i, g, res);
        return;
    }
    for (pi p : g[i]) {
        if (p.x == f) continue;
        res[p.y] = 1 - col;
        dfs(p.x, 1 - col, -1, i, g, res);
    }
    
}
vector<int> Mark(int N, int M, int A, int B, vector<int> U, vector<int> V) {
    n = N; m = M;

    vector<vector<pi>> g(n);
    for (int i = 0; i < m; i++) {
        g[U[i]].push_back({ V[i],i });
        g[V[i]].push_back({ U[i],i });
    }
    if (A >= 3) {
        vector<int> dist(n, 1e9);
        dist[0] = 0;
        queue<int> q;
        q.push(0);
        while (q.size()) {
            int u = q.front(); q.pop();
            for (pi j : g[u]) {
                if (dist[j.x] > dist[u] + 1) {
                    dist[j.x] = dist[u] + 1;
                    q.push(j.x);
                }
            }
        }
        vector<int> res(m);
        for (int i = 0; i < m; i++) {
            res[i] = min(dist[U[i]] , dist[V[i]]) % 3;
        }
        return res;
    }
    else {
        vector<int> res(m);
        dfs(0, 1, -1, -1, g, res);
        return res;
    }
}

Catherine

#include "Catherine.h"
#include <vector>
#include <iostream>
using namespace std;

int v = -1,a,b;
bool flag = 0;
vector<int> last;
void Init(int A, int B) {
    a = A;
    b = B;
    v = -1;
    flag = 0;
    last.clear();
}
vector<int> seqi = { 0, 1, 0, 0, 1, 1 };
bool check() {
    for (int i = 0; i < 6; i++) {
        bool fl = 1;
        for (int j = 0; j < 5; j++) {
            if (last[j] != seqi[(i + j) % 6]) fl = 0;
        }
        if (fl) return 1;
    }
    return 0;
}
int Move(vector<int> y) {
    if (a >= 3) {
        if (v != -1) {
            (v += 2) %= 3;
            return v;
        }
        if (y[0] && !y[2]) v = 0;
        if (!y[1] && y[2]) v = 2;
        if (!y[0] && y[1]) v = 1;
        return v;
    }
    else {
        if (flag) {
            if (y[0] && y[1]) v = 1 - v;
            else if (y[0]) v = 0;
            else if (y[1]) v = 1;
            return v;
        }
        else if (v == -1) {
            if (y[0] + y[1] > 2) {
                if (y[0] > 1) v = 1;
                else v = 0;
                flag = 1;
                return v;
            }
            if (y[0] + y[1] == 1) {
                if (y[0]) v = 0;
                else v = 1;
                flag = 1;
                return v;
            }
            if (y[0]) last.push_back(0);
            if (y[1]) { v = 1; last.push_back(1);}
            if (y[0] == 2) { v = 0; last.push_back(0); }
            if (y[1] == 2) { last.push_back(1); }
            return v;
        }
        else {
            if (y[0] + y[1] > 1) {
                flag = 1;
                if (y[v]) {
                    v = 1 - v;
                    return v;
                }
                else return -1;
            }
            if (y[0] + y[1] == 0) {
                flag = 1;
                return -1;
            }
            if (y[0]) v = 0;
            else v = 1;
            last.push_back(v);
            if (last.size() < 5) return v;
            flag = 1;
            if (check()) return v;
            v = last[3];
            return -1;
        }
    }
}

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