oj.uz

Submission #995021

# Submission time Handle Problem Language Result Execution time Memory
995021 2024-06-08T10:42:52 Z edogawa_something Passport (JOI23_passport) C++17
40 / 100
 1052 ms 1048576 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vii;
typedef pair<ll,ll> pii;
#define F first 
#define S second 
#define all(v) v.begin(),v.end()
#define pb push_back
#define pow poww
const int M=1e6+10;
const ll mod=998244353;
const ll inf=2e18;
ll pow(ll x,ll y){
  ll res=1;
  x%=mod;
  while(y>0){
    if(y%2==1){
      res*=x,res%=mod;  
    }
    x*=x,x%=mod;
    y/=2;
  }
  return res;
}
ll n,dis[M],diss[M],ans[M];
bool vis[M];
vii adj[M];
void bfs(ll x){
  queue<ll>q;
  for(int i=1;i<=n;i++)
  vis[i]=0,dis[i]=inf;
  vis[x]=1;
  dis[x]=0;
  q.push(x);
  while(!q.empty()){
    ll y=q.front();
    q.pop();
    for(auto it:adj[y]){
      if(!vis[it])
      q.push(it),vis[it]=1,dis[it]=dis[y]+1;
    }
  }
}
int main(){
  ios_base::sync_with_stdio(0),cin.tie(0);
  ll TC=1;
  //cin>>TC;
  while(TC--){
    cin>>n;
    for(int i=1;i<=n;i++){
      ll x,y;
      cin>>x>>y;
      for(int j=x;j<=y;j++){
        if(j==i)
        continue;
        adj[j].pb(i);
      }
    }
    bfs(1);
    for(int i=1;i<=n;i++)
    swap(dis[i],diss[i]);
    bfs(n);
    for(int i=1;i<=n;i++)
    dis[i]+=diss[i];
    priority_queue<pii,vector<pii>,greater<pii>>q;
    for(int i=1;i<=n;i++)
    ans[i]=inf;
    for(int i=1;i<=n;i++){
    if(i!=1&&i!=n)
    q.push({dis[i]-1,i});
    else
    q.push({dis[i],i});
    }
    for(int i=1;i<=n;i++)
    vis[i]=0;
    while(!q.empty()){
      pii p=q.top();
      q.pop();
      if(vis[p.S])
      continue;
      vis[p.S]=1;
      ans[p.S]=p.F;
      for(auto it:adj[p.S]){
        q.push({p.F+1,it});
      }
    }
    ll querycnt;
    cin>>querycnt;
    while(querycnt--){
      ll x;
      cin>>x;
      if(ans[x]==inf)
      ans[x]=-1;
      cout<<ans[x]<<'\n';
    }
  }
  return 0;
}
/*

*/

Subtask #1
0 / 6.0

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

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 27228 KB Output is correct
2 Correct 5 ms 27228 KB Output is correct
3 Correct 5 ms 27228 KB Output is correct
4 Correct 4 ms 27228 KB Output is correct
5 Correct 4 ms 27228 KB Output is correct
6 Correct 4 ms 27276 KB Output is correct
7 Correct 4 ms 27308 KB Output is correct
8 Correct 4 ms 27228 KB Output is correct
9 Correct 4 ms 27224 KB Output is correct
10 Correct 4 ms 27248 KB Output is correct
11 Correct 6 ms 27996 KB Output is correct
12 Correct 5 ms 27228 KB Output is correct
13 Correct 8 ms 28376 KB Output is correct
14 Correct 8 ms 28380 KB Output is correct
15 Correct 5 ms 27228 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 27228 KB Output is correct
2 Correct 5 ms 27228 KB Output is correct
3 Correct 5 ms 27228 KB Output is correct
4 Correct 4 ms 27228 KB Output is correct
5 Correct 4 ms 27228 KB Output is correct
6 Correct 4 ms 27276 KB Output is correct
7 Correct 4 ms 27308 KB Output is correct
8 Correct 4 ms 27228 KB Output is correct
9 Correct 4 ms 27224 KB Output is correct
10 Correct 4 ms 27248 KB Output is correct
11 Correct 6 ms 27996 KB Output is correct
12 Correct 5 ms 27228 KB Output is correct
13 Correct 8 ms 28376 KB Output is correct
14 Correct 8 ms 28380 KB Output is correct
15 Correct 5 ms 27228 KB Output is correct
16 Correct 217 ms 60856 KB Output is correct
17 Correct 8 ms 27996 KB Output is correct
18 Correct 393 ms 77476 KB Output is correct
19 Correct 410 ms 75984 KB Output is correct
20 Correct 6 ms 27484 KB Output is correct
21 Correct 33 ms 32180 KB Output is correct
22 Correct 667 ms 131072 KB Output is correct
23 Correct 409 ms 88756 KB Output is correct
24 Correct 382 ms 88268 KB Output is correct

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 27228 KB Output is correct
2 Correct 5 ms 27228 KB Output is correct
3 Correct 5 ms 27228 KB Output is correct
4 Correct 4 ms 27228 KB Output is correct
5 Correct 4 ms 27228 KB Output is correct
6 Correct 4 ms 27276 KB Output is correct
7 Correct 4 ms 27308 KB Output is correct
8 Correct 4 ms 27228 KB Output is correct
9 Correct 4 ms 27224 KB Output is correct
10 Correct 4 ms 27248 KB Output is correct
11 Correct 6 ms 27996 KB Output is correct
12 Correct 5 ms 27228 KB Output is correct
13 Correct 8 ms 28376 KB Output is correct
14 Correct 8 ms 28380 KB Output is correct
15 Correct 5 ms 27228 KB Output is correct
16 Correct 217 ms 60856 KB Output is correct
17 Correct 8 ms 27996 KB Output is correct
18 Correct 393 ms 77476 KB Output is correct
19 Correct 410 ms 75984 KB Output is correct
20 Correct 6 ms 27484 KB Output is correct
21 Correct 33 ms 32180 KB Output is correct
22 Correct 667 ms 131072 KB Output is correct
23 Correct 409 ms 88756 KB Output is correct
24 Correct 382 ms 88268 KB Output is correct
25 Correct 4 ms 27224 KB Output is correct
26 Correct 4 ms 27228 KB Output is correct
27 Incorrect 239 ms 62144 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

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