Submission #260719

#	Time	Username	Problem	Language	Result	Execution time	Memory
260719		Kastanda	Stray Cat (JOI20_stray)	C++14	15 / 100	75 ms	20416 KiB

Anthony

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

const int N = 21234;

int D[N];
vector < int > Adj[N];
vector < pair < int , int > > Ad[N];

vector < int > Sub(int n, int m, int A, int B, vector < int > U, vector < int > V)
{
        assert(B == 0 && A >= 3);

        for (int i = 0; i < m; i ++)
                Adj[U[i]].push_back(V[i]), Adj[V[i]].push_back(U[i]);

        memset(D, -1, sizeof(D));
        queue < int > qu;
        qu.push(0); D[0] = 0;
        while (qu.size())
        {
                int v = qu.front();
                qu.pop();
                for (int u : Adj[v])
                        if (D[u] == -1)
                                D[u] = D[v] + 1, qu.push(u);
        }

        vector < int > C(m, 0);
        for (int i = 0; i < m; i ++)
        {
                int d = min(D[V[i]], D[U[i]]);
                C[i] = d % 3;
        }
        return C;
}

int C[N];
int gx[] = {1, 1, 0, 0, 1, 0};
vector < int > RS;

void DFS(int v, int p, int cc = 0)
{
        for (int i = 0; i < (int)Ad[v].size(); i ++)
                if (Ad[v][i].first == p)
                        Ad[v].erase(Ad[v].begin() + i);
        if (!Ad[v].size())
                return ;

        if (Adj[v].size() > 1)
        {
                for (auto u : Ad[v])
                        C[u.first] = !C[v], RS[u.second] = !C[v], DFS(u.first, v, 0);
                return ;
        }

        if (Adj[v].size() == 1)
        {
                C[Ad[v][0].first] = gx[cc];
                RS[Ad[v][0].second] = gx[cc];
                DFS(Ad[v][0].first, v, (cc + 1) % 6);
                return ;
        }
}

vector < int > Mark(int n, int m, int A, int B, vector < int > U, vector < int > V)
{
        if (B == 0)
                return Sub(n, m, A, B, U, V);

        assert(A == 2);
        for (int i = 0; i < m; i ++)
                Ad[U[i]].push_back({V[i], i}), Ad[V[i]].push_back({U[i], i});

        RS = vector < int >(m, 0);
        DFS(0, -1);
        return RS;

}

Catherine

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

const int N = 21234;

int cA, cB;
int prev = -1, Found = 0;

vector < int > Cur;
vector < vector < int > > vec;

void Init(int A, int B)
{
        cA = A;
        cB = B;
        prev = -1;
        Found = 0;

        vec.push_back({1, 1, 0, 1, 1, 0});
        vec.push_back({1, 1, 1, 0, 1, 1});
        vec.push_back({1, 1, 1, 1, 0, 0});
        vec.push_back({0, 2, 1, 0, 0, 1});
        vec.push_back({1, 1, 0, 0, 1, 0});
        vec.push_back({2, 0, 0, 1, 0, 1});
}

int Move2(vector < int > Freq)
{
        assert(cB == 0 && cA >= 3);

        int c = 0;
        for (int a : Freq)
                if (a) c ++;
        if (c == 1 && Freq[0])
                return 0;
        if (c == 1 && Freq[1])
                return 1;
        if (c == 1 && Freq[2])
                return 2;

        assert(c == 2);
        if (Freq[0] && Freq[1])
                return 0;
        if (Freq[0])
                return 2;
        return 1;
}

int Move(vector < int > Freq)
{
        if (cB == 0)
                return Move2(Freq);

        assert(cA == 2);

        int dg = Freq[0] + Freq[1];
        if (prev != -1) dg ++;
        assert(dg);

        if (dg == 1)
        {
                Found = 1;
                if (prev != -1)
                        return -1;
                prev = Freq[0] ? 0 : 1;
                return prev;
        }

        if (dg > 2)
        {
                Found = 1;
                if (prev != -1 && Freq[prev] == 0)
                        return -1;
                if (prev != 0 && Freq[0] == 1)
                        return prev = 0;
                assert(prev != 1 && Freq[1] == 1);
                return prev = 1;
        }

        if (Found)
                return prev = (Freq[0] ? 0 : 1);

        if (!Cur.size())
        {
                Cur.push_back(Freq[0]);
                Cur.push_back(Freq[1]);
                Cur.push_back(Freq[1] > 0);
                return prev = Freq[1] ? 1 : 0;
        }

        Cur.push_back(Freq[1] == 1);
        if (Cur.size() < 6)
                return prev = Freq[1] == 1;

        assert(Cur.size() == 6);
        bool ff = 0;
        for (auto v : vec)
                ff |= Cur == v;
        if (Cur[2] == 1 && Cur[3] == 1 && Cur[4] == 0 && Cur[5] == 0)
                ff = 1;
        Found = 1;
        if (ff)
                return -1;
        return prev = Freq[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