Submission #443435

#	Time	Username	Problem	Language	Result	Execution time	Memory
443435		mario05092929	Dungeons Game (IOI21_dungeons)	C++17	37 / 100	7024 ms	163908 KiB

dungeons

#include "dungeons.h"
#define pb push_back
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector <int> vec;
int n;
int s[400005],p[400005];
int win[400005],lose[400005];
int sp[400005][20];
ll co[400005][20],d[400005];
vec v[400005];

void dfs(int x) {
    for(int i : v[x]) {
        d[i] = d[x]+s[i];
        sp[i][0] = x;
        co[i][0] = d[i]+s[i];
        dfs(i);
    }
}

void init(int N,vec S,vec P,vec Win,vec Lose) {
    n = N;
    for(int i = 0;i < n;i++) {
        s[i] = S[i], p[i] = P[i];
    }
    for(int i = 0;i < n;i++) {
        win[i] = Win[i], lose[i] = Lose[i];
        v[win[i]].pb(i);
    }
    dfs(n);
    sp[n][0] = n;
    co[n][0] = d[n]+s[n];
    for(int i = 1;i < 20;i++) {
        for(int j = 0;j <= n;j++) {
            sp[j][i] = sp[sp[j][i-1]][i-1];
            co[j][i] = max(co[j][i-1],co[sp[j][i-1]][i-1]);
        }
    }
}

ll simulate(int x,int z) {
	ll he = z;
	for(;1;) {
        int wi = x;
        for(int i = 19;i >= 0;i--) {
            if(d[x]+he >= co[wi][i]) wi = sp[wi][i];
        }
        if(wi == n) {
            he += d[x];
            break;
        }
        he = d[x]-d[wi]+he+p[wi];
        x = lose[wi];
	}
	return he;
}

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