oj.uz

Submission #896280

# Submission time Handle Problem Language Result Execution time Memory
896280 2024-01-01T07:37:26 Z Muhammad_Aneeq Dungeons Game (IOI21_dungeons) C++17
0 / 100
 7000 ms 62796 KB 
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include "dungeons.h"
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];
			}
			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;
			}
				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;
}

Compilation message

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++)
      |                  ~^~~~~~~~~~~~
dungeons.cpp:37:6: warning: unused variable 'o' [-Wunused-variable]
   37 |  int o=0;
      |      ^

Subtask #1
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24924 KB Output is correct
2 Correct 4 ms 24924 KB Output is correct
3 Correct 5 ms 25136 KB Output is correct
4 Correct 30 ms 30752 KB Output is correct
5 Runtime error 24 ms 50776 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 25176 KB Output is correct
2 Execution timed out 7076 ms 62796 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24924 KB Output is correct
2 Incorrect 35 ms 30456 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24924 KB Output is correct
2 Incorrect 35 ms 30456 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24924 KB Output is correct
2 Incorrect 35 ms 30456 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 25176 KB Output is correct
2 Execution timed out 7076 ms 62796 KB Time limit exceeded
3 Halted 0 ms 0 KB -