| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1326301 | aren_dance | The Ties That Guide Us (CEOI23_incursion) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "incursion.h"
using namespace std;
std::vector<int> mark(std::vector<std::pair<int, int>>f, int safe){
queue<pair<int,int>> q;
vectorr<int> ans;
q.push({0,safe});
const int N=45001;
vector<vector<int>> g(N);
vector<bool> vis(N,0);
int n=0;
for(int i=0;i<f.size();++i){
g[f[i].first].push_back(f[i].second);
g[f[i].second].push_back(f[i].first);
n=max(n,f[i].first);
n=max(n,f[i].second);
}
ans.resize(n);
ans[safe-1]=0;
while(!q.empty()){
int x=q.front().first;
int y=q.front().second;
for(auto j:g[x]){
if(!vis[j]){
q.push({j,y+1});
ans[j-1]=y+1;
}
}
}
return ans;
}
vector<vector<int>> g(N);
int sz[N];
void dfs(int v,int p){
int c=0;
vector<pair<int,int>> r;
for(auto i:g[v]){
if(i!=p){
dfs(i,v);
sz[v]+=sz[i];
r.push_back({sz[i],c});
}
++c;
}
sort(r.begin(),r.end());
swap(g[v][r[0].second],g[v][0]);
}
void locate(std::vector<std::pair<int, int>> f, int curr, int t){
if(t==0){
return;
}
for(int i=0;i<f.size();++i){
g[f[i].first].push_back(f[i].second);
}
for(int i=0;i<f.size();++i){
g[f[i].second].push_back(f[i].first);
}
dfs(cur,0);
int nxt;
for(int i=0;i<g[cur].size();++i){
int o=visit(g[cur][i]);
if(o>t){
visit(cur);
}
else{
nxt=g[cur][i];
t=o;
}
}
int pap=cur;
cur=nxt;
while(t!=0){
int nxt;
for(int i=0;i<g[cur].size();++i){
if(g[cur][i]==pap){
continue;
}
int o=visit(g[cur][i]);
if(o>t){
visit(cur);
}
else{
nxt=g[cur][i];
t=o;
}
}
pap=cur;
cur=nxt;
}
}