oj.uz

Submission #1060740

# Submission time Handle Problem Language Result Execution time Memory
1060740 2024-08-15T21:39:42 Z MilosMilutinovic The Ties That Guide Us (CEOI23_incursion) C++17
30 / 100
 279 ms 16124 KB 
#include "incursion.h"
#include <bits/stdc++.h>

using namespace std;

vector<int> mark(vector<pair<int, int>> e, int safe) {
  --safe;
  int n = (int) e.size() + 1;
  vector<vector<int>> g(n);
  for (int i = 0; i + 1 < n; i++) {
    --e[i].first; --e[i].second;
    g[e[i].first].push_back(e[i].second);
    g[e[i].second].push_back(e[i].first);
  }
  int root;
  {
    vector<int> sz(n);
    function<void(int, int)> Dfs = [&](int v, int pv) {
      sz[v] = 1;
      for (int u : g[v]) {
        if (u == pv) {
          continue;
        }
        Dfs(u, v);
        sz[v] += sz[u];
      }
    };
    Dfs(0, 0);
    vector<int> cen;
    function<int(int, int)> FindCentroid = [&](int v, int pv) {
      if (sz[v] * 2 == n) {
        cen.push_back(pv);
      }
      for (int u : g[v]) {
        if (u == pv || sz[u] * 2 < n) {
          continue;
        }
        return FindCentroid(u, v);
      }
      cen.push_back(v);
      return v;
    };
    root = FindCentroid(0, 0);
    if ((int) cen.size() == 2) {
      vector<int> que(1, safe);
      vector<bool> was(n);
      was[safe] = true;
      for (int b = 0; b < (int) que.size(); b++) {
        int i = que[b];
        if (i == cen[0] || i == cen[1]) {
          root = i;
          break;
        }
        for (int j : g[i]) {
          if (!was[j]) {
            que.push_back(j);
            was[j] = true;
          }
        }
      }
    }
  }
  int cnt = 0;
  for (int i = 0; i < n; i++) {
    if ((int) g[i].size() == 2) {
      cnt += 1;
    }
  }
  vector<int> dfn(n);
  vector<int> dfo(n);
  int T = -1;
  function<void(int, int)> Dfs = [&](int v, int pv) {
    dfn[v] = ++T;
    for (int u : g[v]) {
      if (u == pv) {
        continue;
      }
      Dfs(u, v);
    }
    dfo[v] = T;
  };
  Dfs(root, root);
  vector<int> seq(n);
  for (int i = 0; i < n; i++) {
    if (dfn[i] <= dfn[safe] && dfo[safe] <= dfo[i]) {
      seq[i] = 1;
    } else {
      seq[i] = 0;
    }
  }
  return seq;
}

void locate(vector<pair<int, int>> e, int curr, int t) {
  --curr;
  int n = (int) e.size() + 1;
  vector<vector<int>> g(n);
  for (int i = 0; i + 1 < n; i++) {
    --e[i].first; --e[i].second;
    g[e[i].first].push_back(e[i].second);
    g[e[i].second].push_back(e[i].first);
  }
  vector<int> cen;
  {
    vector<int> sz(n);
    function<void(int, int)> Dfs = [&](int v, int pv) {
      sz[v] = 1;
      for (int u : g[v]) {
        if (u == pv) {
          continue;
        }
        Dfs(u, v);
        sz[v] += sz[u];
      }
    };
    Dfs(0, 0);
    function<void(int, int)> Find = [&](int v, int pv) {
      if (sz[v] * 2 == n) {
        cen.push_back(pv);
      }
      for (int u : g[v]) {
        if (u == pv || sz[u] * 2 < n) {
          continue;
        }
        Find(u, v);
        return;
      }
      cen.push_back(v);
    };
    Find(0, 0);
  }
  int root = cen[0];
  int cnt = 0;
  for (int i = 0; i < n; i++) {
    if ((int) g[i].size() == 2) {
      cnt += 1;
    }
  }
  vector<int> x(n, -1);
  vector<int> pr(n);
  vector<int> sz(n);
  function<void(int, int)> Dfs = [&](int v, int pv) {
    pr[v] = pv;
    sz[v] = 1;
    for (int u : g[v]) {
      if (u == pv) {
        continue;
      }
      Dfs(u, v);
      sz[v] += sz[u];
      if (x[v] == -1 || sz[x[v]] < sz[u]) {
        x[v] = u;
      }
    }
  };
  Dfs(root, root);
  int Q = 0;
  while (true) {
    if (curr == root && t == 0) {
      root = cen[1];
      x = vector<int>(n, -1);
      Dfs(root, root);
      t = visit(root + 1);
      assert(t == 1);
      curr = root;
      continue;
    }
    if (t == 0) {
      t = visit(pr[curr] + 1);
      curr = pr[curr];
      continue;
    }
    if (x[curr] == -1) {
      return;
    }
    int k = visit(x[curr] + 1);
    if (k == 1) {
      curr = x[curr];
      t = k;
      continue;
    }
    Q += 2;
    assert(Q <= 30);
    visit(curr + 1);
    bool found = false;
    for (int u : g[curr]) {
      if (u == pr[curr] || u == x[curr]) {
        continue;
      }
      int k = visit(u + 1);
      if (k == 1) {
        t = k;
        curr = u;
        found = true;
        break;
      }
      Q += 2;
      assert(Q <= 30);
      visit(curr + 1);
    }
    if (!found) {
      return;
    }
  }
}

