Submission #735187

#	Time	Username	Problem	Language	Result	Execution time	Memory
735187		arnold518	Passport (JOI23_passport)	C++17	100 / 100	514 ms	62324 KiB

passport

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e6;

int N, Q;
pii A[MAXN+10];
vector<int> adj[MAXN+10];

int init(int node, int tl, int tr)
{
	if(tl==tr) return tl;
	int mid=tl+tr>>1;
	adj[init(node*2, tl, mid)].push_back(node+N);
	adj[init(node*2+1, mid+1, tr)].push_back(node+N);
	return node+N;
}

void query(int node, int tl, int tr, int l, int r, int k)
{
	if(r<tl || tr<l) return;
	if(l<=tl && tr<=r)
	{
		if(tl==tr) adj[tl].push_back(k);
		else adj[node+N].push_back(k);
		return;
	}
	int mid=tl+tr>>1;
	query(node*2, tl, mid, l, r, k);
	query(node*2+1, mid+1, tr, l, r, k);
}

int D1[MAXN+10], D2[MAXN+10], D3[MAXN+10];

void bfs(int *D)
{
	deque<pii> Q;
	vector<pii> V;
	for(int i=1; i<=N; i++) if(D[i]) V.push_back({D[i], i});
	sort(V.begin(), V.end());
	for(int p=0; p<V.size();)
	{
		Q.push_back({V[p].second, V[p].first}); p++;
		while(!Q.empty())
		{
			pii t=Q.front(); Q.pop_front();
			if(D[t.first]!=t.second) continue;

			int now=t.first;
			for(; p<V.size() && V[p].first<=D[now]+1; p++) Q.push_back({V[p].second, V[p].first});
			for(auto nxt : adj[now])
			{
				if(D[nxt]!=0 && D[nxt]<=D[now]+1) continue;
				if(nxt<=N)
				{
					D[nxt]=D[now]+1;
					Q.push_back({nxt, D[nxt]});
				}
				else
				{
					D[nxt]=D[now];
					Q.push_front({nxt, D[nxt]});					
				}
			}
		}
	}
	for(int i=1; i<=N; i++) if(!D[i]) D[i]=N+N;
}

int main()
{
	scanf("%d", &N);
	for(int i=1; i<=N; i++) scanf("%d%d", &A[i].first, &A[i].second);

	init(1, 1, N);
	for(int i=1; i<=N; i++)
	{
		auto [l, r]=A[i];
		query(1, 1, N, l, r, i);
	}

	for(int i=1; i<=N; i++) if(A[i].first==1) D1[i]=1;
	bfs(D1);
	
	for(int i=1; i<=N; i++) if(A[i].second==N) D2[i]=1;
	bfs(D2);
	
	for(int i=1; i<=N; i++) D3[i]=D1[i]+D2[i]-1;
	bfs(D3);

	scanf("%d", &Q);
	while(Q--)
	{
		int t;
		scanf("%d", &t);
		if(D3[t]>N) D3[t]=-1;
		printf("%d\n", D3[t]);
	}
}

Compilation message (stderr)

passport.cpp: In function 'int init(int, int, int)':
passport.cpp:17:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   17 |  int mid=tl+tr>>1;
      |          ~~^~~
passport.cpp: In function 'void query(int, int, int, int, int, int)':
passport.cpp:32:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |  int mid=tl+tr>>1;
      |          ~~^~~
passport.cpp: In function 'void bfs(int*)':
passport.cpp:45:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |  for(int p=0; p<V.size();)
      |               ~^~~~~~~~~
passport.cpp:54:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |    for(; p<V.size() && V[p].first<=D[now]+1; p++) Q.push_back({V[p].second, V[p].first});
      |          ~^~~~~~~~~
passport.cpp: In function 'int main()':
passport.cpp:76:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
passport.cpp:77:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |  for(int i=1; i<=N; i++) scanf("%d%d", &A[i].first, &A[i].second);
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
passport.cpp:95:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |  scanf("%d", &Q);
      |  ~~~~~^~~~~~~~~~
passport.cpp:99:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |   scanf("%d", &t);
      |   ~~~~~^~~~~~~~~~

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