oj.uz

Submission #495671

# Submission time Handle Problem Language Result Execution time Memory
495671 2021-12-19T21:10:07 Z PedroBigMan Dungeons Game (IOI21_dungeons) C++17
37 / 100
 7000 ms 464144 KB 
/*
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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 4 ms 1996 KB Output is correct
4 Correct 98 ms 52096 KB Output is correct
5 Correct 4 ms 1996 KB Output is correct
6 Correct 96 ms 52108 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1100 KB Output is correct
2 Correct 957 ms 447528 KB Output is correct
3 Correct 913 ms 462600 KB Output is correct
4 Correct 925 ms 464144 KB Output is correct
5 Correct 1194 ms 446988 KB Output is correct
6 Correct 956 ms 454244 KB Output is correct
7 Correct 920 ms 460968 KB Output is correct

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1200 KB Output is correct
2 Correct 134 ms 54072 KB Output is correct
3 Correct 148 ms 55240 KB Output is correct
4 Correct 130 ms 55824 KB Output is correct
5 Correct 134 ms 54644 KB Output is correct
6 Execution timed out 7055 ms 53872 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1200 KB Output is correct
2 Correct 134 ms 54072 KB Output is correct
3 Correct 148 ms 55240 KB Output is correct
4 Correct 130 ms 55824 KB Output is correct
5 Correct 134 ms 54644 KB Output is correct
6 Execution timed out 7055 ms 53872 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1200 KB Output is correct
2 Correct 134 ms 54072 KB Output is correct
3 Correct 148 ms 55240 KB Output is correct
4 Correct 130 ms 55824 KB Output is correct
5 Correct 134 ms 54644 KB Output is correct
6 Execution timed out 7055 ms 53872 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1100 KB Output is correct
2 Correct 957 ms 447528 KB Output is correct
3 Correct 913 ms 462600 KB Output is correct
4 Correct 925 ms 464144 KB Output is correct
5 Correct 1194 ms 446988 KB Output is correct
6 Correct 956 ms 454244 KB Output is correct
7 Correct 920 ms 460968 KB Output is correct
8 Correct 2 ms 1200 KB Output is correct
9 Correct 134 ms 54072 KB Output is correct
10 Correct 148 ms 55240 KB Output is correct
11 Correct 130 ms 55824 KB Output is correct
12 Correct 134 ms 54644 KB Output is correct
13 Execution timed out 7055 ms 53872 KB Time limit exceeded
14 Halted 0 ms 0 KB -