oj.uz

답안 #1040684

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1040684 2024-08-01T08:27:45 Z 정민찬(#10997) The Ties That Guide Us (CEOI23_incursion) C++17
30 / 100
 224 ms 14212 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 (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);
            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;
                }
            }
        }
    }
}
/*
using namespace std;
typedef pair<int, int> edge;

constexpr int VISIT = 473895279, ANSWER = 1979520194;

#define VISITING_ALICE "Alice must not call visit"
#define TOO_MANY_VISITS "Bob called visit too often"
#define WRONG_ANSWER "Wrong answer"
#define INVALID_ALICE "Return value of alice invalid"
#define TOO_MANY_TIES "Too many ties in one room"
#define INVALID_VISIT "Invalid call to visit"
#define CORRECT(x,y) "Correct: %d extra visits, Kmax = %d", (x), (y)
#define SECURITY_VIOLATION "Security violation!"

vector<pair<int, float>> _score = {make_pair(1, 1.0f), make_pair(2, 0.4f), make_pair(1000000000, 0.3f)};

void result(double points, const char *msg, ...) {
  va_list args;
  va_start(args, msg);
  vprintf(msg, args);
  va_end(args);
  printf("\n");

    if (points <= 0) {
    exit(0);
    }
  if (points < 1) {
    printf("Partially correct: %.2f%%\n", points * 100);
  }else {
    printf("Correct\n");
  }
  exit(0);
}

class basic_adversary {
  public:
    basic_adversary(vector<edge> E, int d) :
     edges(E), N(E.size() + 1), dest(d), T(N) {
      for(auto [a, b] : edges)
        T[a].push_back(b), T[b].push_back(a);
    }

    ~basic_adversary() {}

    vector<edge> edges_1indexed() {
      vector<edge> E;
      for(auto [a, b] : edges)
        E.emplace_back(a + 1, b + 1);
      return E;
    }

    pair<vector<edge>, int> for_alice() {
      return {edges_1indexed(), dest};
    }
    tuple<vector<edge>, int, int, int> for_bob() {
      return make_tuple(edges_1indexed(), curr_node + 1, ids[curr_node], dist(curr_node, dest-1));
    }

    void answer_alice(vector<int> v) { ids = v; }
    bool answer_bob() { return dest-1 == curr_node; } // should we check whether the solution is unique?
    int visit(int v) {
      if(!connected(curr_node, v)) return -1;
      curr_node = v;
      return ids[curr_node];
    }
    int get_N() { return N; }

    void set_curr_node(int v) { curr_node = v; }

  protected:
    vector<int> ids;
    vector<edge> edges;
    int N;
    int dest;
    int curr_node;
    vector<vector<int>> T;

    int dist(int a, int b) {
      stack<int> s; s.push(a);
      vector<int> dist(T.size(), -1); dist[a] = 0;

      while(!s.empty()) {
        int x = s.top(); s.pop();

        for(int w : T[x])
          if(dist[w] < 0)
            dist[w] = dist[x] + 1, s.push(w);
      }

      return dist[b];
    }

    bool connected(int v, int w) {
      for(int x : T[v])
        if(x == w) return true;
      return false;
    }
};

enum { ALICE = 1337, BOB = 4242 } who;
basic_adversary *adv;
int N;
int Kmax = 0;

int S = 30, counter = 0;

float score(int k) {
  for(auto [bound, s] : _score)
    if(k <= bound) return s;
  assert(false);
  return 0.0;
}

void handle_answer_bob() {
  if(adv->answer_bob()) result(score(Kmax), CORRECT(counter, Kmax));
  else                  result(0.0, WRONG_ANSWER);
}

void handle_alice() {
  who = ALICE;

  // Send Alice the tree and the secret node
  auto [T, dest] = adv->for_alice();

  vector<int> ids = mark(T, dest);
  if (ids.size() != N) result(0.0, INVALID_ALICE);

  printf("mark(F, safe) returned:");
  for(int x : ids) {
    if(x < 0) result(0.0, INVALID_ALICE);
    Kmax = max(Kmax, x);
    printf(" %d", x);
  }
  printf("\n");

  if(Kmax > _score.back().first) result(0.0, TOO_MANY_TIES);
  adv->answer_alice(ids);
}

int visit(int w) {
  if(who != BOB) {
    result(0.0, VISITING_ALICE);
  }

  ++counter;
  if(counter > S) result(0.0, TOO_MANY_VISITS);

  if(w < 1 or w > N) result(0.0, INVALID_VISIT);
  --w;
  int x = adv->visit(w);
  if(x == -1) result(0.0, INVALID_VISIT);
  return x;
}

void handle_bob() {
  who = BOB;

  auto [T, start, x, dist] = adv->for_bob();
  
  counter -= dist;

  locate(T, start, x);

  handle_answer_bob();
}

int main() {
  int safe;
  assert(scanf("%d %d", &N, &safe) == 2);

  vector<edge> edges;
  for(int i = 1; i < N; ++i) {
    int u, v; scanf("%d %d", &u, &v);
    u -= 1; v -= 1;
    edges.emplace_back(u, v);
  }
  
  adv = new basic_adversary(edges, safe);
  
  handle_alice();

  int curr; scanf("%d", &curr);
  curr -= 1;
  adv->set_curr_node(curr);

  handle_bob();

  return 0;
}*/

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:202:17: warning: unused variable 'pos' [-Wunused-variable]
  202 |             int pos = seq.size();
      |                 ^~~
