제출 #896277

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
896277		Muhammad_Aneeq	던전 (IOI21_dungeons)	C++17	0 / 100	7091 ms	66504 KiB

dungeons

#include <vector>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
int const N=4e5+10;
long long 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,int val=0)
{
	cost1[n]=val*st[0];
	for (auto i:nei[n])
	{
		dfs(i,val+1);
	}
}
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);
	int o=0;
	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];
			}
			o+=(j==i);
			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[temp[k]]=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 l=1;l<temp.size();l++)
					pre[l]={temp[l],pre[l-1].second+po[temp[l-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=cost[j];
				reverse(begin(temp),end(temp));
				for (auto k:temp)
				{
					z+=lo[k];
					cost[k]=z;
				}
			}
		}
	}
}
bool yu=0;
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];
			long long y=heads[head[i]].back().second;
			long long r=(f-ans)/y;
			r=max(r,0LL);
			ans+=y*r;
			int st=-1,en=heads[head[i]].size();
			r=f-ans;
			while (st+1<en)
			{
				int mid=(st+en)/2;
				if (heads[head[i]][mid].second>=r)
					en=mid;
				else
					st=mid;
			}
			if (yu==0)
			{
				ans+=heads[head[i]][en].second;
				ans+=cost1[heads[head[i]][en].first];
			}
			yu=1;
		}
		return ans;
	}
	long long ans=z;
	while (i!=nn)
	{
		if (ans>=st[i])
		{
			ans+=st[i];
			i=wi[i];
		}
		else
		{
			ans+=po[i];
			i=lo[i];
		}
	}
	return ans;
}

컴파일 시 표준 에러 (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:79:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for (int l=1;l<temp.size();l++)
      |                  ~^~~~~~~~~~~~

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