oj.uz

Submission #1060703

# Submission time Handle Problem Language Result Execution time Memory
1060703 2024-08-15T20:55:49 Z MilosMilutinovic The Ties That Guide Us (CEOI23_incursion) C++17
0 / 100
 693 ms 1048576 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);
      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]) {
          que.push_back(j);
        }
      }
    }
  }
  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 764 KB Correct

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 13336 KB Correct
2 Correct 208 ms 13800 KB Correct
3 Correct 127 ms 14844 KB Correct
4 Runtime error 693 ms 1048576 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 7916 KB Correct
2 Correct 72 ms 8112 KB Correct
3 Correct 82 ms 7932 KB Correct
4 Correct 96 ms 11848 KB Correct
5 Correct 145 ms 11200 KB Correct
6 Correct 157 ms 11264 KB Correct
7 Correct 79 ms 7932 KB Correct
8 Correct 78 ms 8004 KB Correct
9 Correct 84 ms 7848 KB Correct
10 Incorrect 77 ms 8008 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 223 ms 13336 KB Correct
3 Correct 208 ms 13800 KB Correct
4 Correct 127 ms 14844 KB Correct
5 Runtime error 693 ms 1048576 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -