oj.uz

Submission #260727

# Submission time Handle Problem Language Result Execution time Memory
260727 2020-08-10T19:27:28 Z Kastanda Stray Cat (JOI20_stray) C++14
15 / 100
 71 ms 17464 KB 
// 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;

}
// 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;
                int togo = ((Freq[1] + (prev == 1)) == 1);
                if (prev == togo)
                        return -1;
                return prev = togo;
        }

        if (Found)
                return prev = (Freq[1] == 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] == 1);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 16508 KB Output is correct
2 Correct 1 ms 2816 KB Output is correct
3 Correct 40 ms 15632 KB Output is correct
4 Correct 62 ms 17460 KB Output is correct
5 Correct 63 ms 17464 KB Output is correct
6 Correct 49 ms 15996 KB Output is correct
7 Correct 48 ms 16024 KB Output is correct
8 Correct 57 ms 16756 KB Output is correct
9 Correct 58 ms 16812 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 16508 KB Output is correct
2 Correct 1 ms 2816 KB Output is correct
3 Correct 40 ms 15632 KB Output is correct
4 Correct 62 ms 17460 KB Output is correct
5 Correct 63 ms 17464 KB Output is correct
6 Correct 49 ms 15996 KB Output is correct
7 Correct 48 ms 16024 KB Output is correct
8 Correct 57 ms 16756 KB Output is correct
9 Correct 58 ms 16812 KB Output is correct
10 Correct 45 ms 14072 KB Output is correct
11 Correct 45 ms 14304 KB Output is correct
12 Correct 47 ms 14112 KB Output is correct
13 Correct 44 ms 14324 KB Output is correct
14 Correct 47 ms 14476 KB Output is correct
15 Correct 55 ms 14576 KB Output is correct
16 Correct 59 ms 16956 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 13880 KB Output is correct
2 Correct 1 ms 2816 KB Output is correct
3 Correct 40 ms 13308 KB Output is correct
4 Correct 71 ms 15412 KB Output is correct
5 Correct 64 ms 15220 KB Output is correct
6 Correct 49 ms 13820 KB Output is correct
7 Correct 48 ms 13868 KB Output is correct
8 Correct 61 ms 14460 KB Output is correct
9 Correct 58 ms 14644 KB Output is correct
10 Correct 50 ms 14392 KB Output is correct
11 Correct 51 ms 14388 KB Output is correct
12 Correct 50 ms 14392 KB Output is correct
13 Correct 50 ms 14388 KB Output is correct
14 Correct 70 ms 14448 KB Output is correct
15 Correct 71 ms 14460 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 13880 KB Output is correct
2 Correct 1 ms 2816 KB Output is correct
3 Correct 40 ms 13308 KB Output is correct
4 Correct 71 ms 15412 KB Output is correct
5 Correct 64 ms 15220 KB Output is correct
6 Correct 49 ms 13820 KB Output is correct
7 Correct 48 ms 13868 KB Output is correct
8 Correct 61 ms 14460 KB Output is correct
9 Correct 58 ms 14644 KB Output is correct
10 Correct 50 ms 14392 KB Output is correct
11 Correct 51 ms 14388 KB Output is correct
12 Correct 50 ms 14392 KB Output is correct
13 Correct 50 ms 14388 KB Output is correct
14 Correct 70 ms 14448 KB Output is correct
15 Correct 71 ms 14460 KB Output is correct
16 Correct 44 ms 12152 KB Output is correct
17 Correct 41 ms 12168 KB Output is correct
18 Correct 44 ms 12544 KB Output is correct
19 Correct 46 ms 12160 KB Output is correct
20 Correct 53 ms 12824 KB Output is correct
21 Correct 46 ms 12556 KB Output is correct
22 Correct 57 ms 14776 KB Output is correct
23 Correct 45 ms 12280 KB Output is correct
24 Correct 48 ms 12548 KB Output is correct

Subtask #5
0 / 5.0

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

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 11600 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 55 ms 11580 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -