oj.uz

Submission #1086856

# Submission time Handle Problem Language Result Execution time Memory
1086856 2024-09-11T15:29:57 Z Whisper Passport (JOI23_passport) C++17
6 / 100
 907 ms 167040 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define int long long
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (b); i >= (a); i --)
#define REP(i, a) for (int i = 0; i < (a); ++i)
#define REPD(i, a) for (int i = (a) - 1; i >= 0; --i)

#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)


constexpr ll LINF = (1ll << 60);
constexpr int INF = (1ll << 30);
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

/*
    Phu Trong from Nguyen Tat Thanh High School for gifted student
*/

template <class X, class Y>
    bool minimize(X &x, const Y &y){
        X eps = 1e-9;
        if (x > y + eps) {x = y; return 1;}
        return 0;
    }

template <class X, class Y>
    bool maximize(X &x, const Y &y){
        X eps = 1e-9;
        if (x + eps < y) {x = y; return 1;}
        return 0;
    }
#define MAX                     200005
#define MAX_NODE                1000005
#define lson                    (nd << 1)
#define rson                    (nd << 1 | 1)


int numNode;
int nArr, numQuery;
int l[MAX], r[MAX];
int ID[MAX_NODE];


vector<pair<int, int>> G[MAX_NODE];

void addEdge(int u, int v, int w){
    G[u].emplace_back(v, w);
}
void build(int nd, int l, int r){
    if (l == r){
        addEdge(l, ID[nd], 0);
        return;
    }
    int m = (l + r) >> 1;
    build(lson, l, m);
    build(rson, m + 1, r);

    addEdge(ID[lson], ID[nd], 0);
    addEdge(ID[rson], ID[nd], 0);
}

void addEdge(int nd, int l, int r, int u, int v, int w, int from){
    if (u > r || v < l) return;
    if (u <= l && v >= r){
        addEdge(ID[nd], from, w);
        return;
    }
    int m = (l + r) >> 1;
    addEdge(lson, l, m, u, v, w, from);
    addEdge(rson, m + 1, r, u, v, w, from);
}

void dijkstra(int s, int minDist[]){
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    q.emplace(0, s);
    for (int i = 1; i <= numNode; ++i) minDist[i] = INF;

    minDist[s] = 0;
    while(q.size()){
        int du, u; tie(du, u) = q.top(); q.pop();
        if (du > minDist[u]) continue;

        for (pair<int, int>&x : G[u]){
            int v = x.first, w = x.second;
            if(minimize(minDist[v], minDist[u] + w)){
                q.emplace(minDist[v], v);
            }
        }
    }
}

int minDist[2][MAX_NODE];

int F[MAX_NODE];

void process(void){
    cin >> nArr;
    numNode = nArr;
    for (int i = 1; i <= nArr * 4; ++i) ID[i] = ++numNode;
    build(1, 1, nArr);
    for (int i = 1; i <= nArr; ++i){
        cin >> l[i] >> r[i];
        addEdge(1, 1, nArr, l[i], r[i], 1, i);
    }
    dijkstra(1, minDist[0]);
    dijkstra(nArr, minDist[1]);

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    for (int i = 1; i <= numNode; ++i){
        F[i] = minDist[0][i] + minDist[1][i];
        q.emplace(F[i], i);
    }

    while(q.size()){
        int du, u; tie(du, u) = q.top(); q.pop();
        if(du > F[u]) continue;

        for (pair<int, int>&x : G[u]){
            int v = x.first, w = x.second;
            if(minimize(F[v], F[u] + w)){
                q.emplace(F[v], v);
            }
        }
    }
    cin >> numQuery;
    for (int i = 1; i <= numQuery; ++i){
        int x; cin >> x;
        cout << (F[x] >= INF ? -1 : F[x]) << '\n';
    }
}
signed main(){
    #define name "Whisper"
    cin.tie(nullptr) -> sync_with_stdio(false);
    //freopen(name".inp", "r", stdin);
    //freopen(name".out", "w", stdout);
    process();
    return (0 ^ 0);
}

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 23896 KB Output is correct
4 Correct 907 ms 167040 KB Output is correct
5 Correct 512 ms 112616 KB Output is correct
6 Correct 276 ms 102836 KB Output is correct
7 Correct 359 ms 111960 KB Output is correct
8 Correct 226 ms 102820 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23896 KB Output is correct
2 Correct 10 ms 23900 KB Output is correct
3 Correct 10 ms 23900 KB Output is correct
4 Correct 11 ms 23900 KB Output is correct
5 Correct 11 ms 23900 KB Output is correct
6 Correct 11 ms 23900 KB Output is correct
7 Correct 11 ms 23900 KB Output is correct
8 Incorrect 12 ms 23960 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 23896 KB Output is correct
2 Correct 10 ms 23900 KB Output is correct
3 Correct 10 ms 23900 KB Output is correct
4 Correct 11 ms 23900 KB Output is correct
5 Correct 11 ms 23900 KB Output is correct
6 Correct 11 ms 23900 KB Output is correct
7 Correct 11 ms 23900 KB Output is correct
8 Incorrect 12 ms 23960 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 23896 KB Output is correct
2 Correct 10 ms 23900 KB Output is correct
3 Correct 10 ms 23900 KB Output is correct
4 Correct 11 ms 23900 KB Output is correct
5 Correct 11 ms 23900 KB Output is correct
6 Correct 11 ms 23900 KB Output is correct
7 Correct 11 ms 23900 KB Output is correct
8 Incorrect 12 ms 23960 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 23896 KB Output is correct
4 Correct 907 ms 167040 KB Output is correct
5 Correct 512 ms 112616 KB Output is correct
6 Correct 276 ms 102836 KB Output is correct
7 Correct 359 ms 111960 KB Output is correct
8 Correct 226 ms 102820 KB Output is correct
9 Correct 11 ms 23896 KB Output is correct
10 Correct 10 ms 23900 KB Output is correct
11 Correct 10 ms 23900 KB Output is correct
12 Correct 11 ms 23900 KB Output is correct
13 Correct 11 ms 23900 KB Output is correct
14 Correct 11 ms 23900 KB Output is correct
15 Correct 11 ms 23900 KB Output is correct
16 Incorrect 12 ms 23960 KB Output isn't correct
17 Halted 0 ms 0 KB -