oj.uz

Submission #887560

# Submission time Handle Problem Language Result Execution time Memory
887560 2023-12-14T18:27:48 Z andrei_iorgulescu Passport (JOI23_passport) C++14
100 / 100
 731 ms 121720 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long

const int inf = 1e18;

struct muchie
{
    int x,y,z;///teoretic de la x pe [y z]
    int c;///costul
};

int n,q;
muchie e[200005];
vector<muchie> v[200005];
int rmq1[200005][20],rmqn[200005][20];
int lg[200005];

int query1(int l,int r)
{
    int lgg = lg[r - l + 1];
    return min(rmq1[l][lgg],rmq1[r - (1 << lgg) + 1][lgg]);
}

int queryn(int l,int r)
{
    int lgg = lg[r - l + 1];
    return min(rmqn[l][lgg],rmqn[r - (1 << lgg) + 1][lgg]);
}

bool cmp(muchie A,muchie B)
{
    return A.y < B.y;
}

pair<int,int> aint[800005];

void build(int nod,int l,int r)
{
    if (l == r)
    {
        aint[nod] = {e[l].z,l};
    }
    else
    {
        int mij = (l + r) / 2;
        build(2 * nod,l,mij);
        build(2 * nod + 1,mij + 1,r);
        aint[nod] = max(aint[2 * nod],aint[2 * nod + 1]);
    }
}

void update(int nod,int l,int r,int pos)
{
    if (l == r)
    {
        aint[nod] = {-1,-1};
    }
    else
    {
        int mij = (l + r) / 2;
        if (pos <= mij)
            update(2 * nod,l,mij,pos);
        else
            update(2 * nod + 1,mij + 1,r,pos);
        aint[nod] = max(aint[2 * nod],aint[2 * nod + 1]);
    }
}

pair<int,int> query(int nod,int l,int r,int st,int dr)
{
    if (dr < l or r < st)
        return {-1,-1};
    if (st <= l and r <= dr)
        return aint[nod];
    int mij = (l + r) / 2;
    return max(query(2 * nod,l,mij,st,dr),query(2 * nod + 1,mij + 1,r,st,dr));
}

