oj.uz

Submission #896295

# Submission time Handle Problem Language Result Execution time Memory
896295 2024-01-01T07:53:24 Z Muhammad_Aneeq Dungeons Game (IOI21_dungeons) C++17
11 / 100
 138 ms 43048 KB 
#include <vector>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
int const N=5e4+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,long long val=0)
{
	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]);
	}
	if (sr.size()==1)
	{
		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+=po[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-1)/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:55:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |      for (k=0;k<temp.size();k++)
      |               ~^~~~~~~~~~~~
dungeons.cpp:81:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |      for (int l=1;l<temp.size();l++)
      |                   ~^~~~~~~~~~~~
dungeons.cpp:39:7: warning: unused variable 'o' [-Wunused-variable]
   39 |   int o=0;
      |       ^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2404 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 27 ms 7308 KB Output is correct
5 Correct 2 ms 2652 KB Output is correct
6 Correct 24 ms 7228 KB Output is correct

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Runtime error 138 ms 43048 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2648 KB Output is correct
2 Correct 39 ms 9348 KB Output is correct
3 Correct 35 ms 11392 KB Output is correct
4 Correct 34 ms 11864 KB Output is correct
5 Correct 32 ms 10524 KB Output is correct
6 Incorrect 36 ms 8832 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2648 KB Output is correct
2 Correct 39 ms 9348 KB Output is correct
3 Correct 35 ms 11392 KB Output is correct
4 Correct 34 ms 11864 KB Output is correct
5 Correct 32 ms 10524 KB Output is correct
6 Incorrect 36 ms 8832 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2648 KB Output is correct
2 Correct 39 ms 9348 KB Output is correct
3 Correct 35 ms 11392 KB Output is correct
4 Correct 34 ms 11864 KB Output is correct
5 Correct 32 ms 10524 KB Output is correct
6 Incorrect 36 ms 8832 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Runtime error 138 ms 43048 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -