oj.uz

Submission #1040698

# Submission time Handle Problem Language Result Execution time Memory
1040698 2024-08-01T08:34:22 Z 정민찬(#10997) The Ties That Guide Us (CEOI23_incursion) C++17
30 / 100
 232 ms 14164 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);
            assert(0);
            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) 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:288:18: warning: unused variable 'flag' [-Wunused-variable]
  288 |             bool flag = false;
      |                  ^~~~
incursion.cpp:296:29: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
  296 |             if (sz[l] < sz[r]) swap(l, r);
      |                             ^
incursion.cpp:292:17: warning: 'prv' may be used uninitialized in this function [-Wmaybe-uninitialized]
  292 |                 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 159 ms 12904 KB Correct
2 Correct 163 ms 12960 KB Correct
3 Correct 92 ms 14164 KB Correct
4 Correct 103 ms 12160 KB Correct
5 Correct 191 ms 12604 KB Correct
6 Correct 91 ms 10792 KB Correct
7 Correct 71 ms 10832 KB Correct
8 Correct 172 ms 12884 KB Correct
9 Correct 172 ms 12876 KB Correct
10 Correct 145 ms 12044 KB Correct
11 Correct 84 ms 13068 KB Correct
12 Correct 232 ms 13528 KB Correct
13 Correct 67 ms 11004 KB Correct
14 Correct 86 ms 11016 KB Correct
15 Correct 181 ms 12980 KB Correct
16 Correct 178 ms 12956 KB Correct
17 Correct 106 ms 12576 KB Correct
18 Correct 84 ms 13532 KB Correct
19 Correct 123 ms 13112 KB Correct
20 Correct 77 ms 10824 KB Correct
21 Correct 76 ms 11004 KB Correct
22 Correct 179 ms 12896 KB Correct
23 Correct 160 ms 12956 KB Correct
24 Correct 76 ms 12480 KB Correct
25 Correct 91 ms 13876 KB Correct
26 Correct 75 ms 12624 KB Correct
27 Correct 74 ms 11092 KB Correct
28 Correct 83 ms 11100 KB Correct
29 Correct 190 ms 12800 KB Correct
30 Correct 173 ms 12864 KB Correct
31 Correct 77 ms 11620 KB Correct
32 Correct 188 ms 13092 KB Correct
33 Correct 213 ms 13204 KB Correct
34 Correct 74 ms 11164 KB Correct
35 Correct 76 ms 11072 KB Correct
36 Correct 173 ms 12952 KB Correct
37 Correct 151 ms 13136 KB Correct
38 Correct 196 ms 13428 KB Correct
39 Correct 116 ms 13144 KB Correct
40 Correct 148 ms 12472 KB Correct
41 Correct 66 ms 10844 KB Correct
42 Correct 55 ms 10912 KB Correct
43 Correct 191 ms 12956 KB Correct
44 Correct 181 ms 13216 KB Correct
45 Correct 77 ms 12984 KB Correct
46 Correct 70 ms 13480 KB Correct
47 Correct 91 ms 12532 KB Correct
48 Correct 70 ms 11096 KB Correct
49 Correct 72 ms 10960 KB Correct

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 68 ms 7456 KB Not correct
2 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 159 ms 12904 KB Correct
3 Correct 163 ms 12960 KB Correct
4 Correct 92 ms 14164 KB Correct
5 Correct 103 ms 12160 KB Correct
6 Correct 191 ms 12604 KB Correct
7 Correct 91 ms 10792 KB Correct
8 Correct 71 ms 10832 KB Correct
9 Correct 172 ms 12884 KB Correct
10 Correct 172 ms 12876 KB Correct
11 Correct 145 ms 12044 KB Correct
12 Correct 84 ms 13068 KB Correct
13 Correct 232 ms 13528 KB Correct
14 Correct 67 ms 11004 KB Correct
15 Correct 86 ms 11016 KB Correct
16 Correct 181 ms 12980 KB Correct
17 Correct 178 ms 12956 KB Correct
18 Correct 106 ms 12576 KB Correct
19 Correct 84 ms 13532 KB Correct
20 Correct 123 ms 13112 KB Correct
21 Correct 77 ms 10824 KB Correct
22 Correct 76 ms 11004 KB Correct
23 Correct 179 ms 12896 KB Correct
24 Correct 160 ms 12956 KB Correct
25 Correct 76 ms 12480 KB Correct
26 Correct 91 ms 13876 KB Correct
27 Correct 75 ms 12624 KB Correct
28 Correct 74 ms 11092 KB Correct
29 Correct 83 ms 11100 KB Correct
30 Correct 190 ms 12800 KB Correct
31 Correct 173 ms 12864 KB Correct
32 Correct 77 ms 11620 KB Correct
33 Correct 188 ms 13092 KB Correct
34 Correct 213 ms 13204 KB Correct
35 Correct 74 ms 11164 KB Correct
36 Correct 76 ms 11072 KB Correct
37 Correct 173 ms 12952 KB Correct
38 Correct 151 ms 13136 KB Correct
39 Correct 196 ms 13428 KB Correct
40 Correct 116 ms 13144 KB Correct
41 Correct 148 ms 12472 KB Correct
42 Correct 66 ms 10844 KB Correct
43 Correct 55 ms 10912 KB Correct
44 Correct 191 ms 12956 KB Correct
45 Correct 181 ms 13216 KB Correct
46 Correct 77 ms 12984 KB Correct
47 Correct 70 ms 13480 KB Correct
48 Correct 91 ms 12532 KB Correct
49 Correct 70 ms 11096 KB Correct
50 Correct 72 ms 10960 KB Correct
51 Incorrect 68 ms 7456 KB Not correct
52 Halted 0 ms 0 KB -