제출 #1216252

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1216252		dosts	던전 (IOI21_dungeons)	C++20	37 / 100	471 ms	265320 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 1e6+1, inf = 2e9;
    //a node'unda kazanıyorsam ama b'nodeunda kaybediyosam s[a]*2 < s[b] olmalı
    //fonksiyonel graf şeklinde kaybedicem
    //ilk kez kazanınca nerde olcağımı ve gücümü hesaplamak casework ile O(1)
	//binary lifting?
	//z+l[node]+l[w[node]]... >= s[w[w[...node]]]
    //kaç kez kaybedebilirim?
    //s[i]/p[i]+1 kez olabilir l[i] = i ise
    //kaybettiğim bir adamı yenersem gücüm iki katıma çıkar
    //sürekli ilk kaybedeceğim yeri bulayım (25 candidate var)
    //fonksiyonal grafa göre ordan ilk kazanacağım yeri bulayım 
    //Q*R*(25+log(N))
    //repeat
    //51+11? puan alır
    //13 because ilk kez kazanınca kaybetmicem
    //12 because 5 kez kazanınca kaybetmicem
    //26 because her durumda 2 katına çıkıyorum

    //Bir yerde z güçle ne zaman kaybedicem
    //first t s.t z+p[node][t] < go[node][t]-s[node][t]
    //herkes için 
const int N = 400001;
vector<pii> fearsome[N];
vi s,p,w,l;
vi go(N,0);
int n;

int jump[N][20],lsum[N][20],f[N][20];
void init(signed nn, std::vector<signed> S, std::vector<signed> P, std::vector<signed> W, std::vector<signed> L) {
	//bi sonrakini yenemiyosam bi sonraki + onunkiler (s[i]*2 < s[nxt])
	//yeniyosam alıp onunkilerden poplicam
	w = vi(all(W)),s = vi(all(S)),p = vi(all(P)),l = vi(all(L));
	n = nn;
	s.push_back(0);
	p.push_back(0);
	w.push_back(n);
	l.push_back(n);
	for (int i = n;i>=0;i--) go[i] = go[w[i]]+s[i];
	//s[i]+(s[i]+s[w[i]]+s[w[w[i]]]...) < s[t]
	//s[i]+go[i]-go[t] < s[t] --> s[i]+go[i] < s[t]+go[t]
	for (int i = 0;i<=n;i++) jump[i][0] = l[i],lsum[i][0] = p[i],f[i][0] = s[i];
	for (int i=1;i<20;i++) {
		for (int j = 0;j<=n;j++) {
			jump[j][i] = jump[jump[j][i-1]][i-1];
			lsum[j][i] = lsum[j][i-1]+lsum[jump[j][i-1]][i-1];
			f[j][i] = min(f[j][i-1],f[jump[j][i-1]][i-1]-lsum[j][i-1]);
		}
	}
	for (int i = n-1;i>=0;i--) {
		if (s[i]+go[i] < s[w[i]]+go[w[i]]) fearsome[i].push_back({w[i],s[w[i]]+go[w[i]]-go[i]});
		for (auto it : fearsome[w[i]]) {
			if (go[it.ff]+s[it.ff] > s[i]+go[i]) {
				fearsome[i].push_back({it.ff,s[it.ff]+go[it.ff]-go[i]});
			}
		}
		fearsome[i].push_back({n,-1});
		assert(big(fearsome[i]) <= 30);
	}
}

int simulate(signed x, signed rz) {
	int z = rz;
	if (s[x] > z) {
		for (int i = 19;i>=0;i--) {
			if (f[x][i] <= z) continue;
			z+=lsum[x][i];
			x = jump[x][i];
		}
	}
	while (1) {
		int until = -1;
		for (auto it : fearsome[x]) {
			if (z < it.ss) {
				until = it.ff;
				break;
			}
		}
		if (until == -1) {
			z+=go[x];
			break;
		}
		z+=go[x]-go[until];
		x = until;
		//f[node][i] --> node'dan itibaren 2^i hamle içinde kazanmak için minimum initial z
		//f[node][i] = min(f[node][i-1],f[go[node][i]][i-1]-lsum[node][i])
		//f[node][0] = s[node]
		//lsum[node][0] = s[node], usual lift
		if (s[x] > z) {
			for (int i = 19;i>=0;i--) {
				if (f[x][i] <= z) continue;
				z+=lsum[x][i];
				x = jump[x][i];
			}
		}
	}
	return z;
}

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