oj.uz

Submission #729024

# Submission time Handle Problem Language Result Execution time Memory
729024 2023-04-23T11:58:07 Z MilosMilutinovic Passport (JOI23_passport) C++14
100 / 100
 1413 ms 90756 KB 
#include <bits/stdc++.h>
using namespace std;
 
const int inf=0x3f3f3f3f;
int n,q,l[800005],r[800005],dl[800005],dr[800005],dis[800005],idx[200005];
vector<int> g[800005];
 
void bfs(int* d)
{
    set<pair<int,int>> st;
    for(int i=1;i<=n;i++) st.emplace(d[i],i);
    while(!st.empty())
    {
        auto it=st.begin();
        int x=it->second;
        st.erase(it);
        if(x<=n)
        {
            for(int y=idx[x];y>=1;y/=2)
            {
                if(d[n+y]>d[x])
                {
                    if(st.find({d[n+y],n+y})!=st.end()) st.erase(st.find({d[n+y],n+y}));
                    d[n+y]=d[x];st.emplace(d[n+y],n+y);
                }
            }
        }
        else
        {
            for(int y:g[x])
            {
                int f=d[x]+(y<=n);
                if(d[y]>f)
                {
                    if(st.find({d[y],y})!=st.end()) st.erase(st.find({d[y],y}));
                    d[y]=f;st.emplace(f,y);
                }
            }
        }
    }
}
 
void build(int v,int l,int r)
{
    if(l==r) {idx[l]=v;return;}
    int mid=l+r>>1;
    build(v*2,l,mid);
    build(v*2+1,mid+1,r);
}
void add(int v,int l,int r,int ql,int qr,int i)
{
    if(l>r||l>qr||r<ql) return;
    if(ql<=l&&r<=qr)
    {
        g[i].push_back(n+v);
        g[n+v].push_back(i);
        return;
    }
    int mid=l+r>>1;
    add(v*2,l,mid,ql,qr,i);
    add(v*2+1,mid+1,r,ql,qr,i);
}
 
signed main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d%d",&l[i],&r[i]);
    build(1,1,n);
    for(int i=1;i<=n;i++) add(1,1,n,l[i],r[i],i);
    for(int i=1;i<=800000;i++) dl[i]=dr[i]=dis[i]=inf;
    dl[1]=0;dr[n]=0;
    bfs(dl);bfs(dr);
    dl[1]=1;dr[n]=1;
    for(int i=1;i<=n;i++) dis[i]=dl[i]+dr[i];
    bfs(dis);
    for(int i=1;i<=n;i++) if(dis[i]>=inf) dis[i]=-1; else dis[i]--;
    scanf("%d",&q);
    while(q--)
    {
        int x;scanf("%d",&x);
        printf("%d\n",dis[x]);
    }
}

Compilation message

passport.cpp: In function 'void build(int, int, int)':
passport.cpp:46:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |     int mid=l+r>>1;
      |             ~^~
passport.cpp: In function 'void add(int, int, int, int, int, int)':
passport.cpp:59:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |     int mid=l+r>>1;
      |             ~^~
passport.cpp: In function 'int main()':
passport.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
passport.cpp:67:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |     for(int i=1;i<=n;i++) scanf("%d%d",&l[i],&r[i]);
      |                           ~~~~~^~~~~~~~~~~~~~~~~~~~
passport.cpp:77:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
passport.cpp:80:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |         int x;scanf("%d",&x);
      |               ~~~~~^~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 28372 KB Output is correct
