Submission #744412

#	Time	Username	Problem	Language	Result	Execution time	Memory
744412		amirhoseinfar1385	Game (APIO22_game)	C++17	30 / 100	4078 ms	7972 KiB

game

#include<bits/stdc++.h>
using namespace std;
const int maxn=300000+10;
int fk=0,fn=0;
vector<int>adj[maxn];
int cnt[maxn],w[maxn],vis[maxn];
void init(int n, int k) {
  for(int i=0;i<k-1;i++){
    adj[i].push_back(i+1);
  }
  fk=k;
  fn=n;
}
int f=0,sz=0;
deque<int>vec;
void aval(int u){
  vis[u]=1;
  for(auto x:adj[u]){
    if(vis[x]==0){
      aval(x);
    }
  }
  vec.push_back(u);
}

void dovom(int u){
  vis[u]=1;
  w[u]=sz;
  cnt[sz]++;
  for(auto x:adj[u]){
    if(vis[x]==0){
      dovom(x);
    }
  }
}


int add_teleporter(int u, int v) {
  adj[u].push_back(v);
  if(f==1||(u<fk&&v==u)){
    f=1;
    return 1;
  }
  for(int i=0;i<=sz;i++){
    cnt[i]=0;
  }
  for(int i=0;i<fn;i++){
    vis[i]=w[i]=0;
  }
  vec.clear();
  for(int i=0;i<fn;i++){
    if(vis[i]==0){
      aval(i);
    }
  }
  for(int i=0;i<fn;i++){
    vis[i]=0;
  }
  sz=0;
  while((int)vec.size()>0){
    int x=vec.front();
    vec.pop_front();
    if(vis[x]==0){
      sz++;
      dovom(x);
    }
  }
  for(int i=0;i<fk;i++){
    if(cnt[w[i]]>1){
      f=1;
    }
  }
  if(f){
    return 1;
  }
  return 0;
}

• Subtask 1: 2 / 2
• Subtask 2: 10 / 10
• Subtask 3: 18 / 18
• Subtask 4: 0 / 30
• Subtask 5: 0 / 40