oj.uz

Submission #1040702

# Submission time Handle Problem Language Result Execution time Memory
1040702 2024-08-01T08:36:12 Z 정민찬(#10997) The Ties That Guide Us (CEOI23_incursion) C++17
30 / 100
 226 ms 14188 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) {
            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;
        }
        else if (rcnt == 1) {
            color[r] = visit(r + 1);
            assert(adj[r].size() == 3);
            assert(0);
            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;
        }
        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);
        }
        if (col[0] == col[1] && col[1] == col[2]) return;
        int nxt;
        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] < sz[r]) 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:209:17: warning: unused variable 'pos' [-Wunused-variable]
  209 |             int pos = seq.size();
      |                 ^~~
incursion.cpp:291:18: warning: unused variable 'flag' [-Wunused-variable]
  291 |             bool flag = false;
      |                  ^~~~
incursion.cpp:299:29: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
  299 |             if (sz[l] < sz[r]) swap(l, r);
      |                             ^
incursion.cpp:295:17: warning: 'prv' may be used uninitialized in this function [-Wmaybe-uninitialized]
  295 |                 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 768 KB Correct

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 12956 KB Correct
2 Correct 174 ms 13156 KB Correct
3 Correct 105 ms 14188 KB Correct
4 Correct 86 ms 12052 KB Correct
5 Correct 171 ms 12700 KB Correct
6 Correct 78 ms 10916 KB Correct
7 Correct 66 ms 10908 KB Correct
8 Correct 179 ms 12880 KB Correct
9 Correct 149 ms 12900 KB Correct
10 Correct 128 ms 11876 KB Correct
11 Correct 79 ms 12996 KB Correct
12 Correct 217 ms 13552 KB Correct
13 Correct 66 ms 11164 KB Correct
14 Correct 66 ms 11100 KB Correct
15 Correct 182 ms 12960 KB Correct
16 Correct 172 ms 13140 KB Correct
17 Correct 112 ms 12576 KB Correct
18 Correct 79 ms 13404 KB Correct
19 Correct 133 ms 13172 KB Correct
20 Correct 70 ms 11184 KB Correct
21 Correct 66 ms 11164 KB Correct
22 Correct 187 ms 12892 KB Correct
23 Correct 176 ms 12892 KB Correct
24 Correct 82 ms 12380 KB Correct
25 Correct 77 ms 14184 KB Correct
26 Correct 74 ms 12812 KB Correct
27 Correct 71 ms 11116 KB Correct
28 Correct 71 ms 10844 KB Correct
29 Correct 153 ms 12956 KB Correct
30 Correct 178 ms 12900 KB Correct
31 Correct 69 ms 11512 KB Correct
32 Correct 210 ms 13096 KB Correct
33 Correct 204 ms 13192 KB Correct
34 Correct 65 ms 10920 KB Correct
35 Correct 65 ms 10844 KB Correct
36 Correct 181 ms 12968 KB Correct
37 Correct 188 ms 12968 KB Correct
38 Correct 226 ms 13736 KB Correct
39 Correct 119 ms 13392 KB Correct
40 Correct 154 ms 12488 KB Correct
41 Correct 81 ms 11092 KB Correct
42 Correct 63 ms 11100 KB Correct
43 Correct 170 ms 12948 KB Correct
44 Correct 184 ms 12956 KB Correct
45 Correct 69 ms 13240 KB Correct
46 Correct 74 ms 13136 KB Correct
47 Correct 81 ms 12444 KB Correct
48 Correct 70 ms 11044 KB Correct
49 Correct 67 ms 11048 KB Correct

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 7592 KB Correct
2 Correct 71 ms 7472 KB Correct
3 Correct 66 ms 7580 KB Correct
4 Correct 67 ms 10380 KB Correct
5 Correct 113 ms 10152 KB Correct
6 Correct 136 ms 10484 KB Correct
7 Correct 65 ms 7412 KB Correct
8 Correct 67 ms 7508 KB Correct
9 Correct 64 ms 7600 KB Correct
10 Incorrect 68 ms 7364 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 768 KB Correct
2 Correct 142 ms 12956 KB Correct
3 Correct 174 ms 13156 KB Correct
4 Correct 105 ms 14188 KB Correct
5 Correct 86 ms 12052 KB Correct
6 Correct 171 ms 12700 KB Correct
7 Correct 78 ms 10916 KB Correct
8 Correct 66 ms 10908 KB Correct
9 Correct 179 ms 12880 KB Correct
10 Correct 149 ms 12900 KB Correct
11 Correct 128 ms 11876 KB Correct
12 Correct 79 ms 12996 KB Correct
13 Correct 217 ms 13552 KB Correct
14 Correct 66 ms 11164 KB Correct
15 Correct 66 ms 11100 KB Correct
16 Correct 182 ms 12960 KB Correct
17 Correct 172 ms 13140 KB Correct
18 Correct 112 ms 12576 KB Correct
19 Correct 79 ms 13404 KB Correct
20 Correct 133 ms 13172 KB Correct
21 Correct 70 ms 11184 KB Correct
22 Correct 66 ms 11164 KB Correct
23 Correct 187 ms 12892 KB Correct
24 Correct 176 ms 12892 KB Correct
25 Correct 82 ms 12380 KB Correct
26 Correct 77 ms 14184 KB Correct
27 Correct 74 ms 12812 KB Correct
28 Correct 71 ms 11116 KB Correct
29 Correct 71 ms 10844 KB Correct
30 Correct 153 ms 12956 KB Correct
31 Correct 178 ms 12900 KB Correct
32 Correct 69 ms 11512 KB Correct
33 Correct 210 ms 13096 KB Correct
34 Correct 204 ms 13192 KB Correct
35 Correct 65 ms 10920 KB Correct
36 Correct 65 ms 10844 KB Correct
37 Correct 181 ms 12968 KB Correct
38 Correct 188 ms 12968 KB Correct
39 Correct 226 ms 13736 KB Correct
40 Correct 119 ms 13392 KB Correct
41 Correct 154 ms 12488 KB Correct
42 Correct 81 ms 11092 KB Correct
43 Correct 63 ms 11100 KB Correct
44 Correct 170 ms 12948 KB Correct
45 Correct 184 ms 12956 KB Correct
46 Correct 69 ms 13240 KB Correct
47 Correct 74 ms 13136 KB Correct
48 Correct 81 ms 12444 KB Correct
49 Correct 70 ms 11044 KB Correct
50 Correct 67 ms 11048 KB Correct
51 Correct 65 ms 7592 KB Correct
52 Correct 71 ms 7472 KB Correct
53 Correct 66 ms 7580 KB Correct
54 Correct 67 ms 10380 KB Correct
55 Correct 113 ms 10152 KB Correct
56 Correct 136 ms 10484 KB Correct
57 Correct 65 ms 7412 KB Correct
58 Correct 67 ms 7508 KB Correct
59 Correct 64 ms 7600 KB Correct
60 Incorrect 68 ms 7364 KB Not correct
61 Halted 0 ms 0 KB -