Submission #736888

#	Time	Username	Problem	Language	Result	Execution time	Memory
736888		Cookie	Passport (JOI23_passport)	C++14	16 / 100	135 ms	225996 KiB

passport

#include<bits/stdc++.h>
#include<fstream>
using namespace std;
ifstream fin("WINTER.inp");
ofstream fout("WINTER.out");

#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 = 2e5, mxm = 1e5, sq = 400;
const int base = (1 << 18);
const ll inf = 1e9;
const ld pre = 1e-6;
struct th{
    int u, v, w;
};

int n, q;
int l[mxn + 1], r[mxn + 1], d[2005 * 2005];
vt<pii>adj[2000 * 2000 + 1];
int id(int i, int j){
    return((i - 1) * n + j);
}
void add_edge(int a, int b, int c, int d, int w){
    adj[id(c, d)].pb({id(a, b), w});
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    forr(i, 1, n + 1){
        cin >> l[i] >> r[i];
        forr(j, i, n + 1){
            d[id(i, j)] = 1e9;
        }
    }
    
    for(int i = 1; i <= n; i++){
        int mnl = 1e9, mxr = -1;
        for(int j = i; j <= n; j++){
            mnl = min(mnl, l[j]); mxr = max(mxr, r[j]);
            if(i == j){
                add_edge(i, j, l[i], r[i], 1);
            }if(i < j){
                add_edge(i, j, i + 1, j, 0); add_edge(i, j, i, j - 1, 0);
            }
            add_edge(i, j, mnl, j, 1); add_edge(i, j, i, mxr, 1);
        }
    }
    d[id(1, n)] = 0;
    deque<int>dq; dq.pb({id(1, n)});
    while(!dq.empty()){
        auto 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);
                }
            }
        }
    }
    cin >> q;
    forr(i, 0, q){
        int x; cin >> x;
        int val = id(x, x);
        if(d[val] == 1e9)cout << -1 << "\n";
        else cout << d[val] << "\n";
    }
    return(0);
}

Compilation message (stderr)

passport.cpp: In function 'int main()':
passport.cpp:66:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   66 |         for(auto [v, w]: adj[u]){
      |                  ^

• Subtask 1: 0 / 6
• Subtask 2: 16 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 8
• Subtask 5: 0 / 46