oj.uz

Submission #1040747

# Submission time Handle Problem Language Result Execution time Memory
1040747 2024-08-01T08:54:52 Z 정민찬(#10997) The Ties That Guide Us (CEOI23_incursion) C++17
30 / 100
 254 ms 14252 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;
    }
    if (totf) assert(0);
    while (true) {
        if (adj[curr].size() == 1) {
            if (totf) assert(0);
            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);
                if (totf) assert(0);
                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);
                    if (totf) assert(0);
                    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:297:18: warning: unused variable 'flag' [-Wunused-variable]
  297 |             bool flag = false;
      |                  ^~~~
incursion.cpp:305:33: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
  305 |             if (sz[l] * 2 < sz[r]) swap(l, r);
      |                                 ^
incursion.cpp:301:17: warning: 'prv' may be used uninitialized in this function [-Wmaybe-uninitialized]
  301 |                 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 155 ms 12956 KB Correct
2 Correct 175 ms 13152 KB Correct
3 Correct 90 ms 14252 KB Correct
4 Correct 77 ms 12060 KB Correct
5 Correct 159 ms 12676 KB Correct
6 Correct 69 ms 11180 KB Correct
7 Correct 62 ms 11096 KB Correct
8 Correct 171 ms 13140 KB Correct
9 Correct 181 ms 12952 KB Correct
10 Correct 123 ms 12112 KB Correct
11 Correct 83 ms 12892 KB Correct
12 Correct 254 ms 13548 KB Correct
13 Correct 67 ms 10908 KB Correct
14 Correct 68 ms 11032 KB Correct
15 Correct 186 ms 12964 KB Correct
16 Correct 165 ms 12912 KB Correct
17 Correct 100 ms 12520 KB Correct
18 Correct 70 ms 13572 KB Correct
19 Correct 129 ms 13156 KB Correct
20 Correct 70 ms 11040 KB Correct
21 Correct 72 ms 11116 KB Correct
22 Correct 172 ms 12956 KB Correct
23 Correct 171 ms 12900 KB Correct
24 Correct 87 ms 12316 KB Correct
25 Correct 82 ms 14116 KB Correct
26 Correct 69 ms 12648 KB Correct
27 Correct 67 ms 11164 KB Correct
28 Correct 69 ms 11020 KB Correct
29 Correct 191 ms 12668 KB Correct
30 Correct 202 ms 12844 KB Correct
31 Correct 75 ms 11720 KB Correct
32 Correct 179 ms 13264 KB Correct
33 Correct 197 ms 13276 KB Correct
34 Correct 78 ms 11164 KB Correct
35 Correct 72 ms 11104 KB Correct
36 Correct 160 ms 12956 KB Correct
37 Correct 178 ms 12956 KB Correct
38 Correct 200 ms 13420 KB Correct
39 Correct 112 ms 13204 KB Correct
40 Correct 145 ms 12672 KB Correct
41 Correct 70 ms 11084 KB Correct
42 Correct 77 ms 11028 KB Correct
43 Correct 201 ms 12696 KB Correct
44 Correct 170 ms 12880 KB Correct
45 Correct 68 ms 12896 KB Correct
46 Correct 84 ms 13324 KB Correct
47 Correct 80 ms 12700 KB Correct
48 Correct 66 ms 10908 KB Correct
49 Correct 76 ms 11088 KB Correct

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 7520 KB Correct
2 Correct 78 ms 7596 KB Correct
3 Correct 86 ms 7440 KB Correct
4 Correct 68 ms 10140 KB Correct
5 Correct 107 ms 10152 KB Correct
6 Correct 124 ms 10484 KB Correct
7 Correct 83 ms 7232 KB Correct
8 Correct 79 ms 7416 KB Correct
9 Correct 83 ms 7428 KB Correct
10 Runtime error 60 ms 11008 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 155 ms 12956 KB Correct
3 Correct 175 ms 13152 KB Correct
4 Correct 90 ms 14252 KB Correct
5 Correct 77 ms 12060 KB Correct
6 Correct 159 ms 12676 KB Correct
7 Correct 69 ms 11180 KB Correct
8 Correct 62 ms 11096 KB Correct
9 Correct 171 ms 13140 KB Correct
10 Correct 181 ms 12952 KB Correct
11 Correct 123 ms 12112 KB Correct
12 Correct 83 ms 12892 KB Correct
13 Correct 254 ms 13548 KB Correct
14 Correct 67 ms 10908 KB Correct
15 Correct 68 ms 11032 KB Correct
16 Correct 186 ms 12964 KB Correct
17 Correct 165 ms 12912 KB Correct
18 Correct 100 ms 12520 KB Correct
19 Correct 70 ms 13572 KB Correct
20 Correct 129 ms 13156 KB Correct
21 Correct 70 ms 11040 KB Correct
22 Correct 72 ms 11116 KB Correct
23 Correct 172 ms 12956 KB Correct
24 Correct 171 ms 12900 KB Correct
25 Correct 87 ms 12316 KB Correct
26 Correct 82 ms 14116 KB Correct
27 Correct 69 ms 12648 KB Correct
28 Correct 67 ms 11164 KB Correct
29 Correct 69 ms 11020 KB Correct
30 Correct 191 ms 12668 KB Correct
31 Correct 202 ms 12844 KB Correct
32 Correct 75 ms 11720 KB Correct
33 Correct 179 ms 13264 KB Correct
34 Correct 197 ms 13276 KB Correct
35 Correct 78 ms 11164 KB Correct
36 Correct 72 ms 11104 KB Correct
37 Correct 160 ms 12956 KB Correct
38 Correct 178 ms 12956 KB Correct
39 Correct 200 ms 13420 KB Correct
40 Correct 112 ms 13204 KB Correct
41 Correct 145 ms 12672 KB Correct
42 Correct 70 ms 11084 KB Correct
43 Correct 77 ms 11028 KB Correct
44 Correct 201 ms 12696 KB Correct
45 Correct 170 ms 12880 KB Correct
46 Correct 68 ms 12896 KB Correct
47 Correct 84 ms 13324 KB Correct
48 Correct 80 ms 12700 KB Correct
49 Correct 66 ms 10908 KB Correct
50 Correct 76 ms 11088 KB Correct
51 Correct 60 ms 7520 KB Correct
52 Correct 78 ms 7596 KB Correct
53 Correct 86 ms 7440 KB Correct
54 Correct 68 ms 10140 KB Correct
55 Correct 107 ms 10152 KB Correct
56 Correct 124 ms 10484 KB Correct
57 Correct 83 ms 7232 KB Correct
58 Correct 79 ms 7416 KB Correct
59 Correct 83 ms 7428 KB Correct
60 Runtime error 60 ms 11008 KB Execution killed with signal 6
61 Halted 0 ms 0 KB -