# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
985299 | ph0enlx | Game (APIO22_game) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+10;
vector<set<int>> g(N);
int ng, kg;
void dfs(int ver, int par, bool &exist, vector<bool> &vis, int ret)
{
vis[ver] = true;
for(int child : g[ver])
{
if(vis[child])
{
if(child==ret)
{
exist = true;
return;
}
continue;
}
dfs(child, ver, exist, vis, ret);
}
}
void init(int n, int k)
{
ng = n, kg = k;
for(int i=0; i<k-1; i++)
{
g[i].insert(i+1);
}
}
int add_teleporter(int u, int v)
{
if(u==v && u<k) return 1;
g[u].insert(v);
vector<bool> vis(ng);
bool exist=false;
for(int i=0; i<kg; i++)
{
if(vis[i]) continue;
dfs(i, i, exist, vis, i);
if(exist) return 1;
}
return 0;
}