void dijkstra_nebun(vector<int> &fin, vector<int> dinit)
{
    for (int i = 1; i <= n; i++)
        fin[i] = 4 * inf;
    ///ok so basically, vreau sa iau muchiile care il contin pe nod in [y z] si sa bag muchia inversa pana in x etc
    ///ca sa fac asta (desi aproape ma pot jura ca se poate mai simplu) sortez muchiile dupa y, tin un aint si iau aia cu max_z
    sort(e + 1,e + q + 1,cmp);
    build(1,1,q);
    priority_queue<pair<int,int>>pq;
    for (int i = 1; i <= n; i++)
        pq.push({-dinit[i],i});
    while (!pq.empty())
    {
        int nod = pq.top().second;
        int cst = -pq.top().first;
        pq.pop();
        if (cst >= fin[nod])
            continue;
        fin[nod] = cst;
        int st = 0,pas = 1 << 17;
        while (pas != 0)
        {
            if (st + pas <= q and e[st + pas].y <= nod)
                st += pas;
            pas /= 2;
        }
        while (true)
        {
            if (st == 0)
                break;
            pair<int,int> qr = query(1,1,q,1,st);
            if (qr.first < nod)
                break;
            pq.push({-(fin[nod] + e[qr.second].c),e[qr.second].x});
            update(1,1,q,qr.second);
        }
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    q = n;
    for (int i = 1; i <= n; i++)
    {
        /*
        int x1,x2,x3,x4;
        cin >> x1 >> x2 >> x3 >> x4;
        muchie aux;
        aux.c = x2;
        aux.x = x1;
        aux.y = x3;
        aux.z = x4;
        e[i] = aux;
        v[x1].push_back(aux);*/
        int l,r;
        cin >> l >> r;
        muchie aux;
        aux.c = 1;
        aux.x = i;
        aux.y = l;
        aux.z = r;
        e[i] = aux;
        v[i].push_back(aux);
    }
    vector<int>d1(n + 1),dn(n + 1),cost(n + 1),ans(n + 1);
    vector<int>initial(n + 1);
    initial[1] = 0;
    for (int i = 2; i <= n; i++)
        initial[i] = inf;
    dijkstra_nebun(d1,initial);
    initial[1] = inf;
    initial[n] = 0;
    dijkstra_nebun(dn,initial);
    for (int i = 2; i <= n; i++)
        lg[i] = 1 + lg[i / 2];
    for (int i = 1; i <= n; i++)
        rmq1[i][0] = d1[i],rmqn[i][0] = dn[i];
    for (int j = 1; j <= lg[n]; j++)
    {
        for (int i = 1; i <= n - (1 << j) + 1; i++)
        {
            rmq1[i][j] = min(rmq1[i][j - 1],rmq1[i + (1 << (j - 1))][j - 1]);
            rmqn[i][j] = min(rmqn[i][j - 1],rmqn[i + (1 << (j - 1))][j - 1]);
        }
    }
    for (int i = 1; i <= n; i++)
    {
        cost[i] = d1[i] + dn[i];
        for (auto it : v[i])
        {
            cost[i] = min(cost[i],it.c + query1(it.y,it.z) + queryn(it.y,it.z));
        }
    }
    for (int i = 1; i <= n; i++)
        initial[i] = cost[i];
    dijkstra_nebun(ans,initial);
    int q;
    cin >> q;
    for (int i = 1; i <= q; i++)
    {
        int x;
        cin >> x;
        if (ans[x] >= inf)
            cout << -1 << '\n';
        else
            cout << ans[x] << '\n';
    }
    return 0;
}

/**
ce insane
deci vreau sa calculez cost[i] = costul din i daca el e punctul de articulatie (xt)
cost[i] = min(d1[i] + dn[i],c[k] + min(d1[j]) + min(dn[j]) cu k o muchie din i, j intre l[k] si r[k])
adica daca imi calculez cost[i] pentru fiecare nod, apoi am doar un rmq sau cv
apoi, pentru fiecare x, vreau minimul din dist(x,i) + cost[i], adica un dijkstra in care nodul i in care offset dist[i]
doamne ajuta cu impl
**/

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8680 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 731 ms 115972 KB Output is correct
5 Correct 561 ms 109908 KB Output is correct
6 Correct 457 ms 112508 KB Output is correct
7 Correct 345 ms 120208 KB Output is correct
8 Correct 318 ms 100588 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 2 ms 8540 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 2 ms 8540 KB Output is correct
12 Correct 2 ms 8540 KB Output is correct
13 Correct 3 ms 8796 KB Output is correct
14 Correct 2 ms 8540 KB Output is correct
15 Correct 2 ms 8540 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 2 ms 8540 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 2 ms 8540 KB Output is correct
12 Correct 2 ms 8540 KB Output is correct
13 Correct 3 ms 8796 KB Output is correct
14 Correct 2 ms 8540 KB Output is correct
15 Correct 2 ms 8540 KB Output is correct
16 Correct 7 ms 9304 KB Output is correct
17 Correct 6 ms 9304 KB Output is correct
18 Correct 5 ms 9564 KB Output is correct
19 Correct 5 ms 9308 KB Output is correct
20 Correct 5 ms 9564 KB Output is correct
21 Correct 6 ms 9396 KB Output is correct
22 Correct 5 ms 9564 KB Output is correct
23 Correct 6 ms 9564 KB Output is correct
24 Correct 6 ms 9416 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 2 ms 8540 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 2 ms 8540 KB Output is correct
12 Correct 2 ms 8540 KB Output is correct
13 Correct 3 ms 8796 KB Output is correct
14 Correct 2 ms 8540 KB Output is correct
15 Correct 2 ms 8540 KB Output is correct
16 Correct 7 ms 9304 KB Output is correct
17 Correct 6 ms 9304 KB Output is correct
18 Correct 5 ms 9564 KB Output is correct
19 Correct 5 ms 9308 KB Output is correct
20 Correct 5 ms 9564 KB Output is correct
21 Correct 6 ms 9396 KB Output is correct
22 Correct 5 ms 9564 KB Output is correct
23 Correct 6 ms 9564 KB Output is correct
24 Correct 6 ms 9416 KB Output is correct
25 Correct 2 ms 8540 KB Output is correct
26 Correct 2 ms 8540 KB Output is correct
27 Correct 6 ms 9564 KB Output is correct
28 Correct 6 ms 9560 KB Output is correct
29 Correct 6 ms 9564 KB Output is correct
30 Correct 6 ms 9564 KB Output is correct
31 Correct 8 ms 9564 KB Output is correct

Subtask #5
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8680 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 731 ms 115972 KB Output is correct
5 Correct 561 ms 109908 KB Output is correct
6 Correct 457 ms 112508 KB Output is correct
7 Correct 345 ms 120208 KB Output is correct
8 Correct 318 ms 100588 KB Output is correct
9 Correct 2 ms 8540 KB Output is correct
10 Correct 2 ms 8540 KB Output is correct
11 Correct 2 ms 8540 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct
13 Correct 2 ms 8540 KB Output is correct
14 Correct 2 ms 8540 KB Output is correct
15 Correct 1 ms 8540 KB Output is correct
16 Correct 1 ms 8540 KB Output is correct
17 Correct 2 ms 8540 KB Output is correct
18 Correct 1 ms 8540 KB Output is correct
19 Correct 2 ms 8540 KB Output is correct
20 Correct 2 ms 8540 KB Output is correct
21 Correct 3 ms 8796 KB Output is correct
22 Correct 2 ms 8540 KB Output is correct
23 Correct 2 ms 8540 KB Output is correct
24 Correct 7 ms 9304 KB Output is correct
25 Correct 6 ms 9304 KB Output is correct
26 Correct 5 ms 9564 KB Output is correct
27 Correct 5 ms 9308 KB Output is correct
28 Correct 5 ms 9564 KB Output is correct
29 Correct 6 ms 9396 KB Output is correct
30 Correct 5 ms 9564 KB Output is correct
31 Correct 6 ms 9564 KB Output is correct
32 Correct 6 ms 9416 KB Output is correct
33 Correct 2 ms 8540 KB Output is correct
34 Correct 2 ms 8540 KB Output is correct
35 Correct 6 ms 9564 KB Output is correct
36 Correct 6 ms 9560 KB Output is correct
37 Correct 6 ms 9564 KB Output is correct
38 Correct 6 ms 9564 KB Output is correct
39 Correct 8 ms 9564 KB Output is correct
40 Correct 713 ms 118752 KB Output is correct
41 Correct 555 ms 112668 KB Output is correct
42 Correct 480 ms 113584 KB Output is correct
43 Correct 477 ms 118548 KB Output is correct
44 Correct 490 ms 113008 KB Output is correct
45 Correct 522 ms 112884 KB Output is correct
46 Correct 192 ms 50200 KB Output is correct
47 Correct 529 ms 118264 KB Output is correct
48 Correct 597 ms 121720 KB Output is correct