oj.uz

Submission #1040736

# Submission time Handle Problem Language Result Execution time Memory
1040736 2024-08-01T08:49:52 Z 정민찬(#10997) The Ties That Guide Us (CEOI23_incursion) C++17
30 / 100
 219 ms 14304 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] && 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] * 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:208:17: warning: unused variable 'pos' [-Wunused-variable]
  208 |             int pos = seq.size();
      |                 ^~~
incursion.cpp:290:18: warning: unused variable 'flag' [-Wunused-variable]
  290 |             bool flag = false;
      |                  ^~~~
incursion.cpp:298:33: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
  298 |             if (sz[l] * 2 < sz[r]) swap(l, r);
      |                                 ^
incursion.cpp:294:17: warning: 'prv' may be used uninitialized in this function [-Wmaybe-uninitialized]
  294 |                 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 768 KB Correct

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 12964 KB Correct
2 Correct 167 ms 12952 KB Correct
3 Correct 86 ms 14304 KB Correct
4 Correct 106 ms 12248 KB Correct
5 Correct 160 ms 12700 KB Correct
6 Correct 69 ms 11168 KB Correct
7 Correct 59 ms 11100 KB Correct
8 Correct 187 ms 12948 KB Correct
9 Correct 152 ms 12964 KB Correct
10 Correct 127 ms 12116 KB Correct
11 Correct 84 ms 12816 KB Correct
12 Correct 219 ms 13556 KB Correct
13 Correct 66 ms 10920 KB Correct
14 Correct 68 ms 11176 KB Correct
15 Correct 176 ms 13144 KB Correct
16 Correct 173 ms 13212 KB Correct
17 Correct 111 ms 12520 KB Correct
18 Correct 76 ms 13404 KB Correct
19 Correct 136 ms 13160 KB Correct
20 Correct 74 ms 11032 KB Correct
21 Correct 65 ms 10916 KB Correct
22 Correct 179 ms 12956 KB Correct
23 Correct 187 ms 12964 KB Correct
24 Correct 80 ms 12480 KB Correct
25 Correct 79 ms 13992 KB Correct
26 Correct 69 ms 12700 KB Correct
27 Correct 60 ms 11100 KB Correct
28 Correct 73 ms 10912 KB Correct
29 Correct 199 ms 12948 KB Correct
30 Correct 174 ms 12896 KB Correct
31 Correct 80 ms 11604 KB Correct
32 Correct 180 ms 13404 KB Correct
33 Correct 184 ms 13268 KB Correct
34 Correct 73 ms 11028 KB Correct
35 Correct 68 ms 11164 KB Correct
36 Correct 168 ms 12892 KB Correct
37 Correct 191 ms 12960 KB Correct
38 Correct 196 ms 13488 KB Correct
39 Correct 121 ms 13328 KB Correct
40 Correct 152 ms 12668 KB Correct
41 Correct 67 ms 11072 KB Correct
42 Correct 61 ms 11100 KB Correct
43 Correct 174 ms 12964 KB Correct
44 Correct 194 ms 12972 KB Correct
45 Correct 62 ms 13152 KB Correct
46 Correct 70 ms 13392 KB Correct
47 Correct 86 ms 12516 KB Correct
48 Correct 75 ms 11080 KB Correct
49 Correct 77 ms 11100 KB Correct

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 7448 KB Correct
2 Correct 78 ms 7504 KB Correct
3 Correct 73 ms 7600 KB Correct
4 Correct 83 ms 10348 KB Correct
5 Correct 112 ms 10180 KB Correct
6 Correct 136 ms 10424 KB Correct
7 Correct 63 ms 7244 KB Correct
8 Correct 78 ms 7328 KB Correct
9 Correct 70 ms 7412 KB Correct
10 Incorrect 67 ms 7440 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 768 KB Correct
2 Correct 172 ms 12964 KB Correct
3 Correct 167 ms 12952 KB Correct
4 Correct 86 ms 14304 KB Correct
5 Correct 106 ms 12248 KB Correct
6 Correct 160 ms 12700 KB Correct
7 Correct 69 ms 11168 KB Correct
8 Correct 59 ms 11100 KB Correct
9 Correct 187 ms 12948 KB Correct
10 Correct 152 ms 12964 KB Correct
11 Correct 127 ms 12116 KB Correct
12 Correct 84 ms 12816 KB Correct
13 Correct 219 ms 13556 KB Correct
14 Correct 66 ms 10920 KB Correct
15 Correct 68 ms 11176 KB Correct
16 Correct 176 ms 13144 KB Correct
17 Correct 173 ms 13212 KB Correct
18 Correct 111 ms 12520 KB Correct
19 Correct 76 ms 13404 KB Correct
20 Correct 136 ms 13160 KB Correct
21 Correct 74 ms 11032 KB Correct
22 Correct 65 ms 10916 KB Correct
23 Correct 179 ms 12956 KB Correct
24 Correct 187 ms 12964 KB Correct
25 Correct 80 ms 12480 KB Correct
26 Correct 79 ms 13992 KB Correct
27 Correct 69 ms 12700 KB Correct
28 Correct 60 ms 11100 KB Correct
29 Correct 73 ms 10912 KB Correct
30 Correct 199 ms 12948 KB Correct
31 Correct 174 ms 12896 KB Correct
32 Correct 80 ms 11604 KB Correct
33 Correct 180 ms 13404 KB Correct
34 Correct 184 ms 13268 KB Correct
35 Correct 73 ms 11028 KB Correct
36 Correct 68 ms 11164 KB Correct
37 Correct 168 ms 12892 KB Correct
38 Correct 191 ms 12960 KB Correct
39 Correct 196 ms 13488 KB Correct
40 Correct 121 ms 13328 KB Correct
41 Correct 152 ms 12668 KB Correct
42 Correct 67 ms 11072 KB Correct
43 Correct 61 ms 11100 KB Correct
44 Correct 174 ms 12964 KB Correct
45 Correct 194 ms 12972 KB Correct
46 Correct 62 ms 13152 KB Correct
47 Correct 70 ms 13392 KB Correct
48 Correct 86 ms 12516 KB Correct
49 Correct 75 ms 11080 KB Correct
50 Correct 77 ms 11100 KB Correct
51 Correct 76 ms 7448 KB Correct
52 Correct 78 ms 7504 KB Correct
53 Correct 73 ms 7600 KB Correct
54 Correct 83 ms 10348 KB Correct
55 Correct 112 ms 10180 KB Correct
56 Correct 136 ms 10424 KB Correct
57 Correct 63 ms 7244 KB Correct
58 Correct 78 ms 7328 KB Correct
59 Correct 70 ms 7412 KB Correct
60 Incorrect 67 ms 7440 KB Not correct
61 Halted 0 ms 0 KB -