2 Correct 13 ms 28424 KB Output is correct
3 Correct 13 ms 28500 KB Output is correct
4 Correct 1387 ms 86580 KB Output is correct
5 Correct 774 ms 60448 KB Output is correct
6 Correct 648 ms 68704 KB Output is correct
7 Correct 656 ms 57612 KB Output is correct
8 Correct 354 ms 57172 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28376 KB Output is correct
2 Correct 14 ms 28500 KB Output is correct
3 Correct 15 ms 28500 KB Output is correct
4 Correct 14 ms 28500 KB Output is correct
5 Correct 14 ms 28420 KB Output is correct
6 Correct 13 ms 28500 KB Output is correct
7 Correct 14 ms 28468 KB Output is correct
8 Correct 14 ms 28444 KB Output is correct
9 Correct 13 ms 28396 KB Output is correct
10 Correct 13 ms 28372 KB Output is correct
11 Correct 15 ms 28548 KB Output is correct
12 Correct 15 ms 28500 KB Output is correct
13 Correct 15 ms 28432 KB Output is correct
14 Correct 15 ms 28500 KB Output is correct
15 Correct 14 ms 28500 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28376 KB Output is correct
2 Correct 14 ms 28500 KB Output is correct
3 Correct 15 ms 28500 KB Output is correct
4 Correct 14 ms 28500 KB Output is correct
5 Correct 14 ms 28420 KB Output is correct
6 Correct 13 ms 28500 KB Output is correct
7 Correct 14 ms 28468 KB Output is correct
8 Correct 14 ms 28444 KB Output is correct
9 Correct 13 ms 28396 KB Output is correct
10 Correct 13 ms 28372 KB Output is correct
11 Correct 15 ms 28548 KB Output is correct
12 Correct 15 ms 28500 KB Output is correct
13 Correct 15 ms 28432 KB Output is correct
14 Correct 15 ms 28500 KB Output is correct
15 Correct 14 ms 28500 KB Output is correct
16 Correct 24 ms 29028 KB Output is correct
17 Correct 20 ms 28776 KB Output is correct
18 Correct 20 ms 29032 KB Output is correct
19 Correct 21 ms 29008 KB Output is correct
20 Correct 20 ms 28848 KB Output is correct
21 Correct 17 ms 28864 KB Output is correct
22 Correct 16 ms 28748 KB Output is correct
23 Correct 19 ms 28888 KB Output is correct
24 Correct 18 ms 28884 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28376 KB Output is correct
2 Correct 14 ms 28500 KB Output is correct
3 Correct 15 ms 28500 KB Output is correct
4 Correct 14 ms 28500 KB Output is correct
5 Correct 14 ms 28420 KB Output is correct
6 Correct 13 ms 28500 KB Output is correct
7 Correct 14 ms 28468 KB Output is correct
8 Correct 14 ms 28444 KB Output is correct
9 Correct 13 ms 28396 KB Output is correct
10 Correct 13 ms 28372 KB Output is correct
11 Correct 15 ms 28548 KB Output is correct
12 Correct 15 ms 28500 KB Output is correct
13 Correct 15 ms 28432 KB Output is correct
14 Correct 15 ms 28500 KB Output is correct
15 Correct 14 ms 28500 KB Output is correct
16 Correct 24 ms 29028 KB Output is correct
17 Correct 20 ms 28776 KB Output is correct
18 Correct 20 ms 29032 KB Output is correct
19 Correct 21 ms 29008 KB Output is correct
20 Correct 20 ms 28848 KB Output is correct
21 Correct 17 ms 28864 KB Output is correct
22 Correct 16 ms 28748 KB Output is correct
23 Correct 19 ms 28888 KB Output is correct
24 Correct 18 ms 28884 KB Output is correct
25 Correct 17 ms 28472 KB Output is correct
26 Correct 14 ms 28436 KB Output is correct
27 Correct 23 ms 29024 KB Output is correct
28 Correct 21 ms 28756 KB Output is correct
29 Correct 19 ms 28852 KB Output is correct
30 Correct 19 ms 28756 KB Output is correct
31 Correct 19 ms 28884 KB Output is correct

Subtask #5
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 28372 KB Output is correct
2 Correct 13 ms 28424 KB Output is correct
3 Correct 13 ms 28500 KB Output is correct
4 Correct 1387 ms 86580 KB Output is correct
5 Correct 774 ms 60448 KB Output is correct
6 Correct 648 ms 68704 KB Output is correct
7 Correct 656 ms 57612 KB Output is correct
8 Correct 354 ms 57172 KB Output is correct
9 Correct 14 ms 28376 KB Output is correct
10 Correct 14 ms 28500 KB Output is correct
11 Correct 15 ms 28500 KB Output is correct
12 Correct 14 ms 28500 KB Output is correct
13 Correct 14 ms 28420 KB Output is correct
14 Correct 13 ms 28500 KB Output is correct
15 Correct 14 ms 28468 KB Output is correct
16 Correct 14 ms 28444 KB Output is correct
17 Correct 13 ms 28396 KB Output is correct
18 Correct 13 ms 28372 KB Output is correct
19 Correct 15 ms 28548 KB Output is correct
20 Correct 15 ms 28500 KB Output is correct
21 Correct 15 ms 28432 KB Output is correct
22 Correct 15 ms 28500 KB Output is correct
23 Correct 14 ms 28500 KB Output is correct
24 Correct 24 ms 29028 KB Output is correct
25 Correct 20 ms 28776 KB Output is correct
26 Correct 20 ms 29032 KB Output is correct
27 Correct 21 ms 29008 KB Output is correct
28 Correct 20 ms 28848 KB Output is correct
29 Correct 17 ms 28864 KB Output is correct
30 Correct 16 ms 28748 KB Output is correct
31 Correct 19 ms 28888 KB Output is correct
32 Correct 18 ms 28884 KB Output is correct
33 Correct 17 ms 28472 KB Output is correct
34 Correct 14 ms 28436 KB Output is correct
35 Correct 23 ms 29024 KB Output is correct
36 Correct 21 ms 28756 KB Output is correct
37 Correct 19 ms 28852 KB Output is correct
38 Correct 19 ms 28756 KB Output is correct
39 Correct 19 ms 28884 KB Output is correct
40 Correct 1413 ms 90616 KB Output is correct
41 Correct 804 ms 63284 KB Output is correct
42 Correct 922 ms 87160 KB Output is correct
43 Correct 930 ms 90756 KB Output is correct
44 Correct 679 ms 71404 KB Output is correct
45 Correct 642 ms 66308 KB Output is correct
46 Correct 375 ms 43988 KB Output is correct
47 Correct 980 ms 75756 KB Output is correct
48 Correct 659 ms 76224 KB Output is correct