oj.uz

답안 #736992

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
736992 2023-05-06T12:16:44 Z Cookie Passport (JOI23_passport) C++14
0 / 100
 11 ms 23764 KB 
#include<bits/stdc++.h>
#include<fstream>
using namespace std;
 
 
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const ld PI = 3.14159265359;
const int x[4] = {1, -1, 0, 0};
const int y[4] = {0, 0, 1, -1};
const ll mod = 1e9 + 7;
const int mxn = 5e5, mxm = 1e5, sq = 400;
const int base = (1 << 18);
const ll inf = 1e9;
const ld pre = 1e-6;
//cool problem!
int n;
int l[mxn + 1], r[mxn + 1], id, lson[2 * mxn + 5], rson[2 * mxn + 5];
vt<pii>adj[2 * mxn + 5];
vt<ll>d1, d2, d3;
int build(int nd, int l, int r){
    if(l == r)return(l);
    int mid = (l + r) >> 1;
    int ls = build(nd << 1, l, mid), rs = build(nd << 1 | 1, mid + 1, r);
    ++id;
    lson[id] = ls; rson[id] = rs;
    
    adj[lson[id]].emplace_back(id, 0); adj[rson[id]].emplace_back(id, 0);
    return(id);
}
void upd(int nd, int l, int r, int ql, int qr, int u){
    if(ql > r || qr < l)return;
    if(ql <= l && qr >= r){
        
        adj[nd].emplace_back(u, 1);
        return;
    }
    int mid = (l + r) >> 1;
    upd(lson[nd], l, mid, ql, qr, u); upd(rson[nd], mid + 1, r, ql, qr, u);
}
void find(vt<ll>&d){
    deque<int>dq;
    for(int i = 1; i <= n; i++){
        if(d[i] >= inf)dq.pb(i);
    }
   
    while(!dq.empty()){
        int u = dq.front(); dq.pop_front();
        for(auto [v, w]: adj[u]){
            if(d[v] > d[u] + w){
                d[v] = d[u] + w;
                if(w){
                    dq.pb(v);
                }else{
                    dq.push_front(v);
                }
            }
        }
    }
}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    id = n;
    int root = build(1, 1, n);
    
    forr(i, 1, n + 1){
        cin >> l[i] >> r[i];
        upd(root, 1, n, l[i], r[i], i);
    }
    d1.resize(2 * n + 5, inf); d1[1] = 0;
    find(d1); 
    d1[1] = 1;
    d2.resize(2 * n + 5, inf); d2[n] = 0;
    
    find(d2);
    d2[n] = 1;
    int q; cin >> q;
    
    d3.resize(4 * n + 1, inf);
    for(int i = 1; i <= n; i++){
        d3[i] = min(d1[i] + d2[i], inf); 
    }
    find(d3);
    
    forr(i, 0, q){
        int x; cin >> x;
        if(d3[x] >= 1e9)cout << -1 << "\n";
        else cout << d3[x] - 1 << "\n";
    }
    
    return(0);
}

Compilation message

passport.cpp: In function 'void find(std::vector<long long int>&)':
passport.cpp:58:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   58 |         for(auto [v, w]: adj[u]){
      |                  ^

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 23764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 23764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 23764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 23764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 23764 KB Output isn't correct
2 Halted 0 ms 0 KB -