oj.uz

Submission #891610

# Submission time Handle Problem Language Result Execution time Memory
891610 2023-12-23T10:40:31 Z yellowtoad Passport (JOI23_passport) C++17
46 / 100
 647 ms 104984 KB 
#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

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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 27224 KB Output is correct
2 Correct 5 ms 27228 KB Output is correct
3 Correct 5 ms 27228 KB Output is correct
4 Correct 647 ms 104984 KB Output is correct
5 Correct 314 ms 68264 KB Output is correct
6 Correct 197 ms 58964 KB Output is correct
7 Correct 190 ms 59496 KB Output is correct
8 Correct 165 ms 65916 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 27224 KB Output is correct
2 Correct 5 ms 27280 KB Output is correct
3 Correct 5 ms 27228 KB Output is correct
4 Correct 5 ms 27264 KB Output is correct
5 Correct 5 ms 27228 KB Output is correct
6 Correct 5 ms 27228 KB Output is correct
7 Correct 5 ms 27228 KB Output is correct
8 Correct 5 ms 27224 KB Output is correct
9 Correct 5 ms 27224 KB Output is correct
10 Correct 5 ms 27224 KB Output is correct
11 Correct 8 ms 27292 KB Output is correct
12 Correct 5 ms 27324 KB Output is correct
13 Correct 6 ms 27228 KB Output is correct
14 Correct 5 ms 27228 KB Output is correct
15 Correct 6 ms 27228 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 27224 KB Output is correct
2 Correct 5 ms 27280 KB Output is correct
3 Correct 5 ms 27228 KB Output is correct
4 Correct 5 ms 27264 KB Output is correct
5 Correct 5 ms 27228 KB Output is correct
6 Correct 5 ms 27228 KB Output is correct
7 Correct 5 ms 27228 KB Output is correct
8 Correct 5 ms 27224 KB Output is correct
9 Correct 5 ms 27224 KB Output is correct
10 Correct 5 ms 27224 KB Output is correct
11 Correct 8 ms 27292 KB Output is correct
12 Correct 5 ms 27324 KB Output is correct
13 Correct 6 ms 27228 KB Output is correct
14 Correct 5 ms 27228 KB Output is correct
15 Correct 6 ms 27228 KB Output is correct
16 Correct 9 ms 27736 KB Output is correct
17 Correct 8 ms 27740 KB Output is correct
18 Correct 9 ms 27996 KB Output is correct
19 Correct 8 ms 27996 KB Output is correct
20 Correct 7 ms 27508 KB Output is correct
21 Correct 7 ms 27484 KB Output is correct
22 Correct 7 ms 27484 KB Output is correct
23 Correct 8 ms 27740 KB Output is correct
24 Correct 8 ms 27740 KB Output is correct

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 27224 KB Output is correct
2 Correct 5 ms 27280 KB Output is correct
3 Correct 5 ms 27228 KB Output is correct
4 Correct 5 ms 27264 KB Output is correct
5 Correct 5 ms 27228 KB Output is correct
6 Correct 5 ms 27228 KB Output is correct
7 Correct 5 ms 27228 KB Output is correct
8 Correct 5 ms 27224 KB Output is correct
9 Correct 5 ms 27224 KB Output is correct
10 Correct 5 ms 27224 KB Output is correct
11 Correct 8 ms 27292 KB Output is correct
12 Correct 5 ms 27324 KB Output is correct
13 Correct 6 ms 27228 KB Output is correct
14 Correct 5 ms 27228 KB Output is correct
15 Correct 6 ms 27228 KB Output is correct
16 Correct 9 ms 27736 KB Output is correct
17 Correct 8 ms 27740 KB Output is correct
18 Correct 9 ms 27996 KB Output is correct
19 Correct 8 ms 27996 KB Output is correct
20 Correct 7 ms 27508 KB Output is correct
21 Correct 7 ms 27484 KB Output is correct
22 Correct 7 ms 27484 KB Output is correct
23 Correct 8 ms 27740 KB Output is correct
24 Correct 8 ms 27740 KB Output is correct
25 Correct 7 ms 27736 KB Output is correct
26 Correct 5 ms 27228 KB Output is correct
27 Incorrect 12 ms 27740 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 27224 KB Output is correct
2 Correct 5 ms 27228 KB Output is correct
3 Correct 5 ms 27228 KB Output is correct
4 Correct 647 ms 104984 KB Output is correct
5 Correct 314 ms 68264 KB Output is correct
6 Correct 197 ms 58964 KB Output is correct
7 Correct 190 ms 59496 KB Output is correct
8 Correct 165 ms 65916 KB Output is correct
9 Correct 5 ms 27224 KB Output is correct
10 Correct 5 ms 27280 KB Output is correct
11 Correct 5 ms 27228 KB Output is correct
12 Correct 5 ms 27264 KB Output is correct
13 Correct 5 ms 27228 KB Output is correct
14 Correct 5 ms 27228 KB Output is correct
15 Correct 5 ms 27228 KB Output is correct
16 Correct 5 ms 27224 KB Output is correct
17 Correct 5 ms 27224 KB Output is correct
18 Correct 5 ms 27224 KB Output is correct
19 Correct 8 ms 27292 KB Output is correct
20 Correct 5 ms 27324 KB Output is correct
21 Correct 6 ms 27228 KB Output is correct
22 Correct 5 ms 27228 KB Output is correct
23 Correct 6 ms 27228 KB Output is correct
24 Correct 9 ms 27736 KB Output is correct
25 Correct 8 ms 27740 KB Output is correct
26 Correct 9 ms 27996 KB Output is correct
27 Correct 8 ms 27996 KB Output is correct
28 Correct 7 ms 27508 KB Output is correct
29 Correct 7 ms 27484 KB Output is correct
30 Correct 7 ms 27484 KB Output is correct
31 Correct 8 ms 27740 KB Output is correct
32 Correct 8 ms 27740 KB Output is correct
33 Correct 7 ms 27736 KB Output is correct
34 Correct 5 ms 27228 KB Output is correct
35 Incorrect 12 ms 27740 KB Output isn't correct
36 Halted 0 ms 0 KB -