oj.uz

Submission #549881

# Submission time Handle Problem Language Result Execution time Memory
549881 2022-04-16T18:01:07 Z jesus_coconut Stray Cat (JOI20_stray) C++17
15 / 100
 60 ms 19744 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;
    y[prv]++;
    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;
            }
        }

        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 36 ms 15212 KB Output is correct
2 Correct 0 ms 516 KB Output is correct
3 Correct 32 ms 14640 KB Output is correct
4 Correct 50 ms 16608 KB Output is correct
5 Correct 53 ms 16368 KB Output is correct
6 Correct 40 ms 15212 KB Output is correct
7 Correct 39 ms 15152 KB Output is correct
8 Correct 41 ms 15764 KB Output is correct
9 Correct 44 ms 15908 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 15212 KB Output is correct
2 Correct 0 ms 516 KB Output is correct
3 Correct 32 ms 14640 KB Output is correct
4 Correct 50 ms 16608 KB Output is correct
5 Correct 53 ms 16368 KB Output is correct
6 Correct 40 ms 15212 KB Output is correct
7 Correct 39 ms 15152 KB Output is correct
8 Correct 41 ms 15764 KB Output is correct
9 Correct 44 ms 15908 KB Output is correct
10 Correct 36 ms 13092 KB Output is correct
11 Correct 36 ms 13032 KB Output is correct
12 Correct 32 ms 13136 KB Output is correct
13 Correct 32 ms 13152 KB Output is correct
14 Correct 34 ms 13464 KB Output is correct
15 Correct 41 ms 13764 KB Output is correct
16 Correct 40 ms 15884 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 12956 KB Output is correct
2 Correct 0 ms 508 KB Output is correct
3 Correct 30 ms 12572 KB Output is correct
4 Correct 46 ms 14268 KB Output is correct
5 Correct 48 ms 14272 KB Output is correct
6 Correct 34 ms 13004 KB Output is correct
7 Correct 40 ms 12840 KB Output is correct
8 Correct 60 ms 13524 KB Output is correct
9 Correct 39 ms 13576 KB Output is correct
10 Correct 37 ms 13236 KB Output is correct
11 Correct 37 ms 13348 KB Output is correct
12 Correct 40 ms 13444 KB Output is correct
13 Correct 41 ms 13236 KB Output is correct
14 Correct 45 ms 13512 KB Output is correct
15 Correct 41 ms 13524 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 12956 KB Output is correct
2 Correct 0 ms 508 KB Output is correct
3 Correct 30 ms 12572 KB Output is correct
4 Correct 46 ms 14268 KB Output is correct
5 Correct 48 ms 14272 KB Output is correct
6 Correct 34 ms 13004 KB Output is correct
7 Correct 40 ms 12840 KB Output is correct
8 Correct 60 ms 13524 KB Output is correct
9 Correct 39 ms 13576 KB Output is correct
10 Correct 37 ms 13236 KB Output is correct
11 Correct 37 ms 13348 KB Output is correct
12 Correct 40 ms 13444 KB Output is correct
13 Correct 41 ms 13236 KB Output is correct
14 Correct 45 ms 13512 KB Output is correct
15 Correct 41 ms 13524 KB Output is correct
16 Correct 31 ms 11384 KB Output is correct
17 Correct 28 ms 11264 KB Output is correct
18 Correct 33 ms 11360 KB Output is correct
19 Correct 30 ms 11228 KB Output is correct
20 Correct 37 ms 11884 KB Output is correct
21 Correct 36 ms 11620 KB Output is correct
22 Correct 43 ms 13764 KB Output is correct
23 Correct 38 ms 11312 KB Output is correct
24 Correct 32 ms 11424 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 900 KB Output is correct
2 Runtime error 1 ms 772 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 11176 KB Output is correct
2 Correct 38 ms 12720 KB Output is correct
3 Correct 0 ms 520 KB Output is correct
4 Runtime error 32 ms 19740 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 11056 KB Output is correct
2 Correct 35 ms 12596 KB Output is correct
3 Correct 1 ms 516 KB Output is correct
4 Runtime error 32 ms 19744 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -