oj.uz

Submission #549878

# Submission time Handle Problem Language Result Execution time Memory
549878 2022-04-16T17:52:21 Z jesus_coconut Stray Cat (JOI20_stray) C++17
15 / 100
 48 ms 16488 KB 
#include "Anthony.h"
#include <bits/stdc++.h>

using namespace std;


namespace {
vector<vector<int>> adj;
vector<int> dist;
void bfs() {
    queue<int> q;
    dist.resize(adj.size(), INT_MAX);
    q.push(0);
    dist[0] = 0;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (auto u : adj[v]) {
            if (dist[u] > dist[v] + 1) {
                dist[u] = dist[v] + 1;
                q.push(u);
            }
        }
    }
}

vector<int> s{0, 0, 1, 0, 1, 1};

vector<pair<int, int>> v;
void dfs(int ver, int par, int col, int len) {
    v[ver] = {par, col};
    int numchild = adj[ver].size() - (par != -1);
    if (numchild > 1) {
        for (auto c : adj[ver]) if (c != par) {
            dfs(c, ver, !col, -1);
        }
    } else {
        if (len == -1) {
            if (col == 0) len = 1;
            else len = 3;
        }
        for (auto c : adj[ver]) if (c != par) {
            dfs(c, ver, s[len], (len + 1) % 6);
        }
    }

}
}  // namespace

std::vector<int> Mark(int N, int M, int A, int B,
                      std::vector<int> U, std::vector<int> V) {
    adj.resize(N);
    for (int i = 0; i < M; ++i) {
        adj[U[i]].push_back(V[i]);
        adj[V[i]].push_back(U[i]);
    }
  if (A >= 3) {
        bfs();
        vector<int> ret(M);
        for (int i = 0; i < M; ++i) {
            ret[i] = min(dist[U[i]], dist[V[i]]) % 3;
        }
        return ret;
  }
  v.resize(N);
  dfs(0, -1, 0, -1);
  vector<int> ret(M);
  for (int i = 0; i < M; ++i) {
    if (v[U[i]].first == V[i]) {
        ret[i] = v[U[i]].second;
    } else {
        ret[i] = v[V[i]].second;
    }
  }
  return ret;
}

#include "Catherine.h"
#include <bits/stdc++.h>

using namespace std;

namespace {

int A, B;
int prv;
vector<int> pat{0, 0, 1, 0, 1, 1};
vector<int> cur;
bool correct;
}  // namespace

void Init(int A, int B) {
  ::A = A;
  ::B = B;
  ::prv = -1;
  ::correct = false;
}