incursion.cpp:280:18: warning: unused variable 'flag' [-Wunused-variable]
  280 |             bool flag = false;
      |                  ^~~~
incursion.cpp:288:29: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
  288 |             if (sz[l] < sz[r]) swap(l, r);
      |                             ^
incursion.cpp:284:17: warning: 'prv' may be used uninitialized in this function [-Wmaybe-uninitialized]
  284 |                 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 768 KB Correct

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 173 ms 12884 KB Correct
2 Correct 167 ms 12880 KB Correct
3 Correct 95 ms 14212 KB Correct
4 Correct 87 ms 12232 KB Correct
5 Correct 160 ms 12828 KB Correct
6 Correct 71 ms 10944 KB Correct
7 Correct 71 ms 11000 KB Correct
8 Correct 183 ms 12892 KB Correct
9 Correct 184 ms 12972 KB Correct
10 Correct 123 ms 12108 KB Correct
11 Correct 87 ms 12700 KB Correct
12 Correct 217 ms 13628 KB Correct
13 Correct 67 ms 11168 KB Correct
14 Correct 70 ms 11116 KB Correct
15 Correct 162 ms 12960 KB Correct
16 Correct 183 ms 13084 KB Correct
17 Correct 101 ms 12460 KB Correct
18 Correct 83 ms 13580 KB Correct
19 Correct 125 ms 13340 KB Correct
20 Correct 72 ms 11096 KB Correct
21 Correct 70 ms 11092 KB Correct
22 Correct 180 ms 13212 KB Correct
23 Correct 160 ms 12892 KB Correct
24 Correct 86 ms 12324 KB Correct
25 Correct 65 ms 13980 KB Correct
26 Correct 77 ms 12620 KB Correct
27 Correct 74 ms 11040 KB Correct
28 Correct 72 ms 11104 KB Correct
29 Correct 195 ms 12968 KB Correct
30 Correct 182 ms 12956 KB Correct
31 Correct 77 ms 11620 KB Correct
32 Correct 224 ms 13348 KB Correct
33 Correct 181 ms 13272 KB Correct
34 Correct 66 ms 11100 KB Correct
35 Correct 66 ms 11028 KB Correct
36 Correct 169 ms 12964 KB Correct
37 Correct 157 ms 12960 KB Correct
38 Correct 203 ms 13488 KB Correct
39 Correct 119 ms 13032 KB Correct
40 Correct 182 ms 12372 KB Correct
41 Correct 64 ms 11112 KB Correct
42 Correct 68 ms 10916 KB Correct
43 Correct 192 ms 12960 KB Correct
44 Correct 147 ms 12972 KB Correct
45 Correct 71 ms 13072 KB Correct
46 Correct 72 ms 13376 KB Correct
47 Correct 94 ms 12556 KB Correct
48 Correct 71 ms 10912 KB Correct
49 Correct 72 ms 11108 KB Correct

