Submission #441323

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
441323	2021-07-05 00:05:30	Dormi	Dungeons Game (IOI21_dungeons)	C++17	63 / 100	1820 ms	2097156 KiB

dungeons

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "bits/stdc++.h"
#include "dungeons.h"
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
int sz(const T &a){return int(a.size());}
const int MN=4e5+1,B=3;
vector<vector<pair<int,pll>>> lift[16];//minimum to get to the lifted node and win against any >=pc[i]
int pc[16],n,win[MN],lose[MN],strength[MN],lgain[MN];
void init(int N, vector<int> s, vector<int> p, vector<int> w, vector<int> l){
    n=N;
    pc[0]=1;
    win[n]=n,lose[n]=n,strength[n]=0,lgain[n]=0;
    for(int i=0;i<n;i++)win[i]=w[i],lose[i]=l[i],strength[i]=s[i],lgain[i]=p[i];
    for(int i=0;i<=15;i++){
        if(i)pc[i]=pc[i-1]*B;
        lift[i].resize(__lg(max(0,int(1e7)-pc[i])+n)+1,vector<pair<int,pll>>(n+1));
        lift[i][0][n]={n,{0,LLONG_MAX}};
        for(int j=0;j<n;j++){
            if(s[j]>=pc[i])lift[i][0][j]={l[j],{p[j],s[j]}};
            else lift[i][0][j]={w[j],{s[j],LLONG_MAX}};
        }
        for(int j=1;j<sz(lift[i]);j++){
            for(int k=0;k<=n;k++){
                lift[i][j][k].first=lift[i][j-1][lift[i][j-1][k].first].first;
                lift[i][j][k].second.first=lift[i][j-1][k].second.first+lift[i][j-1][lift[i][j-1][k].first].second.first;
                lift[i][j][k].second.second=min(lift[i][j-1][k].second.second,lift[i][j-1][lift[i][j-1][k].first].second.second-lift[i][j-1][k].second.first);
            }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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