Submission #535166

#	Time	Username	Problem	Language	Result	Execution time	Memory
535166		DanerZein	Dungeons Game (IOI21_dungeons)	C++17	13 / 100	91 ms	20912 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
typedef vector<ll> vi;
const int MAX_N=5e4+10;
vector<vii> Gl;
vector<vi> Gw;
int pa[MAX_N][32];
int tag[MAX_N];
ll dw[MAX_N],dl[MAX_N];
bool vis[MAX_N];
vector<vi> ci;
vector<vi> su;
vi tp;
int n,disp;
void distancia(int u){
  for(auto &v:Gw[u]){
    dw[v]=dw[u]+1;
    distancia(v);
  }
}
void topological(int u){
  vis[u]=1;
  for(auto &v:Gl[u]){
    if(!vis[v.first])
      topological(v.first);
  }
  tp.push_back(u);
}
int ciclo(int u){
  vis[u]=1;
  for(auto &v:Gl[u]){
    if(!vis[v.first]){
      int aux=ciclo(v.first);
      if(aux!=-1){
	ci[aux].push_back(u);
	return tag[u]=aux;
      }
    }
    else{
      int t=ci.size();
      ci.push_back(vi());
      ci[t].push_back(u);
      return tag[u]=t;
    }
  }
  return tag[u];
}
void spare(int u,int p){
  vis[u]=1;
  pa[u][0]=p;
  for(int i=1;i<=20;i++){
    pa[u][i]=pa[pa[u][i-1]][i-1];
  }
  for(auto &v:Gl[u]){
    if(!vis[v.first]){
      dl[v.first]=dl[u]+v.second;
      spare(v.first,u);
    }
  }
}
void init(int N, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
  n=N;
  disp=s[0];
  Gw.resize(n+1);
  Gl.resize(n+1);
  for(int i=0;i<N;i++){
    Gw[w[i]].push_back(i);
    Gl[l[i]].push_back(ii(i,p[i]));
  }
  dw[n]=0;
  distancia(n);
  memset(tag,-1,sizeof tag);
  for(int i=0;i<n;i++){
    if(!vis[i]) topological(i);
  }
  reverse(tp.begin(),tp.end());
  memset(vis,0,sizeof vis);
  for(int i=0;i<tp.size();i++){
    if(!vis[tp[i]]) ciclo(tp[i]);
  }
  memset(vis,0,sizeof vis);
  for(int i=0;i<ci.size();i++){
    dl[ci[i][0]]=0;
    spare(ci[i][0],ci[i][0]);
  }
  dl[N]=0;
  spare(N,N);
  for(int i=0;i<ci.size();i++){
    su.push_back(vi());
    su[i].push_back(0);
    for(int j=0;j<ci[i].size();j++){
      su[i].push_back(su[i][j]+p[ci[i][j]]);
    }
  }
}
int subir(int x,ll z){
  for(int i=20;i>=0;i--){
    ll d=dl[x]-dl[pa[x][i]];
    if(d+z<disp){
      z+=d;
      x=pa[x][i];
    }
  }
  return pa[x][0];
}
long long simulate(int x, int zi) {
  ll z=zi;
  int y=x;
  if(z<disp){
    y=subir(x,z);
    z+=dl[x]-dl[y];
    if(tag[y]!=-1 && ci[tag[y]][0]==y){
      vector<ll> &c=ci[tag[y]];
      vector<ll> &s=su[tag[y]];
      int ts=s.size()-1;
      ll ti=max((ll)0,(disp-z))/s[ts];
      z+=ti*s[ts];
      auto it=lower_bound(s.begin(),s.end(),disp-z);
      z+=(*it);
      int id=it-s.begin();
      id%=(c.size());
      y=c[id];
    }
  }
  z+=dw[y]*disp;
  return z;
}

Compilation message (stderr)

dungeons.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:82:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |   for(int i=0;i<tp.size();i++){
      |               ~^~~~~~~~~~
dungeons.cpp:86:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |   for(int i=0;i<ci.size();i++){
      |               ~^~~~~~~~~~
dungeons.cpp:92:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |   for(int i=0;i<ci.size();i++){
      |               ~^~~~~~~~~~
dungeons.cpp:95:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for(int j=0;j<ci[i].size();j++){
      |                 ~^~~~~~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 26
• Subtask 3: 13 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 27
• Subtask 6: 0 / 11