oj.uz

Submission #1040770

# Submission time Handle Problem Language Result Execution time Memory
1040770 2024-08-01T09:03:43 Z 정민찬(#10997) The Ties That Guide Us (CEOI23_incursion) C++17
30 / 100
 240 ms 14076 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;
    }
    dfs2(curr, -1, sz, adj);
    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: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:295:18: warning: unused variable 'flag' [-Wunused-variable]
  295 |             bool flag = false;
      |                  ^~~~
incursion.cpp:106:10: warning: variable 'totf' set but not used [-Wunused-but-set-variable]
  106 |     bool totf = false;
      |          ^~~~
incursion.cpp:303:29: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
  303 |             if (sz[l] < sz[r]) swap(l, r);
      |                             ^
incursion.cpp:299:17: warning: 'prv' may be used uninitialized in this function [-Wmaybe-uninitialized]
  299 |                 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 764 KB Correct

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 12892 KB Correct
2 Correct 168 ms 12896 KB Correct
3 Correct 89 ms 14076 KB Correct
4 Correct 94 ms 12256 KB Correct
5 Correct 180 ms 12608 KB Correct
6 Correct 76 ms 11116 KB Correct
7 Correct 74 ms 11088 KB Correct
8 Correct 192 ms 12860 KB Correct
9 Correct 199 ms 13148 KB Correct
10 Correct 125 ms 12120 KB Correct
11 Correct 100 ms 12776 KB Correct
12 Correct 216 ms 13676 KB Correct
13 Correct 69 ms 11172 KB Correct
14 Correct 76 ms 11096 KB Correct
15 Correct 191 ms 12876 KB Correct
16 Correct 172 ms 12904 KB Correct
17 Correct 107 ms 12460 KB Correct
18 Correct 73 ms 13716 KB Correct
19 Correct 128 ms 13176 KB Correct
20 Correct 74 ms 11028 KB Correct
21 Correct 78 ms 11092 KB Correct
22 Correct 188 ms 12924 KB Correct
23 Correct 190 ms 12900 KB Correct
24 Correct 80 ms 12488 KB Correct
25 Correct 86 ms 13916 KB Correct
26 Correct 82 ms 12624 KB Correct
27 Correct 75 ms 10988 KB Correct
28 Correct 75 ms 10932 KB Correct
29 Correct 176 ms 12956 KB Correct
30 Correct 161 ms 12952 KB Correct
31 Correct 76 ms 11596 KB Correct
32 Correct 206 ms 13228 KB Correct
33 Correct 238 ms 13388 KB Correct
34 Correct 77 ms 11088 KB Correct
35 Correct 80 ms 11144 KB Correct
36 Correct 180 ms 12964 KB Correct
37 Correct 199 ms 12876 KB Correct
38 Correct 240 ms 13400 KB Correct
39 Correct 120 ms 13224 KB Correct
40 Correct 150 ms 12484 KB Correct
41 Correct 71 ms 11100 KB Correct
42 Correct 68 ms 11044 KB Correct
43 Correct 158 ms 12952 KB Correct
44 Correct 171 ms 12988 KB Correct
45 Correct 75 ms 13148 KB Correct
46 Correct 76 ms 13432 KB Correct
47 Correct 90 ms 12312 KB Correct
48 Correct 69 ms 11044 KB Correct
49 Correct 71 ms 10916 KB Correct

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 7512 KB Correct
2 Correct 67 ms 7468 KB Correct
3 Correct 76 ms 7520 KB Correct
4 Correct 76 ms 10180 KB Correct
5 Correct 118 ms 10316 KB Correct
6 Correct 124 ms 10424 KB Correct
7 Correct 69 ms 7316 KB Correct
8 Correct 70 ms 7436 KB Correct
9 Correct 69 ms 7492 KB Correct
10 Incorrect 61 ms 7332 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 764 KB Correct
2 Correct 179 ms 12892 KB Correct
3 Correct 168 ms 12896 KB Correct
4 Correct 89 ms 14076 KB Correct
5 Correct 94 ms 12256 KB Correct
6 Correct 180 ms 12608 KB Correct
7 Correct 76 ms 11116 KB Correct
8 Correct 74 ms 11088 KB Correct
9 Correct 192 ms 12860 KB Correct
10 Correct 199 ms 13148 KB Correct
11 Correct 125 ms 12120 KB Correct
12 Correct 100 ms 12776 KB Correct
13 Correct 216 ms 13676 KB Correct
14 Correct 69 ms 11172 KB Correct
15 Correct 76 ms 11096 KB Correct
16 Correct 191 ms 12876 KB Correct
17 Correct 172 ms 12904 KB Correct
18 Correct 107 ms 12460 KB Correct
19 Correct 73 ms 13716 KB Correct
20 Correct 128 ms 13176 KB Correct
21 Correct 74 ms 11028 KB Correct
22 Correct 78 ms 11092 KB Correct
23 Correct 188 ms 12924 KB Correct
24 Correct 190 ms 12900 KB Correct
25 Correct 80 ms 12488 KB Correct
26 Correct 86 ms 13916 KB Correct
27 Correct 82 ms 12624 KB Correct
28 Correct 75 ms 10988 KB Correct
29 Correct 75 ms 10932 KB Correct
30 Correct 176 ms 12956 KB Correct
31 Correct 161 ms 12952 KB Correct
32 Correct 76 ms 11596 KB Correct
33 Correct 206 ms 13228 KB Correct
34 Correct 238 ms 13388 KB Correct
35 Correct 77 ms 11088 KB Correct
36 Correct 80 ms 11144 KB Correct
37 Correct 180 ms 12964 KB Correct
38 Correct 199 ms 12876 KB Correct
39 Correct 240 ms 13400 KB Correct
40 Correct 120 ms 13224 KB Correct
41 Correct 150 ms 12484 KB Correct
42 Correct 71 ms 11100 KB Correct
43 Correct 68 ms 11044 KB Correct
44 Correct 158 ms 12952 KB Correct
45 Correct 171 ms 12988 KB Correct
46 Correct 75 ms 13148 KB Correct
47 Correct 76 ms 13432 KB Correct
48 Correct 90 ms 12312 KB Correct
49 Correct 69 ms 11044 KB Correct
50 Correct 71 ms 10916 KB Correct
51 Correct 76 ms 7512 KB Correct
52 Correct 67 ms 7468 KB Correct
53 Correct 76 ms 7520 KB Correct
54 Correct 76 ms 10180 KB Correct
55 Correct 118 ms 10316 KB Correct
56 Correct 124 ms 10424 KB Correct
57 Correct 69 ms 7316 KB Correct
58 Correct 70 ms 7436 KB Correct
59 Correct 69 ms 7492 KB Correct
60 Incorrect 61 ms 7332 KB Not correct
61 Halted 0 ms 0 KB -