Submission #1308179

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308179		thuhienne	Passport (JOI23_passport)	C++20	0 / 100	6 ms	572 KiB

passport

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define thuhien ""
#define re exit(0);

const int inf = 1e9;
const int maxn = 200009;

int n;
pair <int,int> segment[maxn];

int d1[5 * maxn],d2[5 * maxn],d3[5 * maxn];

vector <pair <int,int>> adj[5 * maxn];

void addedge(int u,int v,int w) {
	adj[u].push_back({v,w});
// 	adj[v].push_back({u,w});
}

void init(int id,int l,int r) {
	if (l == r) {
		addedge(l,id + n,0);
		return;
	}
	int mid = (l + r) >> 1;
	
	addedge(id*2 + n,id + n,0);
	addedge(id*2+1 + n,id + n,0);
	
	init(id*2,l,mid);
	init(id*2+1,mid+1,r);
	
}
void addedge(int id,int l,int r,int u,int v,int ver) {
	if (l > v || r < u) return;
	if (l >= u && r <= v) {
		addedge(id + n,ver,1);
		return;
	}
	
	int mid = (l + r) >> 1;
	
	addedge(id*2,l,mid,u,v,ver);
	addedge(id*2+1,mid+1,r,u,v,ver);
}

vector <int> q[maxn];

void bfs(int l[]) {
	for (int i = 0;i <= n + 3;i++) q[i].clear();
	for (int i = 1;i <= n;i++) if (l[i] <= n) q[l[i]].push_back(i);
	
	for (int i = 0;i <= n + 3;i++) {
		while (q[i].size()) {
			int ver = q[i].back();q[i].pop_back();
			if (l[ver] < i) continue;
			
			for (pair <int,int> x : adj[ver]) {
				if (l[x.first] > l[ver] + x.second) {
					l[x.first] = l[ver] + x.second;
					q[l[x.first]].push_back(x.first);
				}
			}
			
		}
	}
}

int main() {
//  ios_base::sync_with_stdio(0);
//  cin.tie(nullptr);
	if (fopen(thuhien".inp","r")) {
	   freopen(thuhien".inp","r",stdin);
	   freopen(thuhien".out","w",stdout);
	}
	
	cin >> n;
	
	for (int i = 1;i <= 5 * n;i++) d1[i] = d2[i] = inf;
	
	for (int i = 1;i <= n;i++) {
		cin >> segment[i].first >> segment[i].second;
		
		if (segment[i].first == 1) d1[i] = 1;
		if (segment[i].second == n) d2[i] = 1;
		
	}
	
	init(1,1,n);
	
	for (int i = 1;i <= n;i++) {
// 		addedge(1,1,n,segment[i].first,segment[i].second,i);
        for (int j = segment[i].first;j <= segment[i].second;j++) {
            addedge(j,i,1);
        }
	}
	
	bfs(d1);
	bfs(d2);
	
// 	for (int i = 1;i <= n;i++) cout << d1[i] << " " << d2[i] << '\n';
// 	re;
	
	for (int i = 1;i <= n;i++) d3[i] = d1[i] + d2[i] - 1;
	
	bfs(d3);
// 	for (int i = 1;i <= n;i++) cout << d3[i] << '\n';
// 	re;
	
	int q;cin >> q;while (q--) {
		int a;cin >> a;
		cout << d3[a] << '\n';
	}
}

Compilation message (stderr)

passport.cpp: In function 'int main()':
passport.cpp:77:19: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |            freopen(thuhien".inp","r",stdin);
      |            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
passport.cpp:78:19: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |            freopen(thuhien".out","w",stdout);
      |            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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