Submission #896258

#	Time	Username	Problem	Language	Result	Execution time	Memory
896258		Muhammad_Aneeq	던전 (IOI21_dungeons)	C++17	0 / 100	7061 ms	62036 KiB

dungeons

#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include "dungeons.h"
using namespace std;
int const N=4e5+10;
int wi[N],lo[N],po[N],st[N];
int nn;
set<int>sr;
vector<int>nei[N]={};
long long head[N]={},cost[N]={},cost1[N]={};
int vis[N]={};
vector<vector<pair<int,long long>>>heads;
void dfs(int n)
{
	for (auto i:nei[n])
	{
		cost1[i]+=st[i];
		cost1[i]=cost1[n];
		dfs(i);
	}
}
void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l)
{
	nn=n;
	for (int i=0;i<n;i++)
	{
		wi[i]=w[i];
		lo[i]=l[i];
		st[i]=s[i];
		po[i]=p[i];
		nei[w[i]].push_back(i);
		head[i]=-1;
		sr.insert(s[i]);
	}
	dfs(n);
	for (int i=0;i<n;i++)
	{
		if (head[i]==-1)
		{
			int j=i;
			vector<int>temp;
			while (!vis[j])
			{
				temp.push_back(j);
				vis[j]=1;
				j=lo[j];
			}
			if (head[j]==-1)
			{
				int k;
				for (k=0;k<temp.size();k++)
					if (temp[k]==j)
						break;
				long long z=0;
				for (int l=k-1;l>=0;l--)
				{
					z+=po[temp[l]];
					cost[temp[l]]=z;
				}
				z=0;
				for (int l=temp.size();l>k;l--)
				{
					z+=po[temp[l]];
					cost[temp[l]]=z;
				}
				cost[j]=0;
				for (auto t:temp)
					head[t]=heads.size();
				reverse(begin(temp),end(temp));
				while (temp.back()!=j)
					temp.pop_back();
				vector<pair<int,long long>>pre(temp.size()+1);
				reverse(begin(temp),end(temp));
				pre[0]={temp[0],0};
				for (int k=1;k<temp.size();k++)
					pre[k]={temp[k],pre[k-1].second+po[temp[k-1]]};
				pre[temp.size()]={temp[0],pre[temp.size()-1].second+po[temp.back()]};
				heads.push_back(pre);
			}
			else
			{
				for (auto k:temp)
				{
					head[k]=head[j];
				}
				long long z=0;
				reverse(begin(temp),end(temp));
				for (auto k:temp)
				{
					z+=lo[k];
					cost[k]=z;
				}
			}
		}
	}
}
long long simulate(int i, int z)
{
	if (sr.size()==1)
	{
		long long f=*begin(sr);
		long long ans=z;
		if (ans+cost[i]>f)
		{
			while (ans<f)
			{
				ans+=po[i];
				i=lo[i];
			}
			ans+=cost1[i];
		}
		else
		{
			ans+=cost[i];
			int y=heads[head[i]].back().second;
			int r=(f-ans-1)/y;
			r=max(r,0);
			ans+=y*r;
			int st=-1,en=heads[head[i]].size()-1;
			r=f-ans;
			while (st+1<en)
			{
				int mid=(st+en)/2;
				if (heads[head[i]][mid].second>=r)
					en=mid;
				else
					st=mid;
			}
			ans+=heads[head[i]][en].second;
			ans+=cost1[heads[head[i]][en].first];
		}
		return ans;
	}
	long long ans=z;
	while (i!=nn)
	{
		if (z>=st[i])
		{
			z+=st[i];
			i=wi[i];
		}
		else
		{
			z+=po[i];
			i=lo[i];
		}
	}
	return z;
}

Compilation message (stderr)

dungeons.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:53:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for (k=0;k<temp.size();k++)
      |              ~^~~~~~~~~~~~
dungeons.cpp:77:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for (int k=1;k<temp.size();k++)
      |                  ~^~~~~~~~~~~~
dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:136:12: warning: unused variable 'ans' [-Wunused-variable]
  136 |  long long ans=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