oj.uz

Submission #1103898

# Submission time Handle Problem Language Result Execution time Memory
1103898 2024-10-22T07:16:44 Z epicci23 Game (APIO22_game) C++17
2 / 100
 5 ms 19792 KB 
#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;
const int BL = 600;
vector<int> v[N],g[N];
bool vis[N],vis2[N];
int n,m,k,out[N],in[N],bin[N],bout[N];
bool ok=0;

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

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

void upd_bin(int a,int val,int real){
  if(bin[a]<=val || ok) return;
  bin[a]=val;
  
  if(bin[a]<bout[a] || in[a]<out[a]){
    ok=1;
    return;
  }
  if(in[a]==out[a] && a>=k){
  	ok=1;
    return;
  }
  if(bin[a]==bout[a] && !vis[a]){
  	vis[a]=vis2[a]=1;
    for(int u=BL*bin[a];u<min(k,BL*(bin[a]+1));u++) 
      upd_out(u,out[u]);
    for(int u=BL*bin[a];u<min(k,BL*(bin[a]+1));u++) 
      upd_in(u,in[u]);
  }
  else upd_in(a,in[a]);
  
  for(int x:g[a]){
  	if(bin[x]>val) upd_bin(x,val,in[a]);
  	else if(bin[x]==val) upd_in(x,in[a]);
  }
}

void upd_bout(int a,int val,int real){
  if(bout[a]>=val || ok) return;
  bout[a]=val;
  if(bin[a]<bout[a] || in[a]<out[a]){
    ok=1;
    return;
  }
  if(in[a]==out[a] && a>=k){
  	ok=1;
    return;
  }
  if(bin[a]==bout[a] && !vis2[a]){
  	vis[a]=vis2[a]=1;
    for(int u=BL*bout[a];u<min(k,BL*(bout[a]+1));u++) 
      upd_out(u,out[u]);
    for(int u=BL*bout[a];u<min(k,BL*(bout[a]+1));u++) 
      upd_in(u,in[u]);
  }
  else upd_out(a,out[a]);
  for(int x:v[a]){
  	if(bout[x]<val) upd_bout(x,val,out[a]);
  	else if(bout[x]==val) upd_out(x,out[a]);
  }
}

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

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

/*void _(){
  cin >> n >> m >> k;
  init(n,k);
  for(int i=1;i<=m;i++){
  	int a,b;
  	cin >> a >> b;
  	cout << add_teleporter(a,b) << '\n';
  }
}

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

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19792 KB Output is correct
2 Correct 4 ms 19792 KB Output is correct
3 Correct 5 ms 19792 KB Output is correct
4 Correct 5 ms 19792 KB Output is correct
5 Correct 5 ms 19792 KB Output is correct
6 Correct 4 ms 19792 KB Output is correct
7 Correct 5 ms 19792 KB Output is correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19792 KB Output is correct
2 Correct 4 ms 19792 KB Output is correct
3 Correct 5 ms 19792 KB Output is correct
4 Correct 5 ms 19792 KB Output is correct
5 Correct 5 ms 19792 KB Output is correct
6 Correct 4 ms 19792 KB Output is correct
7 Correct 5 ms 19792 KB Output is correct
8 Correct 5 ms 19792 KB Output is correct
9 Correct 4 ms 19792 KB Output is correct
10 Incorrect 4 ms 19792 KB Wrong Answer[1]
11 Halted 0 ms 0 KB -

Subtask #3
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19792 KB Output is correct
2 Correct 4 ms 19792 KB Output is correct
3 Correct 5 ms 19792 KB Output is correct
4 Correct 5 ms 19792 KB Output is correct
5 Correct 5 ms 19792 KB Output is correct
6 Correct 4 ms 19792 KB Output is correct
7 Correct 5 ms 19792 KB Output is correct
8 Correct 5 ms 19792 KB Output is correct
9 Correct 4 ms 19792 KB Output is correct
10 Incorrect 4 ms 19792 KB Wrong Answer[1]
11 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19792 KB Output is correct
2 Correct 4 ms 19792 KB Output is correct
3 Correct 5 ms 19792 KB Output is correct
4 Correct 5 ms 19792 KB Output is correct
5 Correct 5 ms 19792 KB Output is correct
6 Correct 4 ms 19792 KB Output is correct
7 Correct 5 ms 19792 KB Output is correct
8 Correct 5 ms 19792 KB Output is correct
9 Correct 4 ms 19792 KB Output is correct
10 Incorrect 4 ms 19792 KB Wrong Answer[1]
11 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19792 KB Output is correct
2 Correct 4 ms 19792 KB Output is correct
3 Correct 5 ms 19792 KB Output is correct
4 Correct 5 ms 19792 KB Output is correct
5 Correct 5 ms 19792 KB Output is correct
6 Correct 4 ms 19792 KB Output is correct
7 Correct 5 ms 19792 KB Output is correct
8 Correct 5 ms 19792 KB Output is correct
9 Correct 4 ms 19792 KB Output is correct
10 Incorrect 4 ms 19792 KB Wrong Answer[1]
11 Halted 0 ms 0 KB -