Submission #891610

#	Time	Username	Problem	Language	Result	Execution time	Memory
891610		yellowtoad	Passport (JOI23_passport)	C++17	46 / 100	647 ms	104984 KiB

passport

#include <iostream>
#include <vector>
#include <queue>
#define f first
#define s second
using namespace std;

int n, node[800010], cnt, l, r, test, dist[2][400010], vis[400010], dp[400010], minn[400010];
vector<pair<int,pair<int,int>>> edge[400010];
vector<pair<int,int>> rev[400010];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;

void build(int id, int x, int y) {
	if (x == y) {
		node[id] = x;
		return;
	}
	int mid = (x+y)/2;
	build(id*2,x,mid);
	build(id*2+1,mid+1,y);
	node[id] = ++cnt;
	edge[node[id*2]].push_back({cnt,{0,0}});
	edge[node[id*2+1]].push_back({cnt,{0,0}});
}

void update(int id, int x, int y, int from) {
	if ((l <= x) && (y <= r)) {
		edge[node[id]].push_back({from,{1,r}});
		return;
	}
	if ((r < x) || (y < l)) return;
	int mid = (x+y)/2;
	update(id*2,x,mid,from);
	update(id*2+1,mid+1,y,from);
}

void dijk(int from, int id) {
	for (int i = 1; i <= cnt; i++) dist[id][i] = 1e9, vis[i] = 0;
	pq.push({0,from});
	dist[id][from] = 0;
	while (pq.size()) {
		int u = pq.top().s;
		pq.pop();
		if (vis[u]) continue;
		vis[u] = 1;
		for (int i = 0; i < edge[u].size(); i++) {
			if (dist[id][u]+edge[u][i].s.f < dist[id][edge[u][i].f]) {
				dist[id][edge[u][i].f] = dist[id][u]+edge[u][i].s.f;
				pq.push({dist[id][edge[u][i].f],edge[u][i].f});
			}
		}
	}
}

void dfs(int u) {
	vis[u] = 1;
	for (int i = 0; i < rev[u].size(); i++) {
		if (!vis[rev[u][i].f]) dfs(rev[u][i].f);
		dp[u] = max(dp[u],max(rev[u][i].s,dp[rev[u][i].f]));
	}
}

int main() {
	cin >> n;
	cnt = n;
	build(1,1,n);
	for (int i = 1; i <= n; i++) {
		cin >> l >> r;
		update(1,1,n,i);
	}
	dijk(1,0);
	dijk(n,1);
	for (int i = 1; i <= cnt; i++) for (int j = 0; j < edge[i].size(); j++) if (dist[0][i]+edge[i][j].s.f == dist[0][edge[i][j].f]) rev[edge[i][j].f].push_back({i,edge[i][j].s.s});
	for (int i = 1; i <= cnt; i++) vis[i] = 0;
	for (int i = 1; i <= n; i++) dp[i] = i;
	minn[0] = 1e9;
	for (int i = 1; i <= n; i++) minn[i] = min(minn[i-1],dist[1][i]);
	for (int i = 1; i <= cnt; i++) if (!vis[i]) dfs(i);
	/*for (int i = 1; i <= n; i++) cout << dp[i] << " ";
	cout << endl;*/
	cin >> test;
	while (test--) {
		int u;
		cin >> u;
		if (max(dist[0][u],minn[dp[u]]) == 1e9) cout << -1 << endl;
		else cout << dist[0][u]+minn[dp[u]] << endl;
	}
}
/*
6
1 1
2 3
3 4
1 4
4 6
6 6
6
1 2 3 4 5 6
*/

Compilation message (stderr)

passport.cpp: In function 'void dijk(int, int)':
passport.cpp:46:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |   for (int i = 0; i < edge[u].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~
passport.cpp: In function 'void dfs(int)':
passport.cpp:57:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |  for (int i = 0; i < rev[u].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
passport.cpp: In function 'int main()':
passport.cpp:73:51: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |  for (int i = 1; i <= cnt; i++) for (int j = 0; j < edge[i].size(); j++) if (dist[0][i]+edge[i][j].s.f == dist[0][edge[i][j].f]) rev[edge[i][j].f].push_back({i,edge[i][j].s.s});
      |                                                 ~~^~~~~~~~~~~~~~~~

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