제출 #497275

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
497275		DanerZein	Dungeons Game (IOI21_dungeons)	C++17	0 / 100	2 ms	972 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N=5e4+10;
vector<ll> pw,pl,Gw,Gl;
int nd;
map<int,int> m,m1;
bool ci[MAX_N];
int in[MAX_N];
ll sum[MAX_N];
int en[MAX_N],sta[MAX_N];
int dis[MAX_N];
int no=0;
ll sc;
vector<ll> cis; 
int ciclo(int u){
  if(ci[u]) return u;
  ci[u]=1;
  return ciclo(Gl[u]);
}
int dfs(int x,int p,int s,bool sw){
  if(ci[x]!=sw || m[x]!=-1) return m[p];
  m[x]=no; m1[no]=x; no++;
  int u=m[x];
  sum[u]=sum[m[p]]+pl[x];
  sta[u]=m[s];
  return en[u]=dfs(Gl[x],x,s,sw);
}
int distan(int u){
  if(u==nd) return 0;
  int x=m[u];
  if(dis[x]!=-1) return dis[x];
  return dis[x]=distan(Gw[u])+1;
}
void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
  memset(in,0,sizeof in);
  memset(ci,0,sizeof ci);
  memset(dis,-1,sizeof dis);
  nd=n;
  sc=s[0];
  dis[n]=0;
  for(int i=0;i<n;i++){
    m[i]=-1;
    pw.push_back(s[i]);
    pl.push_back(p[i]);
    Gw.push_back(w[i]);
    Gl.push_back(l[i]);
    in[l[i]]++;
  }
  int cu=ciclo(0);
  memset(ci,0,sizeof ci);
  ciclo(cu);
  
  for(int i=0;i<n;i++){
    if(in[i]==0){
        dfs(i,i,i,ci[i]);
    }
  }
  for(int i=0;i<n;i++){
    if(ci[i]) dfs(i,i,i,ci[i]);
  }
  for(int i=0;i<n;i++){
    if(dis[m[i]]==-1) {
      distan(i);
    }
  }
  // for(auto &v:m) cout<<v.first<<": "<<v.second<<endl;
}
int binary(int l,int r,ll z,ll a){  
  //  int l=u,r=en[u]+1;
  ll d;
  while(r-l>1){
    int mid=(l+r)/2;
    d=sum[mid]-a;
    if(z+d>=sc) r=mid;
    else l=mid;
  }
  d=sum[l]-a;
  if(z+d>=sc) r=l;
  return r;
}

long long simulate(int x, int zr) {
  int u=m[x];
  ll a=0;
  ll z=zr;
  if(u!=sta[u])
    a=sum[u-1];
  ll d=sum[en[u]]-a;
  if(z+d>=sc){
    u=binary(u,en[u]+1,z,a);
    z+=sum[u]-a;
  }
  else{
    z+=d;
    //u=m[Gw[en[u]]];
    ll vu=(sc-z)/sum[en[u]];
    z+=vu*sum[en[u]];
    
    if(u==sta[u]) a=0;
    else a=sum[u-1];
    if(z+sum[en[u]]-a>=sc){
      u=binary(u,en[u]+1,z,a);
      z+=sum[u]-a;
    }
    else{
      z+=sum[en[u]]-a;
      u=binary(sta[u],u,z,a);
      z+=sum[u];
    }
  }
  u=m[Gl[m1[u]]];
  z+=sc*dis[u];
  return z;
}

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