Compilation message

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 216 ms 13324 KB Correct
2 Correct 206 ms 13800 KB Correct
3 Correct 110 ms 14712 KB Correct
4 Correct 105 ms 15512 KB Correct
5 Correct 194 ms 15256 KB Correct
6 Correct 86 ms 15616 KB Correct
7 Correct 82 ms 13676 KB Correct
8 Correct 187 ms 14064 KB Correct
9 Correct 227 ms 14720 KB Correct
10 Correct 144 ms 14028 KB Correct
11 Correct 105 ms 15544 KB Correct
12 Correct 279 ms 14012 KB Correct
13 Correct 92 ms 13120 KB Correct
14 Correct 84 ms 13828 KB Correct
15 Correct 211 ms 14796 KB Correct
16 Correct 214 ms 16124 KB Correct
17 Correct 131 ms 12796 KB Correct
18 Correct 96 ms 13544 KB Correct
19 Correct 162 ms 12808 KB Correct
20 Correct 88 ms 15084 KB Correct
21 Correct 88 ms 13872 KB Correct
22 Correct 232 ms 14272 KB Correct
23 Correct 201 ms 14184 KB Correct
24 Correct 89 ms 13380 KB Correct
25 Correct 98 ms 14768 KB Correct
26 Correct 93 ms 13216 KB Correct
27 Correct 86 ms 13820 KB Correct
28 Correct 83 ms 14172 KB Correct
29 Correct 227 ms 14324 KB Correct
30 Correct 201 ms 13068 KB Correct
31 Correct 93 ms 15556 KB Correct
32 Correct 255 ms 14632 KB Correct
33 Correct 235 ms 14820 KB Correct
34 Correct 86 ms 13312 KB Correct
35 Correct 90 ms 12792 KB Correct
36 Correct 215 ms 14156 KB Correct
37 Correct 214 ms 14404 KB Correct
38 Correct 273 ms 15476 KB Correct
39 Correct 147 ms 15568 KB Correct
40 Correct 191 ms 15212 KB Correct
41 Correct 93 ms 14992 KB Correct
42 Correct 89 ms 14296 KB Correct
43 Correct 237 ms 14292 KB Correct
44 Correct 224 ms 12536 KB Correct
45 Correct 91 ms 13312 KB Correct
46 Correct 91 ms 13984 KB Correct
47 Correct 102 ms 14636 KB Correct
48 Correct 82 ms 12860 KB Correct
49 Correct 89 ms 15084 KB Correct

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 7936 KB Correct
2 Correct 84 ms 8000 KB Correct
3 Correct 74 ms 7924 KB Correct
4 Correct 84 ms 12196 KB Correct
5 Correct 135 ms 11128 KB Correct
6 Correct 158 ms 11296 KB Correct
7 Correct 79 ms 8012 KB Correct
8 Correct 80 ms 8004 KB Correct
9 Correct 81 ms 8012 KB Correct
10 Incorrect 81 ms 8004 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 216 ms 13324 KB Correct
3 Correct 206 ms 13800 KB Correct
4 Correct 110 ms 14712 KB Correct
5 Correct 105 ms 15512 KB Correct
6 Correct 194 ms 15256 KB Correct
7 Correct 86 ms 15616 KB Correct
8 Correct 82 ms 13676 KB Correct
9 Correct 187 ms 14064 KB Correct
10 Correct 227 ms 14720 KB Correct
11 Correct 144 ms 14028 KB Correct
12 Correct 105 ms 15544 KB Correct
13 Correct 279 ms 14012 KB Correct
14 Correct 92 ms 13120 KB Correct
15 Correct 84 ms 13828 KB Correct
16 Correct 211 ms 14796 KB Correct
17 Correct 214 ms 16124 KB Correct
18 Correct 131 ms 12796 KB Correct
19 Correct 96 ms 13544 KB Correct
20 Correct 162 ms 12808 KB Correct
21 Correct 88 ms 15084 KB Correct
22 Correct 88 ms 13872 KB Correct
23 Correct 232 ms 14272 KB Correct
24 Correct 201 ms 14184 KB Correct
25 Correct 89 ms 13380 KB Correct
26 Correct 98 ms 14768 KB Correct
27 Correct 93 ms 13216 KB Correct
28 Correct 86 ms 13820 KB Correct
29 Correct 83 ms 14172 KB Correct
30 Correct 227 ms 14324 KB Correct
31 Correct 201 ms 13068 KB Correct
32 Correct 93 ms 15556 KB Correct
33 Correct 255 ms 14632 KB Correct
34 Correct 235 ms 14820 KB Correct
35 Correct 86 ms 13312 KB Correct
36 Correct 90 ms 12792 KB Correct
37 Correct 215 ms 14156 KB Correct
38 Correct 214 ms 14404 KB Correct
39 Correct 273 ms 15476 KB Correct
40 Correct 147 ms 15568 KB Correct
41 Correct 191 ms 15212 KB Correct
42 Correct 93 ms 14992 KB Correct
43 Correct 89 ms 14296 KB Correct
44 Correct 237 ms 14292 KB Correct
45 Correct 224 ms 12536 KB Correct
46 Correct 91 ms 13312 KB Correct
47 Correct 91 ms 13984 KB Correct
48 Correct 102 ms 14636 KB Correct
49 Correct 82 ms 12860 KB Correct
50 Correct 89 ms 15084 KB Correct
51 Correct 81 ms 7936 KB Correct
52 Correct 84 ms 8000 KB Correct
53 Correct 74 ms 7924 KB Correct
54 Correct 84 ms 12196 KB Correct
55 Correct 135 ms 11128 KB Correct
56 Correct 158 ms 11296 KB Correct
57 Correct 79 ms 8012 KB Correct
58 Correct 80 ms 8004 KB Correct
59 Correct 81 ms 8012 KB Correct
60 Incorrect 81 ms 8004 KB Not correct
61 Halted 0 ms 0 KB -