oj.uz

Submission #1111144

# Submission time Handle Problem Language Result Execution time Memory
1111144 2024-11-11T15:19:27 Z mispertion Passport (JOI23_passport) C++17
48 / 100
 117 ms 86092 KB 
#include <bits/stdc++.h>

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using ll = long long;
using ld = long double;
using pii = pair<int, int>;

#define F first
#define S second

const ld PI = 3.1415926535;
const int N = 5e5 + 10;
const int M = 1e7 + 1;
ll mod =  998244353;
const int infi = 1e9;
const ll infl = 1e16;
const int P = 31;

int mult(int a, int b) { return a * 1LL * b % mod; }

int sum(int a, int b) {
    if (a + b < 0) return a + b + mod;
    if (a + b >= mod) return a + b - mod;
    return a + b;
}

ll binpow(ll a, ll n) {
    if (n == 0) return 1;
    if (n % 2 == 1) {
        return binpow(a, n - 1) * a % mod;
    } else {
        ll b = binpow(a, n / 2);
        return b * b % mod;
    }
}

int n, L[N], R[N], V[N], q, cur, ru, lc[N], rc[N], a[N], b[N], d[N];
vector<pair<int, int>> g[N];

void buildup(int v, int tl, int tr){
    if(tl == tr){
        g[tl].push_back({v, 1});
        return;
    }
    int tm = (tl + tr) / 2;
    lc[v] = ++cur;
    rc[v] = ++cur;
    g[lc[v]].push_back({v, 0});
    g[rc[v]].push_back({v, 0});
    buildup(lc[v], tl, tm);
    buildup(rc[v], tm + 1, tr);
}

void addup(int v, int tl, int tr, int l, int r, int x){
    if(tl > r || l > tr)
        return;
    if(l <= tl && tr <= r){
        g[v].push_back({x, 0});
        return;
    }
    int tm = (tl + tr) / 2;
    addup(lc[v], tl, tm, l, r, x);
    addup(rc[v], tm + 1, tr, l, r, x);
}

