oj.uz

Submission #549864

# Submission time Handle Problem Language Result Execution time Memory
549864 2022-04-16T17:18:20 Z jesus_coconut Stray Cat (JOI20_stray) C++17
15 / 100
 52 ms 16908 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) {
    cerr << 1 << endl;
    correct = true;
    if (y[prv] == 0) return -1;
    if (y[0] == 1) return prv = 0;
    return prv = 1;
  }
  if (cntadj == 1) {
    cerr << 2 << endl;
    correct = true;
    if (prv != -1) {
        return -1;
    } else {
        if (y[0] == 1) return prv = 0;
        return prv = 1;
    }
  }
  if (correct) {
    cerr << 3 << endl;
    if (y[0] > 0) return prv = 0;
    return  prv = 1;

  }
  if (prv == -1) {
    cerr << 4 << endl;
    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 {
    cerr << 5 << endl;
    if (y[0] > 0) {
        cur.push_back(0);
    } else {
        cur.push_back(1);
    }
    if (cur.size() == 5) {
        for (int i = 0; i < 6; ++i) {
            bool g = true;
            for (int j = 0; j < 5; ++j) {
                if (cur[j] != pat[j]) g = false;
            }
            if (g) {
                correct = true;
                return -1;
            }
            rotate(begin(pat), end(pat), begin(pat) + 1);
        }
        correct = true;
        return prv = cur.back();
    } else {
        return prv = cur.back();
    }
  }
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 15796 KB Output is correct
2 Correct 0 ms 512 KB Output is correct
3 Correct 30 ms 15092 KB Output is correct
4 Correct 49 ms 16908 KB Output is correct
5 Correct 50 ms 16880 KB Output is correct
6 Correct 36 ms 15496 KB Output is correct
7 Correct 37 ms 15472 KB Output is correct
8 Correct 46 ms 16284 KB Output is correct
9 Correct 45 ms 16168 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 15796 KB Output is correct
2 Correct 0 ms 512 KB Output is correct
3 Correct 30 ms 15092 KB Output is correct
4 Correct 49 ms 16908 KB Output is correct
5 Correct 50 ms 16880 KB Output is correct
6 Correct 36 ms 15496 KB Output is correct
7 Correct 37 ms 15472 KB Output is correct
8 Correct 46 ms 16284 KB Output is correct
9 Correct 45 ms 16168 KB Output is correct
10 Correct 36 ms 13548 KB Output is correct
11 Correct 41 ms 13564 KB Output is correct
12 Correct 34 ms 13584 KB Output is correct
13 Correct 36 ms 13616 KB Output is correct
14 Correct 34 ms 13680 KB Output is correct
15 Correct 52 ms 14080 KB Output is correct
16 Correct 47 ms 16452 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 13304 KB Output is correct
2 Correct 0 ms 520 KB Output is correct
3 Correct 28 ms 12960 KB Output is correct
4 Correct 46 ms 14648 KB Output is correct
5 Correct 45 ms 14676 KB Output is correct
6 Correct 35 ms 13424 KB Output is correct
7 Correct 40 ms 13420 KB Output is correct
8 Correct 46 ms 13904 KB Output is correct
9 Correct 42 ms 14004 KB Output is correct
10 Correct 40 ms 13716 KB Output is correct
11 Correct 40 ms 13768 KB Output is correct
12 Correct 39 ms 13684 KB Output is correct
13 Correct 39 ms 13696 KB Output is correct
14 Correct 45 ms 13920 KB Output is correct
15 Correct 49 ms 13956 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 13304 KB Output is correct
2 Correct 0 ms 520 KB Output is correct
3 Correct 28 ms 12960 KB Output is correct
4 Correct 46 ms 14648 KB Output is correct
5 Correct 45 ms 14676 KB Output is correct
6 Correct 35 ms 13424 KB Output is correct
7 Correct 40 ms 13420 KB Output is correct
8 Correct 46 ms 13904 KB Output is correct
9 Correct 42 ms 14004 KB Output is correct
10 Correct 40 ms 13716 KB Output is correct
11 Correct 40 ms 13768 KB Output is correct
12 Correct 39 ms 13684 KB Output is correct
13 Correct 39 ms 13696 KB Output is correct
14 Correct 45 ms 13920 KB Output is correct
15 Correct 49 ms 13956 KB Output is correct
16 Correct 34 ms 11708 KB Output is correct
17 Correct 32 ms 11744 KB Output is correct
18 Correct 31 ms 11740 KB Output is correct
19 Correct 33 ms 11688 KB Output is correct
20 Correct 42 ms 12288 KB Output is correct
21 Correct 39 ms 12040 KB Output is correct
22 Correct 41 ms 14264 KB Output is correct
23 Correct 33 ms 11748 KB Output is correct
24 Correct 31 ms 11756 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 860 KB Output is correct
2 Incorrect 1 ms 512 KB Wrong Answer [4]
3 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

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

Subtask #7
0 / 9.0

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