Submission #1027794

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027794		edogawa_something	Dungeons Game (IOI21_dungeons)	C++17	26 / 100	224 ms	89084 KiB

dungeons

#include "dungeons.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vii;
typedef pair<ll,ll> pii;
#define F first 
#define S second 
#define pb push_back
#define all(v) v.begin(),v.end()
const ll M=4e5+10;
const ll inf=2e18;
vector<pair<pii,int>>inc[M];
ll awin[M];
ll N;
vector<int>lose;
void init(int n,vector<int>s,vector<int>p,vector<int>w,vector<int>l) {
	N=n;
	w.pb(n),l.pb(n);
	s.pb(0);
	for(auto it:l)
	lose.pb(it);
	for(int i=n-1;i>=0;i--){
		for(auto &it:inc[w[i]])
		inc[i].pb(it);
		for(auto &it:inc[i])
		it.F.F-=s[i],it.F.S+=s[i];
		while(inc[i].size()&&inc[i].back().F.F<=s[i])
		inc[i].pop_back();
		inc[i].pb({{s[i],0},i});
	}
	awin[n]=0;
	for(int i=n-1;i>=0;i--){
		awin[i]=awin[w[i]]+s[i];
	}
}

long long simulate(int x, int z){
	ll res=0;
	while(1){
		if(x==N)
		break;
		if(inc[x].front().F.F<=z+res){
			return res+awin[x]+z;
		}
		ll l=0,r=inc[x].size()-1,mid,ind;
		while(l<=r){
			mid=((l+r)>>1);
			if(inc[x][mid].F.F>z+res)
			l=mid+1,ind=mid;
			else
			r=mid-1;
		}
		res+=inc[x][ind].F.S;
		x=inc[x][ind].S;
		res+=inc[x].back().F.F;
		x=lose[x];
	}
	return res+z;
}

Compilation message (stderr)

dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:54:18: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
   54 |   res+=inc[x][ind].F.S;
      |                  ^

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