oj.uz

Submission #1040728

# Submission time Handle Problem Language Result Execution time Memory
1040728 2024-08-01T08:46:05 Z 정민찬(#10997) The Ties That Guide Us (CEOI23_incursion) C++17
30 / 100
 224 ms 14244 KB 
#include "incursion.h"
#include <bits/stdc++.h>

using namespace std;

int visit(int w);

int rep[] = {1, 1, 0, 1, 0, 0};
int rt;

void dfs(int x, int p, int pp, int dep, vector<int> &color, vector<vector<int>> &adj) {
    if (x != rt) {
        if (p == rt) {
            color[x] = 1;
        }
        else {
            if (adj[p].size() == 3) {
                color[x] = color[pp] ^ 1;
                dep = -1;
            }
            else {
                if (dep == -1) {
                    for (int i=0; i<6; i++) {
                        if (rep[i] == color[pp] && rep[(i+1)%6] == color[p]) {
                            dep = (i+2) % 6;
                            break;
                        }
                    }
                }
                color[x] = rep[dep];
            }
        }
    }
    for (auto &y : adj[x]) {
        if (y == p) continue;
        dfs(y, x, p, dep == -1 ? -1 : (dep+1)%6, color, adj);
    }
}

vector<int> mark(vector<pair<int, int>> F, int safe) {
    safe --;
    int N = F.size() + 1;
    if (N <= 10) {
        vector<int> color(N, 0);
        color[safe] = 1;
        return color;
    }
    vector<vector<int>> adj(N);
    for (int i=0; i<N-1; i++) {
        adj[F[i].first - 1].push_back(F[i].second - 1);
        adj[F[i].second - 1].push_back(F[i].first - 1);
    }
    vector<int> color(N);
    rt = safe;
    color[safe] = 1;
    dfs(safe, -1, -1, -1, color, adj);
    return color;
}

void dfs2(int x, int p, vector<int> &sz, vector<vector<int>> &adj) {
    sz[x] = 1;
    for (auto &y : adj[x]) {
        if (y == p) continue;
        dfs2(y, x, sz, adj);
        sz[x] += sz[y];
    }
}

bool dfs3(int x, int p, vector<int> &color, vector<vector<int>> &adj) {
    if (color[x] == 1) return true;
    for (auto &y : adj[x]) {
        if (y == p) continue;
        color[y] = visit(y + 1);
        bool ret = dfs3(y, x, color, adj);
        if (ret) return true;
        visit(x + 1);
    }
    return false;
}

void locate(vector<pair<int, int>> F, int curr, int t) {
    curr --;
    int N = F.size() + 1;
    vector<vector<int>> adj(N);
    for (int i=0; i<N-1; i++) {
        adj[F[i].first - 1].push_back(F[i].second - 1);
        adj[F[i].second - 1].push_back(F[i].first - 1);
    }
    if (N <= 10) {
        vector<int> color(N, 0);
        color[curr] = t;
        dfs3(curr, -1, color, adj);
        return;
    }
    vector<int> color(N, -1);
    color[curr] = t;
    if (adj[curr].size() == 1) {
        t = visit(adj[curr][0] + 1);
        curr = adj[curr][0];
        color[curr] = t;
    }
    vector<int> sz(N);
    dfs2(curr, -1, sz, adj);
    int prv;
    assert(adj[curr].size() > 1);
    if (adj[curr].size() == 2) {
        int l = adj[curr][0], r = adj[curr][1];
        if (sz[l] < sz[r]) swap(l, r);
        int lcnt = 1, rcnt = 1;
        int p = curr, x = l;
        vector<int> ls, rs;
        ls.push_back(l);
        while (lcnt < 4) {
            if (adj[x].size() == 2) {
                lcnt ++;
                int temp = p;
                p = x;
                x = adj[x][0] + adj[x][1] - temp;
                ls.push_back(x);
            }
            else break;
        }
        p = curr; x = r;
        rs.push_back(x);
        while (rcnt < 4) {
            if (adj[x].size() == 2) {
                rcnt ++;
                int temp = p;
                p = x;
                x = adj[x][0] + adj[x][1] - temp;
                rs.push_back(x);
            }
            else break;
        }
        assert(ls.size() == lcnt && rs.size() == rcnt);
        /*for (auto &p : ls) {
            printf("%d ", p);
        }
        printf("\n");
        for (auto &p : rs) {
            printf("%d ", p);
        }
        printf("\n");*/
        if (lcnt == 1) {
            int ori = curr;
            color[l] = visit(l + 1);
            assert(adj[l].size() == 3);
            curr = l;
            vector<int> col(3);
            for (int i=0; i<3; i++) {
                int y = adj[curr][i];
                if (color[y] != -1) {
                    col[i] = color[y];
                    continue;
                }
                color[y] = col[i] = visit(y + 1);
                visit(curr + 1);
            }
            int nxt;
            if (col[0] == col[1] && col[1] == col[2]) return;
            if (col[0] != col[1] && col[0] != col[2]) nxt = adj[curr][0];
            else if (col[1] != col[0] && col[1] != col[2]) nxt = adj[curr][1];
            else nxt = adj[curr][2];
            visit(nxt + 1);
            prv = curr;
            curr = nxt;
            assert(nxt != ori);
        }
        else if (rcnt == 1) {
            int ori = curr;
            color[r] = visit(r + 1);
            assert(adj[r].size() == 3);
            curr = r;
            vector<int> col(3);
            for (int i=0; i<3; i++) {
                int y = adj[curr][i];
                if (color[y] != -1) {
                    col[i] = color[y];
                    continue;
                }
                color[y] = col[i] = visit(y + 1);
                visit(curr + 1);
            }
            int nxt;
            if (col[0] == col[1] && col[1] == col[2]) return;
            if (col[0] != col[1] && col[0] != col[2]) nxt = adj[curr][0];
            else if (col[1] != col[0] && col[1] != col[2]) nxt = adj[curr][1];
            else nxt = adj[curr][2];
            visit(nxt + 1);
            prv = curr;
            curr = nxt;
            assert(nxt != ori);
        }
        else {
            assert(lcnt + rcnt >= 4);
            for (int i=0; i<4-lcnt; i++) {
                color[rs[i]] = visit(rs[i] + 1);
            }
            for (int i=2-lcnt; i>=0; i--) {
                visit(rs[i] + 1);
            }
            if (lcnt < 4)
                visit(curr + 1);
            for (int i=0; i<lcnt; i++) {
                color[ls[i]] = visit(ls[i] + 1);
            }
            vector<int> seq, vtx;
            for (int i=lcnt-1; i>=0; i--) {
                seq.push_back(color[ls[i]]);
                vtx.push_back(ls[i]);
            }
            int pos = seq.size();
            seq.push_back(color[curr]);
            vtx.push_back(curr);
            for (int i=0; i<4-lcnt; i++) {
                seq.push_back(color[rs[i]]);
                vtx.push_back(rs[i]);
            }
            /*for (auto &p : seq) {
                printf("%d ", p);
            }
            printf("\n");
            for (auto &p : vtx) {
                printf("%d ", p);
            }
            printf("\n");*/
            int safe = -1;
            if (seq[0] == seq[1] && seq[1] == seq[2]) safe = 1;
            else if (seq[3] == seq[1] && seq[1] == seq[2]) safe = 2;
            else if (seq[2] == seq[3] && seq[3] == seq[4]) safe = 3;
            if (safe != -1) {
                for (int i=1; i<=safe; i++) visit(vtx[i] + 1);
                return;
            }
            bool f1 = false;
            for (int i=0; i<6; i++) {
                bool f2 = true;
                for (int j=0; j<5; j++) {
                    if (seq[j] != rep[(i+j)%6]) {
                        f2 = false;
                        break;
                    }
                }
                if (f2) {
                    f1 = true;
                    break;
                }
            }
            if (!f1) {
                visit(vtx[1] + 1);
                prv = vtx[0];
                curr = vtx[1];
            }
            else {
                prv = vtx[1];
                curr = vtx[0];
            }
        }
    }
    else if (adj[curr].size() == 3) {
        vector<int> col(3);
        for (int i=0; i<3; i++) {
            int y = adj[curr][i];
            if (color[y] != -1) {
                col[i] = color[y];
                continue;
            }
            color[y] = col[i] = visit(y + 1);
            visit(curr + 1);
        }
        int nxt;
        if (col[0] == col[1] && col[1] == col[2]) return;
        if (col[0] != col[1] && col[0] != col[2]) nxt = adj[curr][0];
        else if (col[1] != col[0] && col[1] != col[2]) nxt = adj[curr][1];
        else nxt = adj[curr][2];
        visit(nxt + 1);
        prv = curr;
        curr = nxt;
    }
    while (true) {
        if (adj[curr].size() == 1) return;
        int zero = color[prv] == 0 || color[curr] == 0;
        if (adj[curr].size() == 2) {
            int nxt = adj[curr][0] + adj[curr][1] - prv;
            color[nxt] = visit(nxt + 1);
            if (!zero && color[nxt]) {
                visit(curr + 1);
                return;
            }
            prv = curr;
            curr = nxt;
        }
        else {
            bool flag = false;
            int l = -1, r;
            for (int i=0; i<3; i++) {
                int y = adj[curr][i];
                if (y == prv) continue;
                if (l == -1) l = y;
                else r = y;
            }
            if (sz[l] * 2 < sz[r]) swap(l, r);
            else if (sz[l] <= sz[r] * 2) {
                if (rand() % 2) swap(l, r);
            }
            color[l] = visit(l + 1);
            if (color[l] != color[prv]) {
                prv = curr;
                curr = l;
            }
            else {
                visit(curr + 1);
                color[r] = visit(r + 1);
                if (color[r] != color[prv]) {
                    prv = curr;
                    curr = r;
                }
                else {
                    visit(curr + 1);
                    return;
                }
            }
        }
    }
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from incursion.cpp:2:
incursion.cpp: In function 'void locate(std::vector<std::pair<int, int> >, int, int)':
incursion.cpp:135:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  135 |         assert(ls.size() == lcnt && rs.size() == rcnt);
      |                ~~~~~~~~~~^~~~~~~
incursion.cpp:135:47: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  135 |         assert(ls.size() == lcnt && rs.size() == rcnt);
      |                                     ~~~~~~~~~~^~~~~~~
incursion.cpp:212:17: warning: unused variable 'pos' [-Wunused-variable]
  212 |             int pos = seq.size();
      |                 ^~~
incursion.cpp:294:18: warning: unused variable 'flag' [-Wunused-variable]
  294 |             bool flag = false;
      |                  ^~~~
incursion.cpp:302:33: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
  302 |             if (sz[l] * 2 < sz[r]) swap(l, r);
      |                                 ^
incursion.cpp:298:17: warning: 'prv' may be used uninitialized in this function [-Wmaybe-uninitialized]
  298 |                 if (y == prv) continue;
      |                 ^~
interface.cpp: In function 'int main()':
interface.cpp:44:55: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |     if(fread(T.data(), sizeof(int), 2 * N - 2, stdin) != 2 * N - 2) exit(0);
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
interface.cpp:50:33: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |         int l = (numbers.size() == N ? N : 0);
      |                  ~~~~~~~~~~~~~~~^~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 764 KB Correct

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 12904 KB Correct
2 Correct 183 ms 12968 KB Correct
3 Correct 80 ms 14244 KB Correct
4 Correct 91 ms 12052 KB Correct
5 Correct 158 ms 12376 KB Correct
6 Correct 67 ms 11172 KB Correct
7 Correct 66 ms 11112 KB Correct
8 Correct 174 ms 13148 KB Correct
9 Correct 178 ms 12884 KB Correct
10 Correct 117 ms 12116 KB Correct
11 Correct 91 ms 12828 KB Correct
12 Correct 224 ms 13556 KB Correct
13 Correct 69 ms 10904 KB Correct
14 Correct 71 ms 11088 KB Correct
15 Correct 174 ms 12900 KB Correct
16 Correct 164 ms 12960 KB Correct
17 Correct 111 ms 12976 KB Correct
18 Correct 73 ms 13668 KB Correct
19 Correct 140 ms 13148 KB Correct
20 Correct 69 ms 11024 KB Correct
21 Correct 72 ms 11112 KB Correct
22 Correct 179 ms 13008 KB Correct
23 Correct 172 ms 13152 KB Correct
24 Correct 81 ms 12448 KB Correct
25 Correct 77 ms 14096 KB Correct
26 Correct 66 ms 12648 KB Correct
27 Correct 69 ms 11172 KB Correct
28 Correct 71 ms 11088 KB Correct
29 Correct 143 ms 12888 KB Correct
30 Correct 165 ms 13212 KB Correct
31 Correct 84 ms 11620 KB Correct
32 Correct 193 ms 13092 KB Correct
33 Correct 209 ms 13268 KB Correct
34 Correct 72 ms 11100 KB Correct
35 Correct 69 ms 11028 KB Correct
36 Correct 175 ms 12884 KB Correct
37 Correct 208 ms 13140 KB Correct
38 Correct 219 ms 13492 KB Correct
39 Correct 117 ms 12964 KB Correct
40 Correct 158 ms 12672 KB Correct
41 Correct 70 ms 11112 KB Correct
42 Correct 65 ms 11108 KB Correct
43 Correct 173 ms 12888 KB Correct
44 Correct 183 ms 12888 KB Correct
45 Correct 71 ms 13188 KB Correct
46 Correct 63 ms 13472 KB Correct
47 Correct 86 ms 12528 KB Correct
48 Correct 74 ms 11100 KB Correct
49 Correct 69 ms 11104 KB Correct

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 7456 KB Correct
2 Correct 70 ms 7668 KB Correct
3 Correct 77 ms 7520 KB Correct
4 Correct 79 ms 10324 KB Correct
5 Correct 108 ms 10160 KB Correct
6 Correct 133 ms 10652 KB Correct
7 Correct 63 ms 7260 KB Correct
8 Correct 70 ms 7452 KB Correct
9 Correct 62 ms 7584 KB Correct
10 Incorrect 70 ms 7420 KB Not correct
11 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 764 KB Correct
2 Correct 200 ms 12904 KB Correct
3 Correct 183 ms 12968 KB Correct
4 Correct 80 ms 14244 KB Correct
5 Correct 91 ms 12052 KB Correct
6 Correct 158 ms 12376 KB Correct
7 Correct 67 ms 11172 KB Correct
8 Correct 66 ms 11112 KB Correct
9 Correct 174 ms 13148 KB Correct
10 Correct 178 ms 12884 KB Correct
11 Correct 117 ms 12116 KB Correct
12 Correct 91 ms 12828 KB Correct
13 Correct 224 ms 13556 KB Correct
14 Correct 69 ms 10904 KB Correct
15 Correct 71 ms 11088 KB Correct
16 Correct 174 ms 12900 KB Correct
17 Correct 164 ms 12960 KB Correct
18 Correct 111 ms 12976 KB Correct
19 Correct 73 ms 13668 KB Correct
20 Correct 140 ms 13148 KB Correct
21 Correct 69 ms 11024 KB Correct
22 Correct 72 ms 11112 KB Correct
23 Correct 179 ms 13008 KB Correct
24 Correct 172 ms 13152 KB Correct
25 Correct 81 ms 12448 KB Correct
26 Correct 77 ms 14096 KB Correct
27 Correct 66 ms 12648 KB Correct
28 Correct 69 ms 11172 KB Correct
29 Correct 71 ms 11088 KB Correct
30 Correct 143 ms 12888 KB Correct
31 Correct 165 ms 13212 KB Correct
32 Correct 84 ms 11620 KB Correct
33 Correct 193 ms 13092 KB Correct
34 Correct 209 ms 13268 KB Correct
35 Correct 72 ms 11100 KB Correct
36 Correct 69 ms 11028 KB Correct
37 Correct 175 ms 12884 KB Correct
38 Correct 208 ms 13140 KB Correct
39 Correct 219 ms 13492 KB Correct
40 Correct 117 ms 12964 KB Correct
41 Correct 158 ms 12672 KB Correct
42 Correct 70 ms 11112 KB Correct
43 Correct 65 ms 11108 KB Correct
44 Correct 173 ms 12888 KB Correct
45 Correct 183 ms 12888 KB Correct
46 Correct 71 ms 13188 KB Correct
47 Correct 63 ms 13472 KB Correct
48 Correct 86 ms 12528 KB Correct
49 Correct 74 ms 11100 KB Correct
50 Correct 69 ms 11104 KB Correct
51 Correct 66 ms 7456 KB Correct
52 Correct 70 ms 7668 KB Correct
53 Correct 77 ms 7520 KB Correct
54 Correct 79 ms 10324 KB Correct
55 Correct 108 ms 10160 KB Correct
56 Correct 133 ms 10652 KB Correct
57 Correct 63 ms 7260 KB Correct
58 Correct 70 ms 7452 KB Correct
59 Correct 62 ms 7584 KB Correct
60 Incorrect 70 ms 7420 KB Not correct
61 Halted 0 ms 0 KB -