Submission #837580

#	Time	Username	Problem	Language	Result	Execution time	Memory
837580		ma_moutahid	Dungeons Game (IOI21_dungeons)	C++17	0 / 100	2 ms	852 KiB

dungeons

#include "dungeons.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
#define vi vector<int>
using ll=long long;
#define vl vector<long long>
#define vii vector<vi>
#define vll vector<vl>
#define pl pair<ll,ll>
ll INF=1e9;
vl s;
vl p;
vl w;
vl l;
ll n;
ll ss;
vii wg;
vl prize_win;
void win_dfs(int node,  ll cum){
	prize_win[node]=cum;
	for(auto child:wg[node]){
		win_dfs(child,cum+ss);
	}
}
vector<vector<pair<ll,ll>>> dp;
void init(int N, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L) {
	
	n=N;
	wg.resize(n+1);
	s.resize(n);
	w.resize(n);
	p.resize(n);
	l.resize(n);
	ss=s[0];
	prize_win.resize(n+1);
	for(int i=0;i<n;i++){
		wg[w[i]].push_back(i);
		s[i]=S[i];
		p[i]=P[i];
		w[i]=W[i];
		l[i]=L[i];
	}
	win_dfs(n,0ll);
	dp.resize(30,vector<pl>(n));
	for(int i=0;i<n;i++){
		dp[0][i]=pl(p[i],l[i]);
	}
	ll val=1;
	for(int pow=1;pow<30;pow++){
		for(int i=0;i<n;i++){
			auto o=dp[pow-1][i];
			dp[pow][i]=pl(min(o.first+dp[pow-1][o.second].first,INF),dp[pow-1][o.second].second);
		}
	}
	return;
}

ll solve(ll x, ll z, int pow){
	if(z>=ss)return z+prize_win[x];
	if(pow==0){
		return z+dp[0][z].first+prize_win[dp[0][z].second];
	}
	if(dp[pow-1][x].first+z<ss)return solve(dp[pow-1][x].first,dp[pow-1][x].second +z, pow);
	else {
		return solve(x,z,pow-1);
	}
}

long long simulate(int X, int Z) {
	return solve(X,Z, 29);
}

Compilation message (stderr)

dungeons.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:49:5: warning: unused variable 'val' [-Wunused-variable]
   49 |  ll val=1;
      |     ^~~

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