oj.uz

Submission #1069544

# Submission time Handle Problem Language Result Execution time Memory
1069544 2024-08-22T05:18:56 Z 김은성(#11131) Passport (JOI23_passport) C++17
0 / 100
 1893 ms 1048576 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(l==r){
		zero[idx].push_back(v);
		return;
	}
	//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:63:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
passport.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |   scanf("%d %d", &l, &r);
      |   ~~~~~^~~~~~~~~~~~~~~~~
passport.cpp:69:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
passport.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |   scanf("%d", &x);
      |   ~~~~~^~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 53596 KB Output is correct
2 Correct 22 ms 53596 KB Output is correct
3 Correct 22 ms 53592 KB Output is correct
4 Runtime error 1893 ms 1048576 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 53596 KB Output is correct
2 Correct 19 ms 53592 KB Output is correct
3 Correct 23 ms 53728 KB Output is correct
4 Correct 23 ms 53592 KB Output is correct
5 Correct 22 ms 53584 KB Output is correct
6 Correct 20 ms 53756 KB Output is correct
7 Incorrect 23 ms 53592 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 53596 KB Output is correct
2 Correct 19 ms 53592 KB Output is correct
3 Correct 23 ms 53728 KB Output is correct
4 Correct 23 ms 53592 KB Output is correct
5 Correct 22 ms 53584 KB Output is correct
6 Correct 20 ms 53756 KB Output is correct
7 Incorrect 23 ms 53592 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 53596 KB Output is correct
2 Correct 19 ms 53592 KB Output is correct
3 Correct 23 ms 53728 KB Output is correct
4 Correct 23 ms 53592 KB Output is correct
5 Correct 22 ms 53584 KB Output is correct
6 Correct 20 ms 53756 KB Output is correct
7 Incorrect 23 ms 53592 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 53596 KB Output is correct
2 Correct 22 ms 53596 KB Output is correct
3 Correct 22 ms 53592 KB Output is correct
4 Runtime error 1893 ms 1048576 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -