oj.uz

Submission #1040756

# Submission time Handle Problem Language Result Execution time Memory
1040756 2024-08-01T08:57:17 Z 정민찬(#10997) The Ties That Guide Us (CEOI23_incursion) C++17
30 / 100
 229 ms 14144 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) {
            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] * 3 < sz[r]*2) swap(l, r);
            else if (sz[l] * 2 <= sz[r] * 3) {
                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: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:294:18: warning: unused variable 'flag' [-Wunused-variable]
  294 |             bool flag = false;
      |                  ^~~~
incursion.cpp:106:10: warning: variable 'totf' set but not used [-Wunused-but-set-variable]
  106 |     bool totf = false;
      |          ^~~~
incursion.cpp:302:33: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
  302 |             if (sz[l] * 3 < sz[r]*2) 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 1 ms 1016 KB Correct

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 12900 KB Correct
2 Correct 172 ms 12896 KB Correct
3 Correct 94 ms 14144 KB Correct
4 Correct 91 ms 12052 KB Correct
5 Correct 161 ms 12660 KB Correct
6 Correct 72 ms 11100 KB Correct
7 Correct 68 ms 11084 KB Correct
8 Correct 173 ms 12900 KB Correct
9 Correct 187 ms 12816 KB Correct
10 Correct 125 ms 12044 KB Correct
11 Correct 89 ms 13136 KB Correct
12 Correct 209 ms 13632 KB Correct
13 Correct 66 ms 10908 KB Correct
14 Correct 70 ms 11164 KB Correct
15 Correct 196 ms 12952 KB Correct
16 Correct 189 ms 12972 KB Correct
17 Correct 109 ms 12376 KB Correct
18 Correct 72 ms 13484 KB Correct
19 Correct 142 ms 13160 KB Correct
20 Correct 67 ms 10856 KB Correct
21 Correct 66 ms 11108 KB Correct
22 Correct 177 ms 12892 KB Correct
23 Correct 181 ms 12964 KB Correct
24 Correct 79 ms 12388 KB Correct
25 Correct 78 ms 13992 KB Correct
26 Correct 77 ms 12632 KB Correct
27 Correct 72 ms 11084 KB Correct
28 Correct 60 ms 11104 KB Correct
29 Correct 199 ms 12964 KB Correct
30 Correct 156 ms 13144 KB Correct
31 Correct 76 ms 11528 KB Correct
32 Correct 213 ms 13092 KB Correct
33 Correct 203 ms 13396 KB Correct
34 Correct 71 ms 11112 KB Correct
35 Correct 67 ms 10924 KB Correct
36 Correct 180 ms 13088 KB Correct
37 Correct 205 ms 12880 KB Correct
38 Correct 229 ms 13500 KB Correct
39 Correct 108 ms 13032 KB Correct
40 Correct 160 ms 12676 KB Correct
41 Correct 69 ms 11020 KB Correct
42 Correct 66 ms 10908 KB Correct
43 Correct 180 ms 12896 KB Correct
44 Correct 171 ms 12956 KB Correct
45 Correct 73 ms 12980 KB Correct
46 Correct 63 ms 13208 KB Correct
47 Correct 88 ms 12368 KB Correct
48 Correct 68 ms 11160 KB Correct
49 Correct 73 ms 11104 KB Correct

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 7516 KB Correct
2 Correct 68 ms 7688 KB Correct
3 Correct 71 ms 7508 KB Correct
4 Correct 80 ms 10064 KB Correct
5 Correct 112 ms 10096 KB Correct
6 Correct 162 ms 10328 KB Correct
7 Correct 64 ms 7584 KB Correct
8 Correct 62 ms 7520 KB Correct
9 Correct 69 ms 7492 KB Correct
10 Incorrect 62 ms 7600 KB Not correct
11 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1016 KB Correct
2 Correct 168 ms 12900 KB Correct
3 Correct 172 ms 12896 KB Correct
4 Correct 94 ms 14144 KB Correct
5 Correct 91 ms 12052 KB Correct
6 Correct 161 ms 12660 KB Correct
7 Correct 72 ms 11100 KB Correct
8 Correct 68 ms 11084 KB Correct
9 Correct 173 ms 12900 KB Correct
10 Correct 187 ms 12816 KB Correct
11 Correct 125 ms 12044 KB Correct
12 Correct 89 ms 13136 KB Correct
13 Correct 209 ms 13632 KB Correct
14 Correct 66 ms 10908 KB Correct
15 Correct 70 ms 11164 KB Correct
16 Correct 196 ms 12952 KB Correct
17 Correct 189 ms 12972 KB Correct
18 Correct 109 ms 12376 KB Correct
19 Correct 72 ms 13484 KB Correct
20 Correct 142 ms 13160 KB Correct
21 Correct 67 ms 10856 KB Correct
22 Correct 66 ms 11108 KB Correct
23 Correct 177 ms 12892 KB Correct
24 Correct 181 ms 12964 KB Correct
25 Correct 79 ms 12388 KB Correct
26 Correct 78 ms 13992 KB Correct
27 Correct 77 ms 12632 KB Correct
28 Correct 72 ms 11084 KB Correct
29 Correct 60 ms 11104 KB Correct
30 Correct 199 ms 12964 KB Correct
31 Correct 156 ms 13144 KB Correct
32 Correct 76 ms 11528 KB Correct
33 Correct 213 ms 13092 KB Correct
34 Correct 203 ms 13396 KB Correct
35 Correct 71 ms 11112 KB Correct
36 Correct 67 ms 10924 KB Correct
37 Correct 180 ms 13088 KB Correct
38 Correct 205 ms 12880 KB Correct
39 Correct 229 ms 13500 KB Correct
40 Correct 108 ms 13032 KB Correct
41 Correct 160 ms 12676 KB Correct
42 Correct 69 ms 11020 KB Correct
43 Correct 66 ms 10908 KB Correct
44 Correct 180 ms 12896 KB Correct
45 Correct 171 ms 12956 KB Correct
46 Correct 73 ms 12980 KB Correct
47 Correct 63 ms 13208 KB Correct
48 Correct 88 ms 12368 KB Correct
49 Correct 68 ms 11160 KB Correct
50 Correct 73 ms 11104 KB Correct
51 Correct 70 ms 7516 KB Correct
52 Correct 68 ms 7688 KB Correct
53 Correct 71 ms 7508 KB Correct
54 Correct 80 ms 10064 KB Correct
55 Correct 112 ms 10096 KB Correct
56 Correct 162 ms 10328 KB Correct
57 Correct 64 ms 7584 KB Correct
58 Correct 62 ms 7520 KB Correct
59 Correct 69 ms 7492 KB Correct
60 Incorrect 62 ms 7600 KB Not correct
61 Halted 0 ms 0 KB -