제출 #604224

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
604224		2fat2code	던전 (IOI21_dungeons)	C++17	11 / 100	1555 ms	1233880 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
#define fr first
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define sc second
#define all(s) s.begin(), s.end()
#define rc(s) return cout << s, 0
using namespace std;

const int nmax = 50005;

int N;
pair<pair<long long, long long>,long long>lca[nmax][24][25];
vector<int>S, W;

void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
    for(auto &it : w) ++it;
    for(auto &it : l) ++it;
    S = s; W = w;
    N = n;
    for(int j=0;j<=24;j++){
        for(int i=1;i<=n;i++){
            if(s[i - 1] < (1 << j)){
                lca[i][0][j].sc = w[i - 1];
                lca[i][0][j].fr.fr = s[i - 1];
                lca[i][0][j].fr.sc = 0;
            }
            else{
                lca[i][0][j].sc = l[i - 1];
                lca[i][0][j].fr.fr = p[i - 1];
                lca[i][0][j].fr.sc = -s[i - 1];
            }
        }
    }
    for(int k=1;k<=23;k++){
        for(int j=0;j<=24;j++){
            for(int i=1;i<=n;i++){
                lca[i][k][j].sc = lca[lca[i][k-1][j].sc][k-1][j].sc;
                lca[i][k][j].fr.fr = lca[i][k-1][j].fr.fr + lca[lca[i][k-1][j].sc][k-1][j].fr.fr;
                lca[i][k][j].fr.sc = max(lca[i][k-1][j].fr.sc, lca[i][k-1][j].fr.fr + lca[lca[i][k-1][j].sc][k-1][j].fr.sc);
            }
        }
    }
}

long long simulate(int x, int z) {
    int pos_curr = x + 1;
    long long putere_curr = z;
    int i = 0;
    while(pos_curr != N + 1){
        if(i == 26) assert(1 == 0);
        for(int j=23;j>=0;j--){
            if(lca[pos_curr][j][i].sc != 0 && lca[pos_curr][j][i].fr.sc + putere_curr < 0LL){
                putere_curr += lca[pos_curr][j][i].fr.fr;
                pos_curr = lca[pos_curr][j][i].sc;
            }
        }
        if(pos_curr == N + 1) break;
        else{
            putere_curr += (long long)S[pos_curr - 1];
            pos_curr = W[pos_curr - 1];
            ++i;
        }
    }
    return putere_curr;
}

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