oj.uz

Submission #1086860

# Submission time Handle Problem Language Result Execution time Memory
1086860 2024-09-11T15:38:15 Z Whisper Passport (JOI23_passport) C++17
6 / 100
 1077 ms 181052 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                1200005
#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, ++numNode);
        addEdge(numNode, i, 0);
    }
    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 13 ms 28504 KB Output is correct
2 Correct 13 ms 28504 KB Output is correct
3 Correct 14 ms 28692 KB Output is correct
4 Correct 1077 ms 181052 KB Output is correct
5 Correct 574 ms 144332 KB Output is correct
6 Correct 323 ms 136884 KB Output is correct
7 Correct 494 ms 126496 KB Output is correct
8 Correct 283 ms 116300 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28504 KB Output is correct
2 Correct 12 ms 28504 KB Output is correct
3 Correct 12 ms 28504 KB Output is correct
4 Correct 12 ms 28676 KB Output is correct
5 Correct 13 ms 28508 KB Output is correct
6 Correct 14 ms 28632 KB Output is correct
7 Correct 12 ms 28508 KB Output is correct
8 Incorrect 14 ms 28508 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28504 KB Output is correct
2 Correct 12 ms 28504 KB Output is correct
3 Correct 12 ms 28504 KB Output is correct
4 Correct 12 ms 28676 KB Output is correct
5 Correct 13 ms 28508 KB Output is correct
6 Correct 14 ms 28632 KB Output is correct
7 Correct 12 ms 28508 KB Output is correct
8 Incorrect 14 ms 28508 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28504 KB Output is correct
2 Correct 12 ms 28504 KB Output is correct
3 Correct 12 ms 28504 KB Output is correct
4 Correct 12 ms 28676 KB Output is correct
5 Correct 13 ms 28508 KB Output is correct
6 Correct 14 ms 28632 KB Output is correct
7 Correct 12 ms 28508 KB Output is correct
8 Incorrect 14 ms 28508 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 28504 KB Output is correct
2 Correct 13 ms 28504 KB Output is correct
3 Correct 14 ms 28692 KB Output is correct
4 Correct 1077 ms 181052 KB Output is correct
5 Correct 574 ms 144332 KB Output is correct
6 Correct 323 ms 136884 KB Output is correct
7 Correct 494 ms 126496 KB Output is correct
8 Correct 283 ms 116300 KB Output is correct
9 Correct 14 ms 28504 KB Output is correct
10 Correct 12 ms 28504 KB Output is correct
11 Correct 12 ms 28504 KB Output is correct
12 Correct 12 ms 28676 KB Output is correct
13 Correct 13 ms 28508 KB Output is correct
14 Correct 14 ms 28632 KB Output is correct
15 Correct 12 ms 28508 KB Output is correct
16 Incorrect 14 ms 28508 KB Output isn't correct
17 Halted 0 ms 0 KB -