oj.uz

Submission #1040691

# Submission time Handle Problem Language Result Execution time Memory
1040691 2024-08-01T08:30:54 Z 정민찬(#10997) The Ties That Guide Us (CEOI23_incursion) C++17
30 / 100
 230 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);
            assert(0);
            curr = l;
            vector<int> col(3);
            for (int i=0; i<3; i++) {
                int y = adj[curr][i];
                if (col[y] != -1) 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);
            assert(0);
            curr = r;
            vector<int> col(3);
            for (int i=0; i<3; i++) {
                int y = adj[curr][i];
                if (col[y] != -1) 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];
            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:204:17: warning: unused variable 'pos' [-Wunused-variable]
  204 |             int pos = seq.size();
      |                 ^~~
incursion.cpp:282:18: warning: unused variable 'flag' [-Wunused-variable]
  282 |             bool flag = false;
      |                  ^~~~
incursion.cpp:290:29: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
  290 |             if (sz[l] < sz[r]) swap(l, r);
      |                             ^
incursion.cpp:286:17: warning: 'prv' may be used uninitialized in this function [-Wmaybe-uninitialized]
  286 |                 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 176 ms 12964 KB Correct
2 Correct 179 ms 12856 KB Correct
3 Correct 94 ms 14288 KB Correct
4 Correct 100 ms 12224 KB Correct
5 Correct 165 ms 12608 KB Correct
6 Correct 81 ms 11028 KB Correct
7 Correct 71 ms 11032 KB Correct
8 Correct 213 ms 12880 KB Correct
9 Correct 198 ms 12864 KB Correct
10 Correct 137 ms 12108 KB Correct
11 Correct 93 ms 12876 KB Correct
12 Correct 230 ms 13620 KB Correct
13 Correct 73 ms 11020 KB Correct
14 Correct 82 ms 11088 KB Correct
15 Correct 170 ms 12900 KB Correct
16 Correct 171 ms 12896 KB Correct
17 Correct 110 ms 12316 KB Correct
18 Correct 81 ms 13492 KB Correct
19 Correct 132 ms 13084 KB Correct
20 Correct 80 ms 11036 KB Correct
21 Correct 68 ms 10912 KB Correct
22 Correct 157 ms 12880 KB Correct
23 Correct 177 ms 12888 KB Correct
24 Correct 68 ms 12408 KB Correct
25 Correct 80 ms 14100 KB Correct
26 Correct 87 ms 12752 KB Correct
27 Correct 66 ms 11096 KB Correct
28 Correct 91 ms 11072 KB Correct
29 Correct 141 ms 12948 KB Correct
30 Correct 166 ms 12892 KB Correct
31 Correct 83 ms 11568 KB Correct
32 Correct 181 ms 13288 KB Correct
33 Correct 171 ms 13200 KB Correct
34 Correct 72 ms 10916 KB Correct
35 Correct 71 ms 10852 KB Correct
36 Correct 152 ms 13144 KB Correct
37 Correct 165 ms 12960 KB Correct
38 Correct 205 ms 13436 KB Correct
39 Correct 131 ms 13036 KB Correct
40 Correct 169 ms 12604 KB Correct
41 Correct 70 ms 10996 KB Correct
42 Correct 69 ms 11108 KB Correct
43 Correct 196 ms 12888 KB Correct
44 Correct 180 ms 12900 KB Correct
45 Correct 73 ms 13152 KB Correct
46 Correct 66 ms 13408 KB Correct
47 Correct 86 ms 12380 KB Correct
48 Correct 69 ms 10908 KB Correct
49 Correct 71 ms 11020 KB Correct

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 7580 KB Correct
2 Correct 76 ms 7444 KB Correct
3 Correct 76 ms 7512 KB Correct
4 Correct 83 ms 10148 KB Correct
5 Correct 124 ms 10072 KB Correct
6 Correct 144 ms 10352 KB Correct
7 Correct 64 ms 7676 KB Correct
8 Correct 71 ms 7476 KB Correct
9 Correct 78 ms 7496 KB Correct
10 Runtime error 74 ms 11092 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 776 KB Correct
2 Correct 176 ms 12964 KB Correct
3 Correct 179 ms 12856 KB Correct
4 Correct 94 ms 14288 KB Correct
5 Correct 100 ms 12224 KB Correct
6 Correct 165 ms 12608 KB Correct
7 Correct 81 ms 11028 KB Correct
8 Correct 71 ms 11032 KB Correct
9 Correct 213 ms 12880 KB Correct
10 Correct 198 ms 12864 KB Correct
11 Correct 137 ms 12108 KB Correct
12 Correct 93 ms 12876 KB Correct
13 Correct 230 ms 13620 KB Correct
14 Correct 73 ms 11020 KB Correct
15 Correct 82 ms 11088 KB Correct
16 Correct 170 ms 12900 KB Correct
17 Correct 171 ms 12896 KB Correct
18 Correct 110 ms 12316 KB Correct
19 Correct 81 ms 13492 KB Correct
20 Correct 132 ms 13084 KB Correct
21 Correct 80 ms 11036 KB Correct
22 Correct 68 ms 10912 KB Correct
23 Correct 157 ms 12880 KB Correct
24 Correct 177 ms 12888 KB Correct
25 Correct 68 ms 12408 KB Correct
26 Correct 80 ms 14100 KB Correct
27 Correct 87 ms 12752 KB Correct
28 Correct 66 ms 11096 KB Correct
29 Correct 91 ms 11072 KB Correct
30 Correct 141 ms 12948 KB Correct
31 Correct 166 ms 12892 KB Correct
32 Correct 83 ms 11568 KB Correct
33 Correct 181 ms 13288 KB Correct
34 Correct 171 ms 13200 KB Correct
35 Correct 72 ms 10916 KB Correct
36 Correct 71 ms 10852 KB Correct
37 Correct 152 ms 13144 KB Correct
38 Correct 165 ms 12960 KB Correct
39 Correct 205 ms 13436 KB Correct
40 Correct 131 ms 13036 KB Correct
41 Correct 169 ms 12604 KB Correct
42 Correct 70 ms 10996 KB Correct
43 Correct 69 ms 11108 KB Correct
44 Correct 196 ms 12888 KB Correct
45 Correct 180 ms 12900 KB Correct
46 Correct 73 ms 13152 KB Correct
47 Correct 66 ms 13408 KB Correct
48 Correct 86 ms 12380 KB Correct
49 Correct 69 ms 10908 KB Correct
50 Correct 71 ms 11020 KB Correct
51 Correct 69 ms 7580 KB Correct
52 Correct 76 ms 7444 KB Correct
53 Correct 76 ms 7512 KB Correct
54 Correct 83 ms 10148 KB Correct
55 Correct 124 ms 10072 KB Correct
56 Correct 144 ms 10352 KB Correct
57 Correct 64 ms 7676 KB Correct
58 Correct 71 ms 7476 KB Correct
59 Correct 78 ms 7496 KB Correct
60 Runtime error 74 ms 11092 KB Execution killed with signal 6
61 Halted 0 ms 0 KB -