void solve() {
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> L[i] >> R[i];
    cur = n + 1;
    ru = cur;
    buildup(ru, 1, n);
    for(int i = 1; i <= cur; i++){
        a[i] = infi;
        b[i] = infi;
    }
    for(int i = 1; i <= n; i++){
        addup(ru, 1, n, L[i], R[i], i);
    }
    deque<int> dq;
    for(int i = 1; i <= n; i++){
        if(L[i] == 1)
            dq.push_back(i), a[i] = 0;
    }
    while(!dq.empty()){
        int v = dq.front();
        dq.pop_front();
        for(auto e : g[v]){
            int u = e.F, w = e.S;
            if(a[u] == infi){
                a[u] = a[v] + w;
                if(w == 0)
                    dq.push_front(u);
                else
                    dq.push_back(u);
            }
        }
    }
    for(int i = 1; i <= n; i++)
        if(R[i] == n)
            dq.push_back(i), b[i] = 0;
    while(!dq.empty()){
        int v = dq.front();
        dq.pop_front();
        for(auto e : g[v]){
            int u = e.F, w = e.S;
            if(b[u] == infi){
                b[u] = b[v] + w;
                if(w == 0)
                    dq.push_front(u);
                else
                    dq.push_back(u);
            }
        }
    }
    int nw = ++cur;
    for(int i = 1; i <= n; i++){
        g[nw].push_back({i, a[i] + b[i] + 1});
    }
    for(int i = 1; i <= cur; i++)
        d[i] = infi;
    d[nw] = 0;
    set<pii> st;
    st.insert({1, nw});
    while(!st.empty()){
        int v = st.begin()->S;
        st.erase(st.begin());
        for(auto e : g[v]){
            int u = e.F, w = e.S;
            if(d[u] > d[v] + w){
                st.erase({d[u], u});
                d[u] = d[v] + w;
                st.insert({d[u], u});
            }
        }
    }
    int q;
    cin >> q;
    while(q--){
        int x;
        cin >> x;
        cout << (d[x] > n ? -1 : d[x]) << '\n';
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12112 KB Output is correct
2 Correct 12 ms 12112 KB Output is correct
3 Correct 9 ms 12112 KB Output is correct
4 Runtime error 117 ms 86092 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12112 KB Output is correct
2 Correct 8 ms 12112 KB Output is correct
3 Correct 4 ms 12880 KB Output is correct
4 Correct 3 ms 12880 KB Output is correct
5 Correct 3 ms 12880 KB Output is correct
6 Correct 4 ms 14968 KB Output is correct
7 Correct 3 ms 12880 KB Output is correct
8 Correct 4 ms 19024 KB Output is correct
9 Correct 3 ms 12880 KB Output is correct
10 Correct 3 ms 12952 KB Output is correct
11 Correct 7 ms 12112 KB Output is correct
12 Correct 9 ms 12112 KB Output is correct
13 Correct 7 ms 12344 KB Output is correct
14 Correct 7 ms 12368 KB Output is correct
15 Correct 7 ms 12112 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12112 KB Output is correct
2 Correct 8 ms 12112 KB Output is correct
3 Correct 4 ms 12880 KB Output is correct
4 Correct 3 ms 12880 KB Output is correct
5 Correct 3 ms 12880 KB Output is correct
6 Correct 4 ms 14968 KB Output is correct
7 Correct 3 ms 12880 KB Output is correct
8 Correct 4 ms 19024 KB Output is correct
9 Correct 3 ms 12880 KB Output is correct
10 Correct 3 ms 12952 KB Output is correct
11 Correct 7 ms 12112 KB Output is correct
12 Correct 9 ms 12112 KB Output is correct
13 Correct 7 ms 12344 KB Output is correct
14 Correct 7 ms 12368 KB Output is correct
15 Correct 7 ms 12112 KB Output is correct
16 Correct 10 ms 12880 KB Output is correct
17 Correct 7 ms 12880 KB Output is correct
18 Correct 12 ms 13136 KB Output is correct
19 Correct 7 ms 13136 KB Output is correct
20 Correct 7 ms 13056 KB Output is correct
21 Correct 6 ms 12624 KB Output is correct
22 Correct 5 ms 19536 KB Output is correct
23 Correct 7 ms 13648 KB Output is correct
24 Correct 8 ms 17596 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12112 KB Output is correct
2 Correct 8 ms 12112 KB Output is correct
3 Correct 4 ms 12880 KB Output is correct
4 Correct 3 ms 12880 KB Output is correct
5 Correct 3 ms 12880 KB Output is correct
6 Correct 4 ms 14968 KB Output is correct
7 Correct 3 ms 12880 KB Output is correct
8 Correct 4 ms 19024 KB Output is correct
9 Correct 3 ms 12880 KB Output is correct
10 Correct 3 ms 12952 KB Output is correct
11 Correct 7 ms 12112 KB Output is correct
12 Correct 9 ms 12112 KB Output is correct
13 Correct 7 ms 12344 KB Output is correct
14 Correct 7 ms 12368 KB Output is correct
15 Correct 7 ms 12112 KB Output is correct
16 Correct 10 ms 12880 KB Output is correct
17 Correct 7 ms 12880 KB Output is correct
18 Correct 12 ms 13136 KB Output is correct
19 Correct 7 ms 13136 KB Output is correct
20 Correct 7 ms 13056 KB Output is correct
21 Correct 6 ms 12624 KB Output is correct
22 Correct 5 ms 19536 KB Output is correct
23 Correct 7 ms 13648 KB Output is correct
24 Correct 8 ms 17596 KB Output is correct
25 Correct 3 ms 12880 KB Output is correct
26 Correct 9 ms 12216 KB Output is correct
27 Correct 7 ms 13648 KB Output is correct
28 Correct 6 ms 13440 KB Output is correct
29 Correct 6 ms 13048 KB Output is correct
30 Correct 5 ms 12880 KB Output is correct
31 Correct 6 ms 12880 KB Output is correct

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12112 KB Output is correct
2 Correct 12 ms 12112 KB Output is correct
3 Correct 9 ms 12112 KB Output is correct
4 Runtime error 117 ms 86092 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -