Submission #1216231

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216231		dosts	던전 (IOI21_dungeons)	C++20	0 / 100	7094 ms	17568 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];
std::vector<signed> s,p,w,l;
vi go(N,0);
int n;
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 = W,s = S,p = P,l = 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 = 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]]-s[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]-s[i]-go[i]});
			}
		}
		fearsome[i].push_back({n,-1});
		assert(big(fearsome[i]) <= 30);
	}
}

int simulate(signed x, signed z) {
	while (z < s[x]) {
		//cerr << "LOSE" sp x sp z << '\n';
		z += p[x];
		x = l[x];
	}
	while (1) {
		int until = x;
		for (auto it : fearsome[x]) {
			//cerr << "FEAR" sp it.ff sp it.ss << '\n';
			if (z < it.ss) break;
			//cerr << "BEATEN\n";
			until = it.ff;
		}
		z+=go[x]-go[until];
		if (until == n) break;
		x = until;
		while (z < s[w[x]]) {
			//cerr << "LOSE" sp x sp z << '\n';
			z += p[w[x]];
			x = l[w[x]];
		}
	}
	return z;
}

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