oj.uz

Submission #1040744

# Submission time Handle Problem Language Result Execution time Memory
1040744 2024-08-01T08:53:22 Z 정민찬(#10997) The Ties That Guide Us (CEOI23_incursion) C++17
30 / 100
 261 ms 14176 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);
    bool totf = false;
    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) {
            totf = true;
            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] && color[curr] == col[0]) 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);
            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] && color[curr] == col[0]) 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);
        }
        int nxt;
        if (col[0] == col[1] && col[1] == col[2] && color[curr] == col[0]) 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) {
            if (totf) assert(0);
            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);
                if (totf) assert(0);
                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);
                    if (totf) assert(0);
                    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:136:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  136 |         assert(ls.size() == lcnt && rs.size() == rcnt);
      |                ~~~~~~~~~~^~~~~~~
incursion.cpp:136:47: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  136 |         assert(ls.size() == lcnt && rs.size() == rcnt);
      |                                     ~~~~~~~~~~^~~~~~~
incursion.cpp:210:17: warning: unused variable 'pos' [-Wunused-variable]
  210 |             int pos = seq.size();
      |                 ^~~
incursion.cpp:296:18: warning: unused variable 'flag' [-Wunused-variable]
  296 |             bool flag = false;
      |                  ^~~~
incursion.cpp:304:33: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
  304 |             if (sz[l] * 2 < sz[r]) swap(l, r);
      |                                 ^
incursion.cpp:300:17: warning: 'prv' may be used uninitialized in this function [-Wmaybe-uninitialized]
  300 |                 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 776 KB Correct

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 12640 KB Correct
2 Correct 177 ms 12964 KB Correct
3 Correct 99 ms 14168 KB Correct
4 Correct 88 ms 12256 KB Correct
5 Correct 167 ms 12904 KB Correct
6 Correct 68 ms 10920 KB Correct
7 Correct 66 ms 11092 KB Correct
8 Correct 175 ms 13128 KB Correct
9 Correct 179 ms 12908 KB Correct
10 Correct 141 ms 12132 KB Correct
11 Correct 84 ms 13012 KB Correct
12 Correct 243 ms 13624 KB Correct
13 Correct 71 ms 11172 KB Correct
14 Correct 71 ms 10852 KB Correct
15 Correct 155 ms 12872 KB Correct
16 Correct 179 ms 12968 KB Correct
17 Correct 106 ms 12468 KB Correct
18 Correct 82 ms 13472 KB Correct
19 Correct 139 ms 13304 KB Correct
20 Correct 71 ms 11152 KB Correct
21 Correct 66 ms 11104 KB Correct
22 Correct 182 ms 12960 KB Correct
23 Correct 179 ms 12960 KB Correct
24 Correct 82 ms 12484 KB Correct
25 Correct 79 ms 14176 KB Correct
26 Correct 70 ms 12576 KB Correct
27 Correct 65 ms 11168 KB Correct
28 Correct 76 ms 11016 KB Correct
29 Correct 192 ms 12944 KB Correct
30 Correct 207 ms 12856 KB Correct
31 Correct 82 ms 11860 KB Correct
32 Correct 200 ms 13084 KB Correct
33 Correct 204 ms 13200 KB Correct
34 Correct 62 ms 11004 KB Correct
35 Correct 73 ms 11024 KB Correct
36 Correct 183 ms 12956 KB Correct
37 Correct 159 ms 12876 KB Correct
38 Correct 261 ms 13432 KB Correct
39 Correct 133 ms 13220 KB Correct
40 Correct 184 ms 12600 KB Correct
41 Correct 79 ms 11136 KB Correct
42 Correct 74 ms 11088 KB Correct
43 Correct 190 ms 12960 KB Correct
44 Correct 181 ms 12772 KB Correct
45 Correct 80 ms 13136 KB Correct
46 Correct 82 ms 13468 KB Correct
47 Correct 71 ms 12368 KB Correct
48 Correct 74 ms 11104 KB Correct
49 Correct 74 ms 10828 KB Correct

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 7648 KB Correct
2 Correct 77 ms 7584 KB Correct
3 Correct 75 ms 7756 KB Correct
4 Correct 79 ms 10348 KB Correct
5 Correct 116 ms 10088 KB Correct
6 Correct 146 ms 10488 KB Correct
7 Correct 65 ms 7424 KB Correct
8 Correct 75 ms 7504 KB Correct
9 Correct 63 ms 7336 KB Correct
10 Incorrect 67 ms 7508 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 776 KB Correct
2 Correct 167 ms 12640 KB Correct
3 Correct 177 ms 12964 KB Correct
4 Correct 99 ms 14168 KB Correct
5 Correct 88 ms 12256 KB Correct
6 Correct 167 ms 12904 KB Correct
7 Correct 68 ms 10920 KB Correct
8 Correct 66 ms 11092 KB Correct
9 Correct 175 ms 13128 KB Correct
10 Correct 179 ms 12908 KB Correct
11 Correct 141 ms 12132 KB Correct
12 Correct 84 ms 13012 KB Correct
13 Correct 243 ms 13624 KB Correct
14 Correct 71 ms 11172 KB Correct
15 Correct 71 ms 10852 KB Correct
16 Correct 155 ms 12872 KB Correct
17 Correct 179 ms 12968 KB Correct
18 Correct 106 ms 12468 KB Correct
19 Correct 82 ms 13472 KB Correct
20 Correct 139 ms 13304 KB Correct
21 Correct 71 ms 11152 KB Correct
22 Correct 66 ms 11104 KB Correct
23 Correct 182 ms 12960 KB Correct
24 Correct 179 ms 12960 KB Correct
25 Correct 82 ms 12484 KB Correct
26 Correct 79 ms 14176 KB Correct
27 Correct 70 ms 12576 KB Correct
28 Correct 65 ms 11168 KB Correct
29 Correct 76 ms 11016 KB Correct
30 Correct 192 ms 12944 KB Correct
31 Correct 207 ms 12856 KB Correct
32 Correct 82 ms 11860 KB Correct
33 Correct 200 ms 13084 KB Correct
34 Correct 204 ms 13200 KB Correct
35 Correct 62 ms 11004 KB Correct
36 Correct 73 ms 11024 KB Correct
37 Correct 183 ms 12956 KB Correct
38 Correct 159 ms 12876 KB Correct
39 Correct 261 ms 13432 KB Correct
40 Correct 133 ms 13220 KB Correct
41 Correct 184 ms 12600 KB Correct
42 Correct 79 ms 11136 KB Correct
43 Correct 74 ms 11088 KB Correct
44 Correct 190 ms 12960 KB Correct
45 Correct 181 ms 12772 KB Correct
46 Correct 80 ms 13136 KB Correct
47 Correct 82 ms 13468 KB Correct
48 Correct 71 ms 12368 KB Correct
49 Correct 74 ms 11104 KB Correct
50 Correct 74 ms 10828 KB Correct
51 Correct 69 ms 7648 KB Correct
52 Correct 77 ms 7584 KB Correct
53 Correct 75 ms 7756 KB Correct
54 Correct 79 ms 10348 KB Correct
55 Correct 116 ms 10088 KB Correct
56 Correct 146 ms 10488 KB Correct
57 Correct 65 ms 7424 KB Correct
58 Correct 75 ms 7504 KB Correct
59 Correct 63 ms 7336 KB Correct
60 Incorrect 67 ms 7508 KB Not correct
61 Halted 0 ms 0 KB -