oj.uz

Submission #1086753

# Submission time Handle Problem Language Result Execution time Memory
1086753 2024-09-11T12:08:45 Z nathan4690 Passport (JOI23_passport) C++17
6 / 100
 732 ms 136052 KB 
#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll,ll>
#define ld long double
#define el cout << '\n'
#define f1(i,n) for(ll i=1;i<=n;i++)
#define __file_name ""
using namespace std;
const ll maxn = 1e6+5, inf=1e18;

ll n, rpos[maxn], l, r, lf[maxn], rt[maxn], q, x, d[maxn], d1[maxn],dn[maxn];
vector<pair<ll,ll>> G[maxn];
bool vis[maxn];
priority_queue<pll, vector<pll>, greater<pll>> pq;

void addEdge(ll u, ll v, ll w){
    // cout << u << " -> " << v << " w = " << w;el;
    G[u].push_back({v, w});
}

void build(ll idx, ll l, ll r){
    if(l == r){
        rpos[l] = idx;
        return;
    }
//    addEdge(idx, idx*2, 0);
//    addEdge(idx, idx*2+1, 0);
    addEdge(idx*2, idx, 0);
    addEdge(idx*2+1, idx, 0);
    ll mid = (l+r)/2;
    build(idx*2, l, mid);
    build(idx*2+1, mid+1, r);
}

void addSeg(ll idx, ll l, ll r, ll u, ll v, ll tar, ll w){
    // connects tar -> [u,v] if not rev
    if(r < u || v < l) return;
    if(u <= l && r <= v){
        addEdge(idx, tar, w);
        return;
    }
    ll mid = (l+r)/2;
    addSeg(idx*2, l, mid, u, v, tar, w);
    addSeg(idx*2+1, mid+1, r, u, v, tar, w);
}

void calc(){
    while(!pq.empty()){
        pair<ll,ll> item = pq.top();
        pq.pop();
        ll dist = item.first, u = item.second;
        if(dist != d[u]) continue;
        vis[u] = true;
        for(pair<ll,ll> e: G[u]){
            ll c = e.first, w = e.second;
            if(d[u] + w < d[c]){
                // cout << u << " -> " << c << " changed: " << d[u] + w;el;
                d[c] = d[u] + w;
                pq.push({d[c], c});
            }
        }
    }
}

void dijkstra(ll s){
    d[0] = inf;
    f1(i,4*n) d[i] = inf;
    d[s] = 0ll;
    pq.push({d[s], s});
    calc();
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    if(fopen(__file_name ".inp", "r")){
        freopen(__file_name ".inp","r",stdin);
        freopen(__file_name ".out","w",stdout);
    }
    // code here
    cin >> n;
    build(1, 1, n);
    f1(i,n){
        cin >> l >> r;
        lf[i] = l; rt[i] = r;
//        if(l != i){
//            addSeg(1,1,n,l,i-1,rpos[i],1);
//        }
//        if(i != r){
//            addSeg(1,1,n,i+1,r,rpos[i],1);
//        }
        addSeg(1,1,n,l,r,rpos[i],1);
    }
    dijkstra(rpos[1]);
    f1(i,4*n) {
        d1[i] = d[i];
    }
    dijkstra(rpos[n]);
    f1(i,4*n) {
        dn[i] = d[i];
    }
    f1(i,4*n) d[i] = inf;
    f1(i,4*n) {
        // cout << i << " = " << d1[i] << ' ' << dn[i];el;
        d[i] = d1[i] + dn[i] - (i > rpos[1] && i < rpos[n]);
        pq.push({d[i], i});
    }
    // f1(i, 4*n) pq.push({min(d[i], d1[i] + dn[i]), i});
    calc();
    cin >> q;
    while(q--){
        cin >> x;
        // cout << x << " = " << rpos[x];el;
        cout << (d[rpos[x]] < inf ? d[rpos[x]] : -1);el;
    }
    return 0;
}

Compilation message

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23900 KB Output is correct
2 Correct 11 ms 23964 KB Output is correct
3 Correct 11 ms 23816 KB Output is correct
4 Correct 732 ms 136052 KB Output is correct
5 Correct 376 ms 97212 KB Output is correct
6 Correct 232 ms 87132 KB Output is correct
7 Correct 271 ms 80712 KB Output is correct
8 Correct 201 ms 92888 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23900 KB Output is correct
2 Correct 11 ms 23928 KB Output is correct
3 Correct 11 ms 23896 KB Output is correct
4 Correct 11 ms 23904 KB Output is correct
5 Correct 10 ms 23940 KB Output is correct
6 Correct 11 ms 23896 KB Output is correct
7 Correct 12 ms 23900 KB Output is correct
8 Incorrect 11 ms 23900 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23900 KB Output is correct
2 Correct 11 ms 23928 KB Output is correct
3 Correct 11 ms 23896 KB Output is correct
4 Correct 11 ms 23904 KB Output is correct
5 Correct 10 ms 23940 KB Output is correct
6 Correct 11 ms 23896 KB Output is correct
7 Correct 12 ms 23900 KB Output is correct
8 Incorrect 11 ms 23900 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23900 KB Output is correct
2 Correct 11 ms 23928 KB Output is correct
3 Correct 11 ms 23896 KB Output is correct
4 Correct 11 ms 23904 KB Output is correct
5 Correct 10 ms 23940 KB Output is correct
6 Correct 11 ms 23896 KB Output is correct
7 Correct 12 ms 23900 KB Output is correct
8 Incorrect 11 ms 23900 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23900 KB Output is correct
2 Correct 11 ms 23964 KB Output is correct
3 Correct 11 ms 23816 KB Output is correct
4 Correct 732 ms 136052 KB Output is correct
5 Correct 376 ms 97212 KB Output is correct
6 Correct 232 ms 87132 KB Output is correct
7 Correct 271 ms 80712 KB Output is correct
8 Correct 201 ms 92888 KB Output is correct
9 Correct 11 ms 23900 KB Output is correct
10 Correct 11 ms 23928 KB Output is correct
11 Correct 11 ms 23896 KB Output is correct
12 Correct 11 ms 23904 KB Output is correct
13 Correct 10 ms 23940 KB Output is correct
14 Correct 11 ms 23896 KB Output is correct
15 Correct 12 ms 23900 KB Output is correct
16 Incorrect 11 ms 23900 KB Output isn't correct
17 Halted 0 ms 0 KB -