Submission #495671

#	Time	Username	Problem	Language	Result	Execution time	Memory
495671		PedroBigMan	Dungeons Game (IOI21_dungeons)	C++17	37 / 100	7055 ms	464144 KiB

dungeons

/*
Author of all code: Pedro BIGMAN Dias
Last edit: 15/02/2021
*/
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
#include "dungeons.h"
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 500000000LL
#define EPS 0.00000001
#define pi 3.14159
#define VV(vvvv,NNNN,xxxx); REP(i,0,NNNN) {vvvv.pb(xxxx);}
ll mod=1000000007LL;

template<class A=ll> 
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}

template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}} 

ll n; vector<ll> s,pp,w,l; 

class Tree
{
    public:
    ll N; 
    vector<ll> p; 
    vector<vector<ll> > sons;
    vector<vector<ll> > adj;
    ll root;
	vector<ll> val; vector<ll> sumto;
	vector<vector<ll> > f; vector<vector<ll> > f2;
    
	Tree() {N=0;}
	
    Tree(vector<vector<ll> > ad, ll r=0LL)
    {
        N=ad.size(); root=r; adj=ad;
        vector<ll> xx; REP(i,0,N) {sons.pb(xx); p.pb(-1); sumto.pb(0);}
        DFS_Build(r,r); DFS_Sumto(root); REP(i,0,n) {val.pb(s[i]+sumto[i]);} val.pb(INF);
		VV(xx,log2(N)+1,0); VV(f,N,xx); VV(f2,N,xx); Conf2(0); Conf(0);
    }
    
    void DFS_Build(ll s, ll par)
    {
        p[s]=par;
        REP(i,0,adj[s].size())
        {
            if(adj[s][i]==par) {continue;}
            sons[s].pb(adj[s][i]);
            DFS_Build(adj[s][i],s);
        }
        return;
    }
	
	void DFS_Sumto(ll x)
	{
		if(x==n) {sumto[x]=0;}
		else {sumto[x]=sumto[p[x]]+s[x];}
		REP(i,0,sons[x].size()) {DFS_Sumto(sons[x][i]);}
	}
	
	void Conf2(ll e) //O(NlogN)
    {
        if((1LL<<e)>N) {return;}
        if(e==0) {REP(i,0,N) {f2[i][e]=p[i];} Conf2(e+1);}
        else 
        {
            REP(i,0,N) 
            {
                f2[i][e]=f2[f2[i][e-1]][e-1];
            }
        }
        Conf2(e+1);
    }

	void Conf(ll e) //O(NlogN)
    {
        if((1LL<<e)>N) {return;}
        if(e==0) {REP(i,0,n) {f[i][e]=val[i];} f[n][e]=INF;}
        else 
        {
            REP(i,0,N) 
            {
                f[i][e]=max(f[i][e-1],f[f2[i][e-1]][e-1]);
            }
        }
        Conf(e+1);
	}
	
	ll Stop(ll v, ll nnode)
	{
		
		ll node = nnode;
		ll e = log2(N);
		while(e>=0)
		{
			if(f[node][e]<=v) {node=f2[node][e];}
			e--;
		}
		return node;
	}
};

Tree T;

void init(int nn, vector<int> ss, vector<int> ppp, vector<int> ww, vector<int> lll) 
{
	n=(ll) nn; REP(i,0,n) {s.pb((ll) ss[i]); pp.pb((ll) ppp[i]); w.pb((ll) ww[i]); l.pb((ll) lll[i]);}
	vector<vector<ll> > adj; VV(adj,n+1,{}); 
	REP(i,0,n) {adj[i].pb(w[i]); adj[w[i]].pb(i);}
	Tree XX(adj,n); T=XX;
	return;
}

long long simulate(int x, int z) 
{
	while(1>0)
	{
		ll nxt = T.Stop(z+T.sumto[x],x);
		if(nxt==n) {return (z+T.sumto[x]);}
		z+=(T.sumto[x]-T.sumto[nxt]); z+=pp[nxt];
		x=l[nxt];
	}
}

Compilation message (stderr)

dungeons.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("O3")
      | 
dungeons.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("unroll-loops")
      |

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