oj.uz

Submission #1060699

# Submission time Handle Problem Language Result Execution time Memory
1060699 2024-08-15T20:52:13 Z MilosMilutinovic The Ties That Guide Us (CEOI23_incursion) C++17
0 / 100
 224 ms 15884 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);
    for (int u : cen) {
      if (u == safe) {
        root = u;
      }
    }
  }
  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];
  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);
  while (true) {
    if (curr == root && t == 0) {
      root = cen[1];
      Dfs(root, 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;
    }
    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;
      }
      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 768 KB Correct

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 13404 KB Correct
2 Correct 217 ms 13560 KB Correct
3 Correct 104 ms 14660 KB Correct
4 Correct 110 ms 15884 KB Correct
5 Correct 197 ms 15340 KB Correct
6 Correct 83 ms 15348 KB Correct
7 Correct 76 ms 13568 KB Correct
8 Correct 222 ms 13984 KB Correct
9 Correct 211 ms 14712 KB Correct
10 Correct 155 ms 13764 KB Correct
11 Correct 110 ms 15424 KB Correct
12 Incorrect 186 ms 13792 KB Not correct
13 Halted 0 ms 0 KB -

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 7920 KB Correct
2 Correct 75 ms 7996 KB Correct
3 Correct 82 ms 7996 KB Correct
4 Correct 99 ms 11764 KB Correct
5 Correct 139 ms 11128 KB Correct
6 Correct 162 ms 11176 KB Correct
7 Correct 80 ms 8004 KB Correct
8 Correct 78 ms 7856 KB Correct
9 Correct 80 ms 8004 KB Correct
10 Incorrect 76 ms 7944 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 768 KB Correct
2 Correct 224 ms 13404 KB Correct
3 Correct 217 ms 13560 KB Correct
4 Correct 104 ms 14660 KB Correct
5 Correct 110 ms 15884 KB Correct
6 Correct 197 ms 15340 KB Correct
7 Correct 83 ms 15348 KB Correct
8 Correct 76 ms 13568 KB Correct
9 Correct 222 ms 13984 KB Correct
10 Correct 211 ms 14712 KB Correct
11 Correct 155 ms 13764 KB Correct
12 Correct 110 ms 15424 KB Correct
13 Incorrect 186 ms 13792 KB Not correct
14 Halted 0 ms 0 KB -