Submission #534785

#	Time	Username	Problem	Language	Result	Execution time	Memory
534785		DanerZein	Dungeons Game (IOI21_dungeons)	C++17	0 / 100	2 ms	844 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;
int n,disp;
void distancia(int u){
  for(auto &v:Gw[u]){
    dw[v]=dw[u]+1;
    distancia(v);
  }
}
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(v.first);
	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]) ciclo(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]);
  }
  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,int z){
  for(int i=20;i>=0;i--){
    int 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 z) {
  int y=subir(x,z);
  z+=dl[x]-dl[y];
  if(y==n) return z;
  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=(disp-z)/s[ts];
    z+=ti*s[ts];
    auto it=lower_bound(s.begin(),s.end(),disp-z);
    int id=it-s.begin();
    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:72: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]
   72 |   for(int i=0;i<ci.size();i++){
      |               ~^~~~~~~~~~
dungeons.cpp:77: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]
   77 |   for(int i=0;i<ci.size();i++){
      |               ~^~~~~~~~~~
dungeons.cpp:80:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for(int j=0;j<ci[i].size();j++){
      |                 ~^~~~~~~~~~~~~

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