oj.uz

Submission #1069540

# Submission time Handle Problem Language Result Execution time Memory
1069540 2024-08-22T05:15:22 Z 김은성(#11131) Passport (JOI23_passport) C++17
6 / 100
 190 ms 89632 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200009, ADD = 1<<19, SEGSZ = ADD*2;
vector<int> zero[SEGSZ], one[SEGSZ];
int idxin[MAXN], idxout[MAXN];
int dist[SEGSZ];
void settree(int v, int l, int r){
	if(l==r){
		idxin[l] = v;
		idxout[l] = v + ADD;
		one[idxin[l]].push_back(idxout[l]);
	}
	else{
		int mid = (l+r)/2;
		zero[v].push_back(2*v);
		zero[v].push_back(2*v+1);
		settree(2*v, l, mid);
		settree(2*v+1, mid+1, r);
	}
}
void updateedge(int v, int l, int r, int idx, int s, int e){
	if(e<l || r<s)
		return;
	if(s<=l && r<=e){
		zero[idx].push_back(v);
	}
	else{
		int mid = (l+r)/2;
		updateedge(2*v, l, mid, idx, s, e);
		updateedge(2*v+1, mid+1, r, idx, s, e);
	}
}
void bfs(int v){
	memset(dist, 127, sizeof(dist));
	deque<pair<int, int> > q;
	q.push_back(make_pair(v, 0));
	dist[v] = 0;
	while(!q.empty()){
		v = q.front().first;
		//printf("v=%d\n", v);
		if(dist[v] != q.front().second){
			q.pop_front();
			continue;
		}
		q.pop_front();
		for(int u: zero[v]){
			if(dist[v] < dist[u]){
				dist[u] = dist[v];
				q.push_front(make_pair(u, dist[u]));
			}
		}
		for(int u: one[v]){
			if(dist[v]+1 < dist[u]){
				dist[u] = dist[v] + 1;
				q.push_back(make_pair(u, dist[u]));
			}
		}
	}
}
int main(){
	int n, q, i, l, r, x;
	scanf("%d", &n);
	settree(1, 1, n);
	for(i=1; i<=n; i++){
		scanf("%d %d", &l, &r);
		updateedge(1, 1, n, idxout[i], l, r);
	}
	scanf("%d", &q);
	while(q--){
		scanf("%d", &x);
		bfs(idxin[x]);
		int ans = 0;
		for(i=1; i<=n; i++)
			ans = max(ans, dist[idxin[i]]);
		if(ans>n)
			ans = -1;
		printf("%d\n", ans);
	}
	return 0;
}

Compilation message

passport.cpp: In function 'int main()':
passport.cpp:62:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
passport.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |   scanf("%d %d", &l, &r);
      |   ~~~~~^~~~~~~~~~~~~~~~~
passport.cpp:68:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
passport.cpp:70:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |   scanf("%d", &x);
      |   ~~~~~^~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 53592 KB Output is correct
2 Correct 19 ms 53596 KB Output is correct
3 Correct 18 ms 53772 KB Output is correct
4 Correct 190 ms 89632 KB Output is correct
5 Correct 133 ms 77388 KB Output is correct
6 Correct 104 ms 76636 KB Output is correct
7 Correct 81 ms 76880 KB Output is correct
8 Correct 94 ms 75600 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 53596 KB Output is correct
2 Correct 22 ms 53596 KB Output is correct
3 Correct 21 ms 53596 KB Output is correct
4 Correct 21 ms 53596 KB Output is correct
5 Correct 24 ms 53596 KB Output is correct
6 Correct 19 ms 53808 KB Output is correct
7 Incorrect 22 ms 53596 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 53596 KB Output is correct
2 Correct 22 ms 53596 KB Output is correct
3 Correct 21 ms 53596 KB Output is correct
4 Correct 21 ms 53596 KB Output is correct
5 Correct 24 ms 53596 KB Output is correct
6 Correct 19 ms 53808 KB Output is correct
7 Incorrect 22 ms 53596 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 53596 KB Output is correct
2 Correct 22 ms 53596 KB Output is correct
3 Correct 21 ms 53596 KB Output is correct
4 Correct 21 ms 53596 KB Output is correct
5 Correct 24 ms 53596 KB Output is correct
6 Correct 19 ms 53808 KB Output is correct
7 Incorrect 22 ms 53596 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 53592 KB Output is correct
2 Correct 19 ms 53596 KB Output is correct
3 Correct 18 ms 53772 KB Output is correct
4 Correct 190 ms 89632 KB Output is correct
5 Correct 133 ms 77388 KB Output is correct
6 Correct 104 ms 76636 KB Output is correct
7 Correct 81 ms 76880 KB Output is correct
8 Correct 94 ms 75600 KB Output is correct
9 Correct 18 ms 53596 KB Output is correct
10 Correct 22 ms 53596 KB Output is correct
11 Correct 21 ms 53596 KB Output is correct
12 Correct 21 ms 53596 KB Output is correct
13 Correct 24 ms 53596 KB Output is correct
14 Correct 19 ms 53808 KB Output is correct
15 Incorrect 22 ms 53596 KB Output isn't correct
16 Halted 0 ms 0 KB -