oj.uz

Submission #1040722

# Submission time Handle Problem Language Result Execution time Memory
1040722 2024-08-01T08:44:25 Z 정민찬(#10997) The Ties That Guide Us (CEOI23_incursion) C++17
30 / 100
 241 ms 14208 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);
            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);
        }
        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: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 0 ms 768 KB Correct

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 12872 KB Correct
2 Correct 177 ms 12960 KB Correct
3 Correct 92 ms 14112 KB Correct
4 Correct 92 ms 12228 KB Correct
5 Correct 174 ms 12668 KB Correct
6 Correct 71 ms 11160 KB Correct
7 Correct 72 ms 11092 KB Correct
8 Correct 166 ms 12960 KB Correct
9 Correct 177 ms 12884 KB Correct
10 Correct 135 ms 12032 KB Correct
11 Correct 95 ms 13004 KB Correct
12 Correct 241 ms 13624 KB Correct
13 Correct 80 ms 11104 KB Correct
14 Correct 64 ms 11032 KB Correct
15 Correct 171 ms 12800 KB Correct
16 Correct 194 ms 13080 KB Correct
17 Correct 110 ms 12456 KB Correct
18 Correct 87 ms 13468 KB Correct
19 Correct 149 ms 13064 KB Correct
20 Correct 69 ms 10840 KB Correct
21 Correct 74 ms 11104 KB Correct
22 Correct 183 ms 12960 KB Correct
23 Correct 157 ms 12892 KB Correct
24 Correct 77 ms 12696 KB Correct
25 Correct 72 ms 14208 KB Correct
26 Correct 72 ms 12704 KB Correct
27 Correct 68 ms 11024 KB Correct
28 Correct 76 ms 10916 KB Correct
29 Correct 173 ms 12956 KB Correct
30 Correct 184 ms 13208 KB Correct
31 Correct 79 ms 11600 KB Correct
32 Correct 236 ms 13252 KB Correct
33 Correct 214 ms 13272 KB Correct
34 Correct 73 ms 10844 KB Correct
35 Correct 80 ms 11100 KB Correct
36 Correct 198 ms 12892 KB Correct
37 Correct 178 ms 12892 KB Correct
38 Correct 188 ms 13412 KB Correct
39 Correct 127 ms 13032 KB Correct
40 Correct 171 ms 12656 KB Correct
41 Correct 66 ms 11112 KB Correct
42 Correct 77 ms 11348 KB Correct
43 Correct 179 ms 12948 KB Correct
44 Correct 205 ms 12956 KB Correct
45 Correct 80 ms 12776 KB Correct
46 Correct 73 ms 13480 KB Correct
47 Correct 83 ms 12640 KB Correct
48 Correct 76 ms 10832 KB Correct
49 Correct 75 ms 10836 KB Correct

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 7516 KB Correct
2 Correct 63 ms 7664 KB Correct
3 Correct 69 ms 7580 KB Correct
4 Correct 84 ms 10280 KB Correct
5 Correct 133 ms 10092 KB Correct
6 Correct 154 ms 10612 KB Correct
7 Correct 68 ms 7284 KB Correct
8 Correct 70 ms 7260 KB Correct
9 Correct 75 ms 7484 KB Correct
10 Incorrect 71 ms 7432 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 166 ms 12872 KB Correct
3 Correct 177 ms 12960 KB Correct
4 Correct 92 ms 14112 KB Correct
5 Correct 92 ms 12228 KB Correct
6 Correct 174 ms 12668 KB Correct
7 Correct 71 ms 11160 KB Correct
8 Correct 72 ms 11092 KB Correct
9 Correct 166 ms 12960 KB Correct
10 Correct 177 ms 12884 KB Correct
11 Correct 135 ms 12032 KB Correct
12 Correct 95 ms 13004 KB Correct
13 Correct 241 ms 13624 KB Correct
14 Correct 80 ms 11104 KB Correct
15 Correct 64 ms 11032 KB Correct
16 Correct 171 ms 12800 KB Correct
17 Correct 194 ms 13080 KB Correct
18 Correct 110 ms 12456 KB Correct
19 Correct 87 ms 13468 KB Correct
20 Correct 149 ms 13064 KB Correct
21 Correct 69 ms 10840 KB Correct
22 Correct 74 ms 11104 KB Correct
23 Correct 183 ms 12960 KB Correct
24 Correct 157 ms 12892 KB Correct
25 Correct 77 ms 12696 KB Correct
26 Correct 72 ms 14208 KB Correct
27 Correct 72 ms 12704 KB Correct
28 Correct 68 ms 11024 KB Correct
29 Correct 76 ms 10916 KB Correct
30 Correct 173 ms 12956 KB Correct
31 Correct 184 ms 13208 KB Correct
32 Correct 79 ms 11600 KB Correct
33 Correct 236 ms 13252 KB Correct
34 Correct 214 ms 13272 KB Correct
35 Correct 73 ms 10844 KB Correct
36 Correct 80 ms 11100 KB Correct
37 Correct 198 ms 12892 KB Correct
38 Correct 178 ms 12892 KB Correct
39 Correct 188 ms 13412 KB Correct
40 Correct 127 ms 13032 KB Correct
41 Correct 171 ms 12656 KB Correct
42 Correct 66 ms 11112 KB Correct
43 Correct 77 ms 11348 KB Correct
44 Correct 179 ms 12948 KB Correct
45 Correct 205 ms 12956 KB Correct
46 Correct 80 ms 12776 KB Correct
47 Correct 73 ms 13480 KB Correct
48 Correct 83 ms 12640 KB Correct
49 Correct 76 ms 10832 KB Correct
50 Correct 75 ms 10836 KB Correct
51 Correct 68 ms 7516 KB Correct
52 Correct 63 ms 7664 KB Correct
53 Correct 69 ms 7580 KB Correct
54 Correct 84 ms 10280 KB Correct
55 Correct 133 ms 10092 KB Correct
56 Correct 154 ms 10612 KB Correct
57 Correct 68 ms 7284 KB Correct
58 Correct 70 ms 7260 KB Correct
59 Correct 75 ms 7484 KB Correct
60 Incorrect 71 ms 7432 KB Not correct
61 Halted 0 ms 0 KB -