int Move(std::vector<int> y) {
  if (A >= 3) {
    if (y[0] == 0) {
        if (y[1] == 0) return 2;
        return 1;
    } else if (y[1] == 0) {
        if (y[2] == 0) return 0;
        return 2;
    } else if (y[2] == 0) {
        if (y[0] == 0) return 1;
        return 0;
    }
    assert(false);
  }
  int cntadj = accumulate(begin(y), end(y), 0) + (prv != -1);
  if (cntadj > 2) {
    correct = true;
    if (prv != -1 && y[prv] == 0) return -1;
    if (y[0] == 1) return prv = 0;
    else if (y[1] == 1) return prv = 1;
    assert(false);
  }
  if (cntadj == 1) {
    correct = true;
    if (prv != -1) {
        return -1;
    } else {
        if (y[0] == 1) return prv = 0;
        else if (y[1] == 1) return prv = 1;
        assert(false);
    }
  }
  if (correct) {
    if (y[0] > 0) return prv = 0;
    else if (y[1] > 0) return  prv = 1;
    assert(false);
  }
  if (prv == -1) {
    if (y[0] > 0) {
        cur.push_back(0);
        if (y[1] > 0) {
            cur.push_back(1);
            return prv = 1;
        } else {
            cur.push_back(0);
            return prv = 0;
        }
    } else {
        assert(y[1] > 0);
        cur.push_back(1);
        cur.push_back(1);
        return prv = 1;
    }
  } else {
    if (y[0] > 0) {
        cur.push_back(0);
    } else {
        assert(y[1] > 0);
        cur.push_back(1);
    }
    if (cur.size() == 5) {
        for (int i = 0; i < 10; ++i) {
            bool g = true;
            for (int j = 0; j < 5; ++j) {
                if (cur[j] != pat[(j + i) % size(pat)]) g = false;
            }
            if (g) {
                correct = true;
                return -1;
            }
        }
        reverse(begin(cur), end(cur));
        bool tmp = false;
        for (int i = 0; i < 10; ++i) {
            bool g = true;
            for (int j = 0; j < 5; ++j) {
                if (cur[j] != pat[(j + i) % size(pat)]) g = false;
            }
            if (g) {
                tmp = true;
            }
        }
        assert(tmp);
        correct = true;
        assert(y[cur.back()] > 0);
        return prv = cur.back();
    } else {
        assert(y[cur.back()] > 0);
        return prv = cur.back();
    }
  }
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 15308 KB Output is correct
2 Correct 0 ms 508 KB Output is correct
3 Correct 28 ms 14612 KB Output is correct
4 Correct 43 ms 16372 KB Output is correct
5 Correct 46 ms 16488 KB Output is correct
6 Correct 35 ms 15072 KB Output is correct
7 Correct 35 ms 15124 KB Output is correct
8 Correct 40 ms 15764 KB Output is correct
9 Correct 40 ms 15852 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 15308 KB Output is correct
2 Correct 0 ms 508 KB Output is correct
3 Correct 28 ms 14612 KB Output is correct
4 Correct 43 ms 16372 KB Output is correct
5 Correct 46 ms 16488 KB Output is correct
6 Correct 35 ms 15072 KB Output is correct
7 Correct 35 ms 15124 KB Output is correct
8 Correct 40 ms 15764 KB Output is correct
9 Correct 40 ms 15852 KB Output is correct
10 Correct 32 ms 13076 KB Output is correct
11 Correct 31 ms 13072 KB Output is correct
12 Correct 31 ms 13164 KB Output is correct
13 Correct 33 ms 13076 KB Output is correct
14 Correct 41 ms 13300 KB Output is correct
15 Correct 37 ms 13728 KB Output is correct
16 Correct 48 ms 15908 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 12820 KB Output is correct
2 Correct 0 ms 508 KB Output is correct
3 Correct 30 ms 12512 KB Output is correct
4 Correct 44 ms 14220 KB Output is correct
5 Correct 40 ms 14232 KB Output is correct
6 Correct 33 ms 12908 KB Output is correct
7 Correct 32 ms 12948 KB Output is correct
8 Correct 39 ms 13496 KB Output is correct
9 Correct 39 ms 13496 KB Output is correct
10 Correct 37 ms 13456 KB Output is correct
11 Correct 37 ms 13240 KB Output is correct
12 Correct 37 ms 13204 KB Output is correct
13 Correct 37 ms 13212 KB Output is correct
14 Correct 41 ms 13464 KB Output is correct
15 Correct 39 ms 13576 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 12820 KB Output is correct
2 Correct 0 ms 508 KB Output is correct
3 Correct 30 ms 12512 KB Output is correct
4 Correct 44 ms 14220 KB Output is correct
5 Correct 40 ms 14232 KB Output is correct
6 Correct 33 ms 12908 KB Output is correct
7 Correct 32 ms 12948 KB Output is correct
8 Correct 39 ms 13496 KB Output is correct
9 Correct 39 ms 13496 KB Output is correct
10 Correct 37 ms 13456 KB Output is correct
11 Correct 37 ms 13240 KB Output is correct
12 Correct 37 ms 13204 KB Output is correct
13 Correct 37 ms 13212 KB Output is correct
14 Correct 41 ms 13464 KB Output is correct
15 Correct 39 ms 13576 KB Output is correct
16 Correct 38 ms 11408 KB Output is correct
17 Correct 28 ms 11312 KB Output is correct
18 Correct 31 ms 11248 KB Output is correct
19 Correct 32 ms 11180 KB Output is correct
20 Correct 36 ms 11840 KB Output is correct
21 Correct 33 ms 11640 KB Output is correct
22 Correct 38 ms 13840 KB Output is correct
23 Correct 33 ms 11336 KB Output is correct
24 Correct 33 ms 11280 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 820 KB Output is correct
2 Correct 0 ms 516 KB Output is correct
3 Correct 2 ms 896 KB Output is correct
4 Correct 2 ms 896 KB Output is correct
5 Correct 2 ms 908 KB Output is correct
6 Correct 2 ms 904 KB Output is correct
7 Runtime error 2 ms 1280 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

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

Subtask #7
0 / 9.0

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