Submission #438503

#	Time	Username	Problem	Language	Result	Execution time	Memory
438503		PiejanVDC	Dungeons Game (IOI21_dungeons)	C++17	0 / 100	1014 ms	7212 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;

int nnn,sss;

vector<int>ppp,lll;
vector<long long>winning_path;
vector<vector<int>>adj;
void gen(void);
void init(int nn, vector<int> ss, vector<int> pp, vector<int> ww, vector<int> ll) {
    nnn=nn;
    sss=ss[0],ppp=pp,lll=ll;
    adj.resize(nnn+1);
    for(int i = 0 ; i < nnn ; i++) {
        adj[ww[i]].push_back(i);
    }
    winning_path.resize(nnn+1);
    winning_path[nnn]=0;
    queue<int>q;
    q.push(nnn);
    long long cnt=0;
    while(!q.empty()) {
        int sz = q.size();
        while(sz--) {
            int node = q.front();
            q.pop();
            winning_path[node]=cnt;
            for(auto z : adj[node]) q.push(z);
        }
        cnt++;
    }
}

long long simulate(int x, int zz) {
    vector<long long>v(nnn+1,0);
    vector<int> seq;
    long long curr=0, len=0;
    long long z=zz;
    while(true) {
        if(v[x]) {
            z+=((sss-z)/(curr-v[x]))*(curr-v[x]);
            int left=0, right=seq.size()-1, use=x;
            while(left <= right) {
                int mid = (left+right)/2;
                if(z+(v[seq[mid]]-v[x]) >= sss) {
                use=mid;
                right=mid-1;
                } else {
                    left=mid+1;
                }
            }
            if(use>0&&use<seq.size()){
                z+=v[seq[use]] - v[x];
                x=seq[use];
            }
            return z+sss*winning_path[x];
        }
        if(x==nnn) return z;
        if(z >= sss) return z+sss*winning_path[x];
        v[x]=curr;
        curr+=ppp[x],z+=ppp[x];
        seq.push_back(x);
        x=lll[x];
        len++;
    }
}

Compilation message (stderr)

dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:53:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |             if(use>0&&use<seq.size()){
      |                       ~~~^~~~~~~~~~~

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