제출 #603181

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
603181		2fat2code	던전 (IOI21_dungeons)	C++17	26 / 100	410 ms	112808 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 int long long
#define rc(s) return cout << s, 0
using namespace std;

const int nmax = 400005;

int N;
pair<pair<int,int>,int> lca[nmax][19];
vector<int>L_cringe;

void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
    N = n;
    for(auto &it : w) ++it;
    for(auto &it : l) ++it;
    L_cringe = l;
	for(int i=1;i<=n;i++){
        lca[i][0].fr.fr = s[i - 1];
        lca[i][0].fr.sc = -s[i - 1];
        lca[i][0].sc = w[i - 1];
	}
	for(int j=1;j<=18;j++){
        for(int i=1;i<=n;i++){
            lca[i][j].sc = lca[lca[i][j-1].sc][j-1].sc;
            lca[i][j].fr.fr = lca[i][j-1].fr.fr + lca[lca[i][j-1].sc][j-1].fr.fr;
            lca[i][j].fr.sc = min(lca[i][j-1].fr.sc, lca[i][j-1].fr.fr + lca[lca[i][j-1].sc][j-1].fr.sc);
        }
	}
    return;
}

long long simulate(int x, int z) {
	int curr = z;
	++x;
	while(x != N + 1){
        for(int j=18;j>=0;j--){
            if(lca[x][j].sc != 0 && lca[x][j].fr.sc + curr >= 0){
                curr += lca[x][j].fr.fr;
                x = lca[x][j].sc;
            }
        }
        if(x != N + 1){
            curr += lca[x][0].fr.fr;
            x = L_cringe[x - 1];
        }
	}
	return curr;
}

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