oj.uz

Submission #1040706

# Submission time Handle Problem Language Result Execution time Memory
1040706 2024-08-01T08:38:04 Z 정민찬(#10997) The Ties That Guide Us (CEOI23_incursion) C++17
30 / 100
 232 ms 14288 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;
            assert(0);
        }
        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);
        }
        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 179 ms 12952 KB Correct
2 Correct 182 ms 12992 KB Correct
3 Correct 92 ms 14288 KB Correct
4 Correct 100 ms 11940 KB Correct
5 Correct 171 ms 12672 KB Correct
6 Correct 71 ms 11032 KB Correct
7 Correct 69 ms 11108 KB Correct
8 Correct 186 ms 12956 KB Correct
9 Correct 170 ms 12948 KB Correct
10 Correct 130 ms 12116 KB Correct
11 Correct 91 ms 12960 KB Correct
12 Correct 230 ms 13568 KB Correct
13 Correct 67 ms 11120 KB Correct
14 Correct 66 ms 11176 KB Correct
15 Correct 151 ms 12892 KB Correct
16 Correct 172 ms 13156 KB Correct
17 Correct 102 ms 12704 KB Correct
18 Correct 70 ms 13664 KB Correct
19 Correct 138 ms 13152 KB Correct
20 Correct 67 ms 11096 KB Correct
21 Correct 72 ms 10984 KB Correct
22 Correct 171 ms 12960 KB Correct
23 Correct 170 ms 12960 KB Correct
24 Correct 80 ms 12480 KB Correct
25 Correct 78 ms 14172 KB Correct
26 Correct 80 ms 12860 KB Correct
27 Correct 65 ms 11112 KB Correct
28 Correct 72 ms 11104 KB Correct
29 Correct 190 ms 12876 KB Correct
30 Correct 171 ms 13212 KB Correct
31 Correct 81 ms 11604 KB Correct
32 Correct 202 ms 12892 KB Correct
33 Correct 198 ms 13360 KB Correct
34 Correct 68 ms 11164 KB Correct
35 Correct 70 ms 11164 KB Correct
36 Correct 169 ms 12888 KB Correct
37 Correct 170 ms 12960 KB Correct
38 Correct 232 ms 13432 KB Correct
39 Correct 122 ms 13408 KB Correct
40 Correct 172 ms 12740 KB Correct
41 Correct 67 ms 11172 KB Correct
42 Correct 72 ms 11104 KB Correct
43 Correct 173 ms 12952 KB Correct
44 Correct 156 ms 12884 KB Correct
45 Correct 68 ms 12960 KB Correct
46 Correct 71 ms 13392 KB Correct
47 Correct 87 ms 12572 KB Correct
48 Correct 71 ms 11188 KB Correct
49 Correct 68 ms 11172 KB Correct

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 7512 KB Correct
2 Correct 70 ms 7580 KB Correct
3 Correct 70 ms 7500 KB Correct
4 Correct 74 ms 10576 KB Correct
5 Correct 125 ms 10156 KB Correct
6 Correct 142 ms 10408 KB Correct
7 Correct 66 ms 7576 KB Correct
8 Correct 73 ms 7516 KB Correct
9 Correct 63 ms 7636 KB Correct
10 Runtime error 67 ms 11164 KB Execution killed with signal 6
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 179 ms 12952 KB Correct
3 Correct 182 ms 12992 KB Correct
4 Correct 92 ms 14288 KB Correct
5 Correct 100 ms 11940 KB Correct
6 Correct 171 ms 12672 KB Correct
7 Correct 71 ms 11032 KB Correct
8 Correct 69 ms 11108 KB Correct
9 Correct 186 ms 12956 KB Correct
10 Correct 170 ms 12948 KB Correct
11 Correct 130 ms 12116 KB Correct
12 Correct 91 ms 12960 KB Correct
13 Correct 230 ms 13568 KB Correct
14 Correct 67 ms 11120 KB Correct
15 Correct 66 ms 11176 KB Correct
16 Correct 151 ms 12892 KB Correct
17 Correct 172 ms 13156 KB Correct
18 Correct 102 ms 12704 KB Correct
19 Correct 70 ms 13664 KB Correct
20 Correct 138 ms 13152 KB Correct
21 Correct 67 ms 11096 KB Correct
22 Correct 72 ms 10984 KB Correct
23 Correct 171 ms 12960 KB Correct
24 Correct 170 ms 12960 KB Correct
25 Correct 80 ms 12480 KB Correct
26 Correct 78 ms 14172 KB Correct
27 Correct 80 ms 12860 KB Correct
28 Correct 65 ms 11112 KB Correct
29 Correct 72 ms 11104 KB Correct
30 Correct 190 ms 12876 KB Correct
31 Correct 171 ms 13212 KB Correct
32 Correct 81 ms 11604 KB Correct
33 Correct 202 ms 12892 KB Correct
34 Correct 198 ms 13360 KB Correct
35 Correct 68 ms 11164 KB Correct
36 Correct 70 ms 11164 KB Correct
37 Correct 169 ms 12888 KB Correct
38 Correct 170 ms 12960 KB Correct
39 Correct 232 ms 13432 KB Correct
40 Correct 122 ms 13408 KB Correct
41 Correct 172 ms 12740 KB Correct
42 Correct 67 ms 11172 KB Correct
43 Correct 72 ms 11104 KB Correct
44 Correct 173 ms 12952 KB Correct
45 Correct 156 ms 12884 KB Correct
46 Correct 68 ms 12960 KB Correct
47 Correct 71 ms 13392 KB Correct
48 Correct 87 ms 12572 KB Correct
49 Correct 71 ms 11188 KB Correct
50 Correct 68 ms 11172 KB Correct
51 Correct 66 ms 7512 KB Correct
52 Correct 70 ms 7580 KB Correct
53 Correct 70 ms 7500 KB Correct
54 Correct 74 ms 10576 KB Correct
55 Correct 125 ms 10156 KB Correct
56 Correct 142 ms 10408 KB Correct
57 Correct 66 ms 7576 KB Correct
58 Correct 73 ms 7516 KB Correct
59 Correct 63 ms 7636 KB Correct
60 Runtime error 67 ms 11164 KB Execution killed with signal 6
61 Halted 0 ms 0 KB -