Submission #437897

#	Time	Username	Problem	Language	Result	Execution time	Memory
437897		WnRS	Dungeons Game (IOI21_dungeons)	C++17	0 / 100	59 ms	14080 KiB

dungeons

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

int nnn;
vector<int>sss,ppp,www,lll;
vector<int>winning_path;
vector<int>adj[400001];
void gen(void);
void init(int nn, vector<int> ss, vector<int> pp, vector<int> ww, vector<int> ll) {
    nnn=nn;
    sss=ss,ppp=pp,www=ww,lll=ll;
    for(int i = 0 ; i < nnn ; i++) {
        adj[www[i]].push_back(i);
    }
    gen();
}

void gen(void) {
    vector<bool>vis(nnn+1,false);
    winning_path.resize(nnn+1);
    winning_path[nnn]=0;
    queue<int>q;
    q.push(nnn);
    int cnt=0;
    while(!q.empty()) {
        int sz = q.size();
        while(sz--) {
            int node = q.front();
            q.pop();
            vis[node]=true;
            winning_path[node]=cnt;
            for(auto z : adj[node]) {
                if(!vis[z]) {
                    q.push(z);
                }
            }
        }
        cnt++;
    }
}

long long simulate(int x, int zz) {
    long long z=zz;
    while(true) {
        if(z >= sss[x]) {
            return (long long)(z+sss[x]*winning_path[x]);
        }
        z+=ppp[x];
        x=lll[x];
    }
}
/*
//#include "dungeons.h"
#include <vector>
#include <cassert>
#include <cstdio>
// BEGIN SECRET
#include <string>
// END SECRET

static int n, q;
static std::vector<int> s, p, z;
static std::vector<int> w, l, x;
static std::vector<long long> answer;

int main() {
    // BEGIN SECRET
    const std::string input_secret = "b50747e9-747c-4fca-b3b0-62317b32d2f6";
    const std::string output_secret = "f39eb8f7-7d10-4b4a-af02-d7aef3d4dd0a";
    char secret[1000];
    assert(1 == scanf("%s", secret));
    if (std::string(secret) != input_secret) {
        printf("%s\n", output_secret.c_str());
        printf("PV\n");
        printf("Possible tampering with the input\n");
        fclose(stdout);
        return 0;
    }
    // END SECRET
	assert(scanf("%d %d", &n, &q) == 2);
	s.resize(n);
	p.resize(n);
	w.resize(n);
	l.resize(n);
    x.resize(q);
    z.resize(q);
    answer.resize(q);

	for (int i = 0; i < n; i++) {
		assert(scanf("%d", &s[i]) == 1);
	}
	for (int i = 0; i < n; i++) {
		assert(scanf("%d", &p[i]) == 1);
	}
	for (int i = 0; i < n; i++) {
		assert(scanf("%d", &w[i]) == 1);
	}
	for (int i = 0; i < n; i++) {
		assert(scanf("%d", &l[i]) == 1);
	}


    init(n, s, p, w, l);

    for (int i = 0; i < q; i++) {
		assert(scanf("%d %d", &x[i], &z[i]) == 2);
		answer[i] = simulate(x[i], z[i]);
    }
    fclose(stdin);

    // BEGIN SECRET
    printf("%s\n", output_secret.c_str());
    printf("OK\n");
    // END SECRET
    for (int i = 0; i < q; i++) {
        printf("%lld\n", answer[i]);
    }
    fclose(stdout);
    return 0;
}
*/

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