oj.uz

Submission #251882

# Submission time Handle Problem Language Result Execution time Memory
251882 2020-07-22T17:02:59 Z imeimi2000 Stray Cat (JOI20_stray) C++17
15 / 100
 76 ms 17256 KB 
#include "Anthony.h"
#include <bits/stdc++.h>

using namespace std;

static vector<int> edge[20000];
static int par[20000], pc[20000], ord[20000];
void dfs(int x, int p) {
    par[x] = p;
    ord[x] = -1;
    if (!x) {
        for (int i : edge[x]) dfs(i, x);
    }
    else if (int(edge[x].size()) != 2) {
        for (int i : edge[x]) {
            if (i == p) continue;
            pc[i] = pc[x] ^ 1;
            dfs(i, x);
        }
    }
    else {
        ord[x] = ord[p] != -1 ? (ord[p] + 1) % 6 : (pc[x] ? 2 : 1);
        for (int i : edge[x]) {
            if (i == p) continue;
            pc[i] = "010011"[ord[x]] - '0';
            dfs(i, x);
        }
    }
}

vector<int> Mark(int n, int m, int A, int B, vector<int> U, vector<int> V) {
    for (int i = 0; i < m; ++i) {
        edge[U[i]].push_back(V[i]);
        edge[V[i]].push_back(U[i]);
    }
    if (A > 2) {
        vector<int> dist(n, -1);
        queue<int> q;
        q.push(0);
        dist[0] = 0;
        while (!q.empty()) {
            int x = q.front(); q.pop();
            for (int i : edge[x]) {
                if (dist[i] != -1) continue;
                q.push(i);
                dist[i] = dist[x] + 1;
            }
        }
        vector<int> ret(m);
        for (int i = 0; i < m; ++i) {
            int u = U[i], v = V[i];
            if (dist[u] > dist[v]) swap(u, v);
            ret[i] = dist[u] % 3;
        }
        return ret;
    }
    dfs(0, -1);
    vector<int> ret(m);
    for (int i = 0; i < m; ++i) {
        int u = U[i], v = V[i];
        if (u == par[v]) swap(u, v);
        ret[i] = pc[u];
    }
    return ret;
}
#include "Catherine.h"
#include <bits/stdc++.h>

using namespace std;

static int A, B, pr;
static vector<int> path;

void Init(int a, int b) {
    A = a, B = b;
    pr = -1;
    path.clear();
}

int Move(vector<int> cnt) {
    if (A > 2) {
        int sum = 0;
        for (int i : cnt) sum += i > 0;
        if (sum == 1) {
            for (int i = 0; ; ++i) if (cnt[i]) return i;
        }
        else if (sum == 2) {
            for (int i = 0; ; ++i) if (!cnt[i]) return (i + 1) % 3;
        }
        else exit(1);
    }
    int deg = cnt[0] + cnt[1] + (pr != -1);
    if (deg != 2) path.resize(6);
    if (int(path.size()) > 5) {
        if (deg != 2 && pr != -1) ++cnt[pr];
        for (int i = 0; i < 2; ++i) {
            if (cnt[i] == 1) {
                if (pr != i) return pr = i;
                return -1;
            }
        }
        exit(2);
    }
    while (cnt[0]--) path.push_back(0);
    while (cnt[1]--) path.push_back(1);
    if (int(path.size()) == 5) {
        for (int i = 0; i < 6; ++i) {
            bool dif = 0;
            for (int j = 0; j < 5; ++j) {
                if (path[j] != "010011"[(i + j) % 6] - '0') dif = 1;
            }
            if (!dif) return path.push_back(0), -1;
        }
        path.push_back(path.back());
    }
    return pr = path.back();
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 15972 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 42 ms 15168 KB Output is correct
4 Correct 76 ms 17124 KB Output is correct
5 Correct 58 ms 17256 KB Output is correct
6 Correct 48 ms 15916 KB Output is correct
7 Correct 47 ms 15696 KB Output is correct
8 Correct 57 ms 16468 KB Output is correct
9 Correct 53 ms 16488 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 15972 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 42 ms 15168 KB Output is correct
4 Correct 76 ms 17124 KB Output is correct
5 Correct 58 ms 17256 KB Output is correct
6 Correct 48 ms 15916 KB Output is correct
7 Correct 47 ms 15696 KB Output is correct
8 Correct 57 ms 16468 KB Output is correct
9 Correct 53 ms 16488 KB Output is correct
10 Correct 40 ms 13916 KB Output is correct
11 Correct 46 ms 13920 KB Output is correct
12 Correct 41 ms 13772 KB Output is correct
13 Correct 41 ms 13996 KB Output is correct
14 Correct 43 ms 14260 KB Output is correct
15 Correct 49 ms 14576 KB Output is correct
16 Correct 51 ms 16608 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 13544 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 37 ms 13164 KB Output is correct
4 Correct 54 ms 14960 KB Output is correct
5 Correct 54 ms 14956 KB Output is correct
6 Correct 43 ms 13740 KB Output is correct
7 Correct 43 ms 13768 KB Output is correct
8 Correct 52 ms 14320 KB Output is correct
9 Correct 52 ms 14304 KB Output is correct
10 Correct 47 ms 13908 KB Output is correct
11 Correct 48 ms 14288 KB Output is correct
12 Correct 49 ms 14056 KB Output is correct
13 Correct 48 ms 14056 KB Output is correct
14 Correct 57 ms 14164 KB Output is correct
15 Correct 51 ms 14312 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 13544 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 37 ms 13164 KB Output is correct
4 Correct 54 ms 14960 KB Output is correct
5 Correct 54 ms 14956 KB Output is correct
6 Correct 43 ms 13740 KB Output is correct
7 Correct 43 ms 13768 KB Output is correct
8 Correct 52 ms 14320 KB Output is correct
9 Correct 52 ms 14304 KB Output is correct
10 Correct 47 ms 13908 KB Output is correct
11 Correct 48 ms 14288 KB Output is correct
12 Correct 49 ms 14056 KB Output is correct
13 Correct 48 ms 14056 KB Output is correct
14 Correct 57 ms 14164 KB Output is correct
15 Correct 51 ms 14312 KB Output is correct
16 Correct 40 ms 12012 KB Output is correct
17 Correct 49 ms 12004 KB Output is correct
18 Correct 58 ms 11980 KB Output is correct
19 Correct 43 ms 12084 KB Output is correct
20 Correct 64 ms 12492 KB Output is correct
21 Correct 52 ms 12660 KB Output is correct
22 Correct 56 ms 14444 KB Output is correct
23 Correct 46 ms 12216 KB Output is correct
24 Correct 41 ms 12108 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1688 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 2 ms 1792 KB Output is correct
4 Incorrect 2 ms 1792 KB Wrong Answer [6]
5 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 50 ms 11780 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -