Submission #1103563

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103563		epicci23	Game (APIO22_game)	C++17	60 / 100	4075 ms	40436 KiB

game

#include "bits/stdc++.h"
#include "game.h"
//#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;


const int N = 3e5 + 5;
vector<int> v[N],g[N];
int n,k,in[N],out[N];
bool ok=0;

void upd_in(int a,int val){
  if(val>=in[a] || ok) return;
  in[a]=val;
  if(in[a]<out[a]){
  	ok=1;
  	return;
  }
  if(in[a]==out[a] && a>=k){
  	ok=1;
  	return;
  }
  for(int x:g[a]){
  	upd_in(x,val);
  	if(ok) return;
  }
}


void upd_out(int a,int val){
  if(val<=out[a] || ok) return;
  out[a]=val;
  if(in[a]<out[a]){
  	ok=1;
  	return;
  }
  if(in[a]==out[a] && a>=k){
  	ok=1;
  	return;
  }
  for(int x:v[a]){
  	upd_out(x,val);
  	if(ok) return;
  }
}

void init(int _n,int _k){
  n=_n,k=_k;
  fill(in,in+N,k);
  fill(out,out+N,-1);
  for(int i=0;i<k;i++) in[i]=out[i]=i;
  
  for(int i=0;i<k-1;i++){
  	v[i].push_back(i+1);
    g[i+1].push_back(i);
  }
}

int add_teleporter(int a, int b){
  v[a].push_back(b);
  g[b].push_back(a);
  if(in[a]>in[b]) upd_in(a,in[b]);
  if(out[a]>out[b]) upd_out(b,out[a]);
  if(a==b && a<k) ok=1;
  return ok;
}

/*void _(){
  cin >> n >> m >> k;

  fill(in,in+N,k);
  fill(out,out+N,-1);
  for(int i=0;i<k;i++) in[i]=out[i]=i;
  
  for(int i=0;i<k-1;i++){
  	v[i].push_back(i+1);
    g[i+1].push_back(i);
  }

  for(int i=1;i<=m;i++){
    int a,b;
    cin >> a >> b;
    v[a].push_back(b);
    g[b].push_back(a);
    if(in[a]>in[b]) upd_in(a,in[b]);
    if(out[a]>out[b]) upd_out(b,out[a]);
    if(a==b && a<k) ok=1;
    cout << ok << '\n';
  }
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}*/

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