제출 #1216236

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1216236		dosts	던전 (IOI21_dungeons)	C++20	0 / 100	7095 ms	12864 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;
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 = 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 rz) {
	int z = rz;
	while (z < s[x]) {
		//cerr << "LOSE" sp x sp z << '\n';
		z += p[x];
		x = l[x];
	}
	while (1) {
		while (z >= s[x]) {
			z+=s[x];
			x = w[x];
		}
		if (x == n) break;
		while (z < s[x]) {
			//cerr << "LOSE" sp x sp z << '\n';
			z += p[x];
			x = l[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