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 "game.h"
#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
int const n_max=3e5+10;
int mx[n_max],mn[n_max];
vector<int> node[n_max];
vector<int> rnode[n_max];
int n,k;
void init(int N, int K)
{
n=N;
k=K;
for(int i=1;i<=k;i++)mx[i]=mn[i]=i;
for(int i=k+1;i<=n;i++)mx[i]=0,mn[i]=k+1;
}
bool flag=false;
int add_teleporter(int uu, int vv)
{
uu++;
vv++;
if(flag)return 1;
if (uu >= vv && uu <= k){flag=true;return 1;}
if (uu == vv) return 0;
node[uu].push_back(vv);
rnode[vv].push_back(uu);
deque<pii> q;
q.push_front({uu,vv});
while(!q.empty())
{
int u=q.front().fi,v=q.front().se;
q.pop_front();
if(mx[u]>=mn[v])
{
flag=true;
return 1;
}
if(mn[u]<=mx[v])
{
continue;
}
while (mx[u] >= (mn[v] + mx[v]) / 2+1)
{
mx[v] = (mx[v] + mn[v]) / 2+1;
for (auto it:node[v])
{
q.push_front({v,it});
}
}
while (mn[v] <= (mn[u] + mx[u]) / 2)
{
mn[u] = (mx[u] + mn[u]) / 2 ;
for (auto it:rnode[u])
{
q.push_front({it,u});
}
}
}
if(flag)return 1;
return 0;
/* queue<int> q;
int val=mx[u];
if(u<k)val=u;
if(val==-1)return 0;
q.push(v);
while(!q.empty())
{
int cur=q.front();
q.pop();
if(mx[cur]>=val)continue;
if(cur<k&&val>=cur)
{
flag=true;
return 1;
}
mx[cur]=val;
for(auto nxt:node[cur])
{
if(mx[nxt]>=val)continue;
q.push(nxt);
}
}
return 0; */
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |