제출 #1232620

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1232620		LeonidCuk	던전 (IOI21_dungeons)	C++17	25 / 100	1188 ms	2162688 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int>w,l,s,p,v;
struct pom{
	long long nxt,sum;
};
vector<vector<vector<pom>>>lca;
void init(int N,vector<int> S,vector<int> P,vector<int> W,vector<int> L) {
	n=N;
	l=L;
	s=S;
	p=P;
	w=W;
	s.push_back(0);
	l.push_back(n);
	w.push_back(n);
	p.push_back(0);
	map<int,int>mp;
	for(int i=0;i<n;i++)
	{
		if(mp[s[i]]==0)
		{
			mp[s[i]]=1;
			v.push_back(s[i]);
		}
	}
	v.push_back(0);
	sort(v.begin(),v.end());
	lca.resize(v.size(),vector<vector<pom>>(n+1,vector<pom>(25)));
	for(int i1=0;i1<v.size();i1++)
	{
		long long k=v[i1];
		for(int j=0;j<25;j++)
		{
			for(int i=0;i<=n;i++)
			{
				if(j==0)
				{
					if(k>=s[i])
					{
						lca[i1][i][j].nxt=w[i];
						lca[i1][i][j].sum=s[i];
					}
					else
					{
						lca[i1][i][j].nxt=l[i];
						lca[i1][i][j].sum=p[i];
					}
				}
				else
				{
					int a=lca[i1][i][j-1].nxt;
					lca[i1][i][j].nxt=lca[i1][a][j-1].nxt;
					lca[i1][i][j].sum=lca[i1][i][j-1].sum+lca[i1][a][j-1].sum;
				}
			}
		}
	}
	return;
}

long long simulate(int x, int z) {
	long long sum=z;
	for(int i=0;i<v.size()-1;i++)
	{
		if(sum>=v[i+1])continue;
		for(int j=24;j>=0;j--)
		{
			if(sum+lca[i][x][j].sum<v[i+1])
			{
				sum+=lca[i][x][j].sum;
				x=lca[i][x][j].nxt;
			}
		}
		sum+=lca[i][x][0].sum;
		x=lca[i][x][0].nxt;
	}
	sum+=lca[v.size()-1][x][24].sum;
	return sum;
}

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