oj.uz

답안 #549872

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
549872 2022-04-16T17:40:48 Z jesus_coconut 길고양이 (JOI20_stray) C++17
15 / 100
 68 ms 16500 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 {
        cur.push_back(1);
        if (y[0] > 0) {
            cur.push_back(0);
            return prv = 0;
        } else {
            cur.push_back(1);
            return prv = 1;
        }
    }
  } else {
    if (y[0] > 0) {
        cur.push_back(0);
    } else {
        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;
        return prv = cur.back();
    } else {
        return prv = cur.back();
    }
  }
}

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 15252 KB Output is correct
2 Correct 0 ms 516 KB Output is correct
3 Correct 33 ms 14680 KB Output is correct
4 Correct 51 ms 16500 KB Output is correct
5 Correct 47 ms 16340 KB Output is correct
6 Correct 40 ms 15168 KB Output is correct
7 Correct 37 ms 15264 KB Output is correct
8 Correct 68 ms 15768 KB Output is correct
9 Correct 43 ms 15952 KB Output is correct

Subtask #2
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 15252 KB Output is correct
2 Correct 0 ms 516 KB Output is correct
3 Correct 33 ms 14680 KB Output is correct
4 Correct 51 ms 16500 KB Output is correct
5 Correct 47 ms 16340 KB Output is correct
6 Correct 40 ms 15168 KB Output is correct
7 Correct 37 ms 15264 KB Output is correct
8 Correct 68 ms 15768 KB Output is correct
9 Correct 43 ms 15952 KB Output is correct
10 Correct 39 ms 13148 KB Output is correct
11 Correct 34 ms 13176 KB Output is correct
12 Correct 36 ms 13076 KB Output is correct
13 Correct 35 ms 13092 KB Output is correct
14 Correct 39 ms 13356 KB Output is correct
15 Correct 41 ms 13744 KB Output is correct
16 Correct 47 ms 15936 KB Output is correct

Subtask #3
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 12820 KB Output is correct
2 Correct 0 ms 508 KB Output is correct
3 Correct 37 ms 12428 KB Output is correct
4 Correct 41 ms 14228 KB Output is correct
5 Correct 40 ms 14268 KB Output is correct
6 Correct 31 ms 13044 KB Output is correct
7 Correct 33 ms 12908 KB Output is correct
8 Correct 39 ms 13592 KB Output is correct
9 Correct 40 ms 13520 KB Output is correct
10 Correct 41 ms 13296 KB Output is correct
11 Correct 39 ms 13316 KB Output is correct
12 Correct 35 ms 13308 KB Output is correct
13 Correct 36 ms 13376 KB Output is correct
14 Correct 40 ms 13656 KB Output is correct
15 Correct 37 ms 13680 KB Output is correct

Subtask #4
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 12820 KB Output is correct
2 Correct 0 ms 508 KB Output is correct
3 Correct 37 ms 12428 KB Output is correct
4 Correct 41 ms 14228 KB Output is correct
5 Correct 40 ms 14268 KB Output is correct
6 Correct 31 ms 13044 KB Output is correct
7 Correct 33 ms 12908 KB Output is correct
8 Correct 39 ms 13592 KB Output is correct
9 Correct 40 ms 13520 KB Output is correct
10 Correct 41 ms 13296 KB Output is correct
11 Correct 39 ms 13316 KB Output is correct
12 Correct 35 ms 13308 KB Output is correct
13 Correct 36 ms 13376 KB Output is correct
14 Correct 40 ms 13656 KB Output is correct
15 Correct 37 ms 13680 KB Output is correct
16 Correct 34 ms 11412 KB Output is correct
17 Correct 32 ms 11392 KB Output is correct
18 Correct 30 ms 11248 KB Output is correct
19 Correct 30 ms 11260 KB Output is correct
20 Correct 37 ms 11900 KB Output is correct
21 Correct 34 ms 11612 KB Output is correct
22 Correct 41 ms 13760 KB Output is correct
23 Correct 35 ms 11300 KB Output is correct
24 Correct 31 ms 11288 KB Output is correct

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 896 KB Output is correct
2 Correct 0 ms 508 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 904 KB Output is correct
6 Correct 2 ms 904 KB Output is correct
7 Incorrect 2 ms 896 KB Wrong Answer [5]
8 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 34 ms 11060 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 28 ms 11128 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -