oj.uz

Submission #1086752

# Submission time Handle Problem Language Result Execution time Memory
1086752 2024-09-11T12:06:30 Z nathan4690 Passport (JOI23_passport) C++17
6 / 100
 718 ms 136100 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];
        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 23900 KB Output is correct
3 Correct 11 ms 23900 KB Output is correct
4 Correct 718 ms 136100 KB Output is correct
5 Correct 346 ms 97400 KB Output is correct
6 Correct 250 ms 87004 KB Output is correct
7 Correct 275 ms 80684 KB Output is correct
8 Correct 202 ms 92908 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 10 ms 23928 KB Output is correct
3 Correct 10 ms 23896 KB Output is correct
4 Correct 11 ms 23768 KB Output is correct
5 Correct 11 ms 23988 KB Output is correct
6 Correct 9 ms 23900 KB Output is correct
7 Correct 9 ms 23972 KB Output is correct
8 Incorrect 9 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 10 ms 23928 KB Output is correct
3 Correct 10 ms 23896 KB Output is correct
4 Correct 11 ms 23768 KB Output is correct
5 Correct 11 ms 23988 KB Output is correct
6 Correct 9 ms 23900 KB Output is correct
7 Correct 9 ms 23972 KB Output is correct
8 Incorrect 9 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 10 ms 23928 KB Output is correct
3 Correct 10 ms 23896 KB Output is correct
4 Correct 11 ms 23768 KB Output is correct
5 Correct 11 ms 23988 KB Output is correct
6 Correct 9 ms 23900 KB Output is correct
7 Correct 9 ms 23972 KB Output is correct
8 Incorrect 9 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 23900 KB Output is correct
3 Correct 11 ms 23900 KB Output is correct
4 Correct 718 ms 136100 KB Output is correct
5 Correct 346 ms 97400 KB Output is correct
6 Correct 250 ms 87004 KB Output is correct
7 Correct 275 ms 80684 KB Output is correct
8 Correct 202 ms 92908 KB Output is correct
9 Correct 11 ms 23900 KB Output is correct
10 Correct 10 ms 23928 KB Output is correct
11 Correct 10 ms 23896 KB Output is correct
12 Correct 11 ms 23768 KB Output is correct
13 Correct 11 ms 23988 KB Output is correct
14 Correct 9 ms 23900 KB Output is correct
15 Correct 9 ms 23972 KB Output is correct
16 Incorrect 9 ms 23900 KB Output isn't correct
17 Halted 0 ms 0 KB -