Submission #1146349

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146349		ind1v	The Ties That Guide Us (CEOI23_incursion)	C++17	0 / 100	40 ms	3832 KiB

incursion

#include <bits/stdc++.h>
#include "incursion.h"

using namespace std;

const int N = 5e4 + 5;

vector<int> mark(vector<pair<int, int>> F, int safe) {
  vector<int> g[N];
  int n = F.size() + 1;
  for (auto x : F) {
    g[x.first - 1].emplace_back(x.second - 1);
    g[x.second - 1].emplace_back(x.first - 1);
  }
  vector<int> d(n, -1);
  safe--;
  d[safe] = 0;
  queue<int> q;
  q.push(safe);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int v : g[u]) {
      if (d[v] == -1) {
        d[v] = d[u] + 1;
        q.push(v);
      }
    }
  }
  return d;
}

void dfs(int u, int p, vector<vector<int>> &g, vector<int> &fa) {
  for (int v : g[u]) {
    if (v != p) {
      fa[v] = u;
      dfs(v, u, g, fa);
    }
  }
}

void locate(vector<pair<int, int>> F, int curr, int t) {
  vector<vector<int>> g;
  int n = F.size() + 1;
  assert(n == 44895);
  g.resize(N);
  int deg[N];
  memset(deg, 0, sizeof(deg));
  for (auto x : F) {
    g[x.first].emplace_back(x.second);
    g[x.second].emplace_back(x.first);
    deg[x.first]++;
    deg[x.second]++;
  }
  bool f = true;
  for (int i = 1; i <= n; i++) {
    f &= (deg[i] < 3);
  }
  if (f) {
    int x = curr;
    set<int> vis;
    if (t == 0) {
      return;
    }
    vis.insert(x);
    if (g[x].size() == 1) {
      vis.insert(g[x][0]);
      x = g[x][0];
    } else {
      int y = visit(g[x][0]);
      visit(x);
      int z = visit(g[x][1]);
      visit(x);
      if (y < z) {
        visit(g[x][0]);
        x = g[x][0];
        vis.insert(x);
      } else {
        visit(g[x][1]);
        x = g[x][1];
        vis.insert(x);
      }
    }
    t--;
    while (t > 0) {
      if (g[x].size() == 1) {
        visit(g[x][0]);
        vis.insert(g[x][0]);
        x = g[x][0];
      } else if (g[x].size() == 2) {
        if (vis.count(g[x][0])) {
          visit(g[x][1]);
          vis.insert(g[x][1]);
          x = g[x][1];
        } else {
          visit(g[x][0]);
          vis.insert(g[x][0]);
          x = g[x][0];
        }
      }
      t--;
    }
    return;
  }
  vector<int> fa(N, 0);
  int root;
  for (int i = 1; i <= n; i++) {
    if (deg[i] == 2) {
      root = i;
    }
  }
  dfs(root, root, g, fa);
  if (t == 0) {
    return;
  }
  int x = curr;
  set<int> vis;
  vis.insert(x);
  while (x != root) {
    if (visit(fa[x]) < t) {
      x = fa[x];
      vis.insert(x);
      t--;
    } else {
      visit(x);
      break;
    }
  }
  while (t > 0) {
    vector<int> cnd;
    for (int y : g[x]) {
      if (!vis.count(y)) {
        cnd.emplace_back(y);
      }
    }
    if (visit(cnd[0]) < t) {
      t--;
      x = cnd[0];
      vis.insert(x);
    } else {
      visit(x);
      visit(cnd[1]);
      t--;
      x = cnd[1];
      vis.insert(x);
    }
  }
  return;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40