oj.uz

Submission #260723

# Submission time Handle Problem Language Result Execution time Memory
260723 2020-08-10T19:21:33 Z Kastanda Stray Cat (JOI20_stray) C++14
15 / 100
 73 ms 18048 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 (togo == prev)
                  	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];
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 16820 KB Output is correct
2 Correct 1 ms 2816 KB Output is correct
3 Correct 40 ms 15916 KB Output is correct
4 Correct 72 ms 18048 KB Output is correct
5 Correct 67 ms 17864 KB Output is correct
6 Correct 52 ms 16564 KB Output is correct
7 Correct 50 ms 16552 KB Output is correct
8 Correct 60 ms 17216 KB Output is correct
9 Correct 67 ms 17332 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 16820 KB Output is correct
2 Correct 1 ms 2816 KB Output is correct
3 Correct 40 ms 15916 KB Output is correct
4 Correct 72 ms 18048 KB Output is correct
5 Correct 67 ms 17864 KB Output is correct
6 Correct 52 ms 16564 KB Output is correct
7 Correct 50 ms 16552 KB Output is correct
8 Correct 60 ms 17216 KB Output is correct
9 Correct 67 ms 17332 KB Output is correct
10 Correct 47 ms 14396 KB Output is correct
11 Correct 44 ms 14692 KB Output is correct
12 Correct 45 ms 14708 KB Output is correct
13 Correct 46 ms 14580 KB Output is correct
14 Correct 47 ms 14868 KB Output is correct
15 Correct 53 ms 15244 KB Output is correct
16 Correct 57 ms 17352 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 14280 KB Output is correct
2 Correct 1 ms 2816 KB Output is correct
3 Correct 40 ms 13872 KB Output is correct
4 Correct 73 ms 15796 KB Output is correct
5 Correct 63 ms 15816 KB Output is correct
6 Correct 49 ms 14128 KB Output is correct
7 Correct 48 ms 14368 KB Output is correct
8 Correct 67 ms 14912 KB Output is correct
9 Correct 62 ms 15140 KB Output is correct
10 Correct 58 ms 14928 KB Output is correct
11 Correct 57 ms 14664 KB Output is correct
12 Correct 55 ms 14664 KB Output is correct
13 Correct 55 ms 14808 KB Output is correct
14 Correct 59 ms 15148 KB Output is correct
15 Correct 56 ms 15044 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 14280 KB Output is correct
2 Correct 1 ms 2816 KB Output is correct
3 Correct 40 ms 13872 KB Output is correct
4 Correct 73 ms 15796 KB Output is correct
5 Correct 63 ms 15816 KB Output is correct
6 Correct 49 ms 14128 KB Output is correct
7 Correct 48 ms 14368 KB Output is correct
8 Correct 67 ms 14912 KB Output is correct
9 Correct 62 ms 15140 KB Output is correct
10 Correct 58 ms 14928 KB Output is correct
11 Correct 57 ms 14664 KB Output is correct
12 Correct 55 ms 14664 KB Output is correct
13 Correct 55 ms 14808 KB Output is correct
14 Correct 59 ms 15148 KB Output is correct
15 Correct 56 ms 15044 KB Output is correct
16 Correct 41 ms 12748 KB Output is correct
17 Correct 41 ms 12828 KB Output is correct
18 Correct 44 ms 12684 KB Output is correct
19 Correct 43 ms 12640 KB Output is correct
20 Correct 53 ms 13192 KB Output is correct
21 Correct 47 ms 13084 KB Output is correct
22 Correct 56 ms 15300 KB Output is correct
23 Correct 44 ms 12600 KB Output is correct
24 Correct 44 ms 12808 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 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 40 ms 11988 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

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