Submission #735164

#	Time	Username	Problem	Language	Result	Execution time	Memory
735164		arnold518	Passport (JOI23_passport)	C++17	48 / 100	2102 ms	666036 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 = 2e5;

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

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

void bfs(int *D)
{
	queue<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({V[p].second, V[p].first}); p++;
		while(!Q.empty())
		{
			pii t=Q.front(); Q.pop();
			if(D[t.first]!=t.second) continue;

			int now=t.first;
			for(; p<V.size() && V[p].first<=D[now]+1; p++) Q.push({V[p].second, V[p].first});
			for(auto nxt : adj[now])
			{
				if(D[nxt]!=0 && D[nxt]<=D[now]+1) continue;
				D[nxt]=D[now]+1;
				Q.push({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);

	for(int i=1; i<=N; i++)
	{
		auto [l, r]=A[i];
		for(int j=l; j<=r; j++) adj[j].push_back(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 'void bfs(int*)':
passport.cpp:22: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]
   22 |  for(int p=0; p<V.size();)
      |               ~^~~~~~~~~
passport.cpp:31: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]
   31 |    for(; p<V.size() && V[p].first<=D[now]+1; p++) Q.push({V[p].second, V[p].first});
      |          ~^~~~~~~~~
passport.cpp: In function 'int main()':
passport.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
passport.cpp:46:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |  for(int i=1; i<=N; i++) scanf("%d%d", &A[i].first, &A[i].second);
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
passport.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |  scanf("%d", &Q);
      |  ~~~~~^~~~~~~~~~
passport.cpp:67:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |   scanf("%d", &t);
      |   ~~~~~^~~~~~~~~~

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