Subtask #2
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 63 ms 7588 KB Correct
2 Correct 63 ms 7516 KB Correct
3 Correct 72 ms 7512 KB Correct
4 Correct 75 ms 10076 KB Correct
5 Correct 110 ms 10068 KB Correct
6 Correct 153 ms 10480 KB Correct
7 Correct 73 ms 7500 KB Correct
8 Correct 67 ms 7324 KB Correct
9 Correct 62 ms 7516 KB Correct
10 Incorrect 69 ms 7332 KB Not correct
11 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 768 KB Correct
2 Correct 173 ms 12884 KB Correct
3 Correct 167 ms 12880 KB Correct
4 Correct 95 ms 14212 KB Correct
5 Correct 87 ms 12232 KB Correct
6 Correct 160 ms 12828 KB Correct
7 Correct 71 ms 10944 KB Correct
8 Correct 71 ms 11000 KB Correct
9 Correct 183 ms 12892 KB Correct
10 Correct 184 ms 12972 KB Correct
11 Correct 123 ms 12108 KB Correct
12 Correct 87 ms 12700 KB Correct
13 Correct 217 ms 13628 KB Correct
14 Correct 67 ms 11168 KB Correct
15 Correct 70 ms 11116 KB Correct
16 Correct 162 ms 12960 KB Correct
17 Correct 183 ms 13084 KB Correct
18 Correct 101 ms 12460 KB Correct
19 Correct 83 ms 13580 KB Correct
20 Correct 125 ms 13340 KB Correct
21 Correct 72 ms 11096 KB Correct
22 Correct 70 ms 11092 KB Correct
23 Correct 180 ms 13212 KB Correct
24 Correct 160 ms 12892 KB Correct
25 Correct 86 ms 12324 KB Correct
26 Correct 65 ms 13980 KB Correct
27 Correct 77 ms 12620 KB Correct
28 Correct 74 ms 11040 KB Correct
29 Correct 72 ms 11104 KB Correct
30 Correct 195 ms 12968 KB Correct
31 Correct 182 ms 12956 KB Correct
32 Correct 77 ms 11620 KB Correct
33 Correct 224 ms 13348 KB Correct
34 Correct 181 ms 13272 KB Correct
35 Correct 66 ms 11100 KB Correct
36 Correct 66 ms 11028 KB Correct
37 Correct 169 ms 12964 KB Correct
38 Correct 157 ms 12960 KB Correct
39 Correct 203 ms 13488 KB Correct
40 Correct 119 ms 13032 KB Correct
41 Correct 182 ms 12372 KB Correct
42 Correct 64 ms 11112 KB Correct
43 Correct 68 ms 10916 KB Correct
44 Correct 192 ms 12960 KB Correct
45 Correct 147 ms 12972 KB Correct
46 Correct 71 ms 13072 KB Correct
47 Correct 72 ms 13376 KB Correct
48 Correct 94 ms 12556 KB Correct
49 Correct 71 ms 10912 KB Correct
50 Correct 72 ms 11108 KB Correct
51 Correct 63 ms 7588 KB Correct
52 Correct 63 ms 7516 KB Correct
53 Correct 72 ms 7512 KB Correct
54 Correct 75 ms 10076 KB Correct
55 Correct 110 ms 10068 KB Correct
56 Correct 153 ms 10480 KB Correct
57 Correct 73 ms 7500 KB Correct
58 Correct 67 ms 7324 KB Correct
59 Correct 62 ms 7516 KB Correct
60 Incorrect 69 ms 7332 KB Not correct
61 Halted 0 ms 0 KB -