Submission #749905

#	Time	Username	Problem	Language	Result	Execution time	Memory
749905		Cyber_Wolf	Passport (JOI23_passport)	C++17	100 / 100	1068 ms	159308 KiB

passport

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")

using namespace std;

#define lg long long
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

const lg N = 1e6+5;

vector<array<lg, 2>> adj[N];
lg dis[2][N], dist[N], id, n, in_queue[N];

void propagate(lg node, lg lr, lg hr, lg idx, lg lq, lg hq)
{
	if(lq > hr || lr > hq)	return;
	if(lq <= lr && hr <= hq)
	{
		adj[node].push_back({idx, 0});
		return;
	}
	lg mid = (lr+hr)/2;
	propagate(node << 1, lr, mid, idx, lq, hq);
	propagate(node << 1 | 1, mid+1, hr, idx, lq, hq);
	return;
}

void dijkstra(lg t, lg src)
{
	memset(dis[t], 0x3f, sizeof(dis[t]));
	dis[t][src] = 0;
	priority_queue<array<lg, 2>> pq;
	pq.push({0, src});
	in_queue[src] = true;
	while(pq.size())
	{
		lg u = pq.top()[1];
		in_queue[u] = false;
		pq.pop();
		for(auto [it, c] : adj[u])
		{
			if(dis[t][it] > dis[t][u]+c)
			{
				dis[t][it] = dis[t][u]+c;
				if(in_queue[it])	continue;
				pq.push({-dis[t][it], it});
				in_queue[it] = true;
			}
		}
	}
	return;
}

int main()
{
	fastio;
	cin >> n;
	lg sn = 1;
	while(sn < n)	sn *= 2;
	id = sn*2+1;
	for(int i = 1; i <= n; i++)
	{
		lg x, y;
		cin >> x >> y;
		id++;
		adj[id].push_back({i-1+sn, 1});
		propagate(1, 1, sn, id, x, y);
	}
	for(int i = 1; i < sn; i++)
	{
		adj[i*2].push_back({i, 0});
		adj[i*2+1].push_back({i, 0});
	}
	// for(int i = 1; i <= id; i++)
	// {
		// for(auto [it, c] : adj[i])
		// {
			// cout << i << " " << it << ' ' << c << '\n';
		// }
	// }
	dijkstra(0, sn);
	dijkstra(1, sn+n-1);
	priority_queue<array<lg, 2>> pq;
	for(int i = 1; i <= id; i++)	dist[i] += dis[0][i]+dis[1][i];
	for(int i = 1; i <= id; i++)	
	{
		if(dist[i] > 1e9)	continue;
		pq.push({-dist[i], i}), in_queue[i] = 1;
	}
	while(pq.size())
	{
		lg u = pq.top()[1];
		in_queue[u] = false;
		pq.pop();
		for(auto [it, c] : adj[u])
		{
			if(dist[it] > dist[u]+c)
			{
				dist[it] = dist[u]+c;
				if(in_queue[it])	continue;
				pq.push({-dist[it], it});
				in_queue[it] = true;
			}
		}
	}
	lg q;
	cin >> q;
	while(q--)
	{
		lg node;
		cin >> node;
		if(dist[node+sn-1] > 1e9)	dist[node+sn-1] = -1;
		cout << dist[node+sn-1] << '\n';
	}

    return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 8 / 8
• Subtask 5: 46 / 46