Submission #1205208

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205208		dosts	The Ties That Guide Us (CEOI23_incursion)	C++20	9 / 100	144 ms	5068 KiB

incursion

#include <bits/stdc++.h>
#include "incursion.h"
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
//#define int long long
#define pii pair<int,int> 
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " << 
#define all(x) x.begin(),x.end()
using namespace std;

const int N = 45000;
vector<vi> edges(N);
vi dist(N,-1);

void dfs(int node,int der = 0) {
  if (dist[node] != -1) return;
  dist[node] = der;
  for (auto it : edges[node]) dfs(it,der+1);

}

std::vector<int> mark(std::vector<std::pair<int, int>> F, int safe) {
  int n = 0;
  for (int i = 0;i<F.size();i++){
    F[i].ff--,F[i].ss--;
    if (edges[F[i].ff].empty()) n++;
    if (edges[F[i].ss].empty()) n++;
    edges[F[i].ff].push_back(F[i].ss);
    edges[F[i].ss].push_back(F[i].ff);
  }
  dfs(safe-1);
  dist.resize(n);
  edges.resize(n);
  return dist;
}

int play(int curr,int t,int par) {
  for (auto it : edges[curr]) {
    if (it == par) continue;
    int x = visit(it+1);
    if (x > t) {
      //wrong direction
      visit(curr+1);
      continue;
    }
    return play(it,x,curr);
  }
  return curr+1;
}

void locate(std::vector<std::pair<int, int>> F, int curr, int t) {
  for (auto& it : edges) it.clear();
  for (int i = 0;i<F.size();i++){
    F[i].ff--,F[i].ss--;
    edges[F[i].ff].push_back(F[i].ss);
    edges[F[i].ss].push_back(F[i].ff);
  }
  curr--;
  curr = play(curr,t,curr);
}

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