oj.uz

Submission #896245

# Submission time Handle Problem Language Result Execution time Memory
896245 2024-01-01T05:13:53 Z Muhammad_Aneeq Dungeons Game (IOI21_dungeons) C++17
11 / 100
 7000 ms 111740 KB 
#include <vector>
#include <set>
#include <map>
#include <algorithm>
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]={};
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);
	}
	dfs(n);
	map<int,int>vis;
	for (int i=0;i<n;i++)
	{
		if (!vis[i])
		{
			int j=i;
			vector<int>temp;
			while (!vis[j])
			{
				vis[j]=1;
				temp.push_back(j);
			}
			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 i:temp)
				head[i]=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 i=1;i<temp.size();i++)
				pre[i]={temp[i],pre[i-1].second+po[temp[i-1]]};
			pre[temp.size()]={temp[0],pre[temp.size()-1].second+po[temp.back()]};
			heads.push_back(pre);
		}
	}
}
long long simulate(int i, int z)
{
	if (sr.size()==1)
	{
		long long f=*begin(sr);
		long long ans=z;
		if (z+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

dungeons.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:47:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |    for (k=0;k<temp.size();k++)
      |             ~^~~~~~~~~~~~
dungeons.cpp:71:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |    for (int i=1;i<temp.size();i++)
      |                 ~^~~~~~~~~~~~
dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:115:12: warning: unused variable 'ans' [-Wunused-variable]
  115 |  long long ans=z;
      |            ^~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 18780 KB Output is correct
2 Correct 4 ms 18780 KB Output is correct
3 Correct 4 ms 19036 KB Output is correct
4 Correct 43 ms 28388 KB Output is correct
5 Correct 6 ms 19152 KB Output is correct
6 Correct 52 ms 28196 KB Output is correct

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19036 KB Output is correct
2 Execution timed out 7078 ms 111740 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19032 KB Output is correct
2 Correct 58 ms 29596 KB Output is correct
3 Execution timed out 7020 ms 31244 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19032 KB Output is correct
2 Correct 58 ms 29596 KB Output is correct
3 Execution timed out 7020 ms 31244 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19032 KB Output is correct
2 Correct 58 ms 29596 KB Output is correct
3 Execution timed out 7020 ms 31244 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19036 KB Output is correct
2 Execution timed out 7078 ms 111740 KB Time limit exceeded
3 Halted 0 ms 0 KB -