Submission #912142

#	Time	Username	Problem	Language	Result	Execution time	Memory
912142		yellowtoad	Passport (JOI23_passport)	C++17	100 / 100	1363 ms	135704 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], dpp[400010], minnn[400010];
vector<pair<pair<int,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;
	dpp[cnt] = x;
	dp[cnt] = y;
	edge[node[id*2]].push_back({{cnt,0},{1e9,0}});
	edge[node[id*2+1]].push_back({{cnt,0},{1e9,0}});
}

void update(int id, int x, int y, int from) {
	if ((l <= x) && (y <= r)) {
		edge[node[id]].push_back({{from,1},{l,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].f.s < dist[id][edge[u][i].f.f]) {
				dist[id][edge[u][i].f.f] = dist[id][u]+edge[u][i].f.s;
				pq.push({dist[id][edge[u][i].f.f],edge[u][i].f.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]));
	}
}

void dfss(int u) {
	vis[u] = 1;
	for (int i = 0; i < rev[u].size(); i++) {
		if (!vis[rev[u][i].f]) dfss(rev[u][i].f);
		dpp[u] = min(dpp[u],min(rev[u][i].s,dpp[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].f.s == dist[0][edge[i][j].f.f]) rev[edge[i][j].f.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 <= cnt; i++) rev[i].clear();
	for (int i = 1; i <= cnt; i++) for (int j = 0; j < edge[i].size(); j++) if (dist[1][i]+edge[i][j].f.s == dist[1][edge[i][j].f.f]) rev[edge[i][j].f.f].push_back({i,edge[i][j].s.f});
	for (int i = 1; i <= cnt; i++) vis[i] = 0;
	for (int i = 1; i <= n; i++) dpp[i] = i;
	minnn[n+1] = 1e9;
	for (int i = n; i >= 1; i--) minnn[i] = min(minnn[i+1],dist[0][i]);
	for (int i = 1; i <= cnt; i++) if (!vis[i]) dfss(i);
	/*for (int i = 1; i <= n; i++) cout << dpp[i] << " ";
	cout << endl;*/
	cin >> test;
	while (test--) {
		int u;
		cin >> u;
		if (min(max(dist[0][u],minn[dp[u]]),max(dist[1][u],minnn[dpp[u]])) == 1e9) cout << -1 << endl;
		else cout << min(dist[0][u]+minn[dp[u]],dist[1][u]+minnn[dpp[u]]) << endl;
	}
}
/*
7
1 1
2 4
1 3
4 6
1 5
1 7
7 7
7
1 2 3 4 5 6 7
*/

Compilation message (stderr)

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

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