oj.uz

Submission #468669

# Submission time Handle Problem Language Result Execution time Memory
468669 2021-08-29T09:33:13 Z blue Factories (JOI14_factories) C++17
100 / 100
 7470 ms 255968 KB 
#include "factories.h"
#include <vector>
#include <set>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

const int maxN = 500'000;
const int logN = 21;
const long long INF = 1'000'000'000'000'000'000LL;

//ZERO-INDEXED!!!

int N;
vector<int> edge[maxN];
vector<long long> wt[maxN];

int curr = -1;
vector<int> order;
vector<int> ind(maxN, -1);
vector<int> depth(maxN, 0);
vector<long long> dist0(maxN, 0);
vector<int> parent(maxN);
int** anc;

vector<int> lg2(1+maxN);

void dfs(int u)
{
    curr++;
    ind[u] = curr;
    order.push_back(u);

    for(int e = 0; e < (int)edge[u].size(); e++)
    {
        int v = edge[u][e];
        long long w = wt[u][e];

        if(ind[v] != -1) continue;

        depth[v] = depth[u] + 1;
        dist0[v] = dist0[u] + w;
        parent[v] = u;

        dfs(v);
    }
}

int access_anc(int u, int e)
{
    if(e >= lg2[depth[u]]) return 0;
    else return anc[u][e];
}

void Init(int N_, int A[], int B[], int D[])
{
    N = N_;
    lg2[0] = 1;
    lg2[1] = 1;
    for(int i = 1; i <= N; i++) lg2[i] = 1 + lg2[i/2];

    for(int e = 0; e < N-1; e++)
    {
        edge[ A[e] ].push_back( B[e] );
        wt[ A[e] ].push_back( D[e] );

        edge[ B[e] ].push_back( A[e] );
        wt[ B[e] ].push_back( D[e] );
    }

    parent[0] = 0;
    dfs(0);

    // cerr << "dfs done\n";

    anc = new int*[N];
    for(int i = 0; i < N; i++) anc[i] = new int[lg2[depth[i]]];

    for(int i = 0; i < N; i++) anc[i][0] = parent[i];

    // cerr << "check 1\n";

    for(int e = 1; e < logN; e++)
    {
        // cerr << "e = " << e << '\n';
        for(int i = 0; i < N; i++)
        {
            // cerr << "i = " << i << '\n';
            if(e < lg2[depth[i]])
            {
                // cerr << "case X\n";
                anc[i][e] = access_anc( access_anc(i, e-1) , e-1);
            }
        }
    }
    // cerr << "check 2\n";
}

int getAnc(int u, int d)
{
    for(int e = logN-1; e >= 0; e--)
        if((1 << e) & d)
            u = access_anc(u, e);

    return u;
}

int lca(int u, int v)
{
    if(depth[u] > depth[v]) swap(u, v);

    for(int e = logN-1; e >= 0; e--)
        if((1 << e) & (depth[v] - depth[u]))
            v = access_anc(v, e);

    if(u == v) return u;

    for(int e = logN-1; e >= 0; e--)
    {
        if(access_anc(u, e) != access_anc(v, e))
        {
            u = access_anc(u, e);
            v = access_anc(v, e);
        }
    }
    u = access_anc(u, 0);
    v = access_anc(v, 0);
    return u;
}

int S;
int* X;
int T;
int* Y;
vector<int> Z;

vector<int> new_edge[1'200'000];
vector<long long> new_wt[1'200'000];

int act(int i) //actual
{
    if(i < S) return X[i];
    else if(i < S+T) return Y[i-S];
    else return Z[i-S-T];
}

void add_new_edge(int u, int v, long long d)
{
    new_edge[u].push_back(v);
    new_wt[u].push_back(d);

    new_edge[v].push_back(u);
    new_wt[v].push_back(d);
}


vector<long long> src_dist(1'200'000);

struct pos
{
    int i;
};

bool operator < (pos A, pos B)
{
    if(src_dist[A.i] == src_dist[B.i]) return A.i < B.i;
    return src_dist[A.i] < src_dist[B.i];
}





long long Query(int S_, int X_[], int T_, int Y_[])
{
    S = S_;
    T = T_;

    // X = vector<int>(S);
    // for(int i = 0; i < S; i++) X[i] = X_[i];

    // Y = vector<int>(T);
    // for(int i = 0; i < T; i++) Y[i] = Y_[i];

    X = X_;
    Y = Y_;

    Z.clear();


    vector<int> V(S+T);
    for(int i = 0; i < S+T; i++) V[i] = i;
    sort(V.begin(), V.end(), [] (int i, int j)
    {
        return ind[act(i)] < ind[act(j)];
    });


    for(int i = 0; i+1 < S+T; i++)
    {
        Z.push_back(lca(act(V[i]), act(V[i+1])));
        V.push_back(S+T+i);
    }
    sort(V.begin(), V.end(), [] (int i, int j)
    {
        return ind[act(i)] < ind[act(j)];
    });

    int Q = (int)V.size();


    vector<int> st(1, V[0]);
    for(int i = 1; i < Q; i++)
    {
        while(act(st.back()) != getAnc(act(V[i]), depth[act(V[i])] - depth[act(st.back())]))
            st.pop_back();

        add_new_edge(V[i], st.back(), dist0[act(V[i])] - dist0[act(st.back())]);

        st.push_back(V[i]);
    }


    for(int i = 0; i < S; i++) src_dist[i] = 0;
    for(int i = S; i < Q; i++) src_dist[i] = INF;

    queue<pos> tbv;
    for(int i = 0; i < S; i++) tbv.push(pos{i});

    while(!tbv.empty())
    {
        int u = tbv.front().i;
        tbv.pop();

        for(int e = 0; e < (int)new_edge[u].size(); e++)
        {
            int v = new_edge[u][e];
            long long w = new_wt[u][e];
            if(src_dist[v] > src_dist[u] + w)
            {
                src_dist[v] = src_dist[u] + w;
                tbv.push(pos{v});
            }
        }
    }

    long long res = INF;
    for(int i = S; i < S+T; i++)
        res = min(res, src_dist[i]);


    // X.clear();
    // Y.clear();
    Z.clear();
    for(int i = 0; i < Q; i++)
    {
        new_edge[i].clear();
        new_wt[i].clear();
    }

    return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 101824 KB Output is correct
2 Correct 2481 ms 111208 KB Output is correct
3 Correct 2337 ms 110248 KB Output is correct
4 Correct 2213 ms 111516 KB Output is correct
5 Correct 2416 ms 110816 KB Output is correct
6 Correct 1616 ms 136148 KB Output is correct
7 Correct 2292 ms 110284 KB Output is correct
8 Correct 2196 ms 111304 KB Output is correct
9 Correct 2434 ms 110752 KB Output is correct
10 Correct 1581 ms 136088 KB Output is correct
11 Correct 2279 ms 110080 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 101444 KB Output is correct
2 Correct 2667 ms 170856 KB Output is correct
3 Correct 4722 ms 193544 KB Output is correct
4 Correct 1732 ms 172896 KB Output is correct
5 Correct 4351 ms 222068 KB Output is correct
6 Correct 4996 ms 194100 KB Output is correct
7 Correct 3672 ms 127496 KB Output is correct
8 Correct 1582 ms 136012 KB Output is correct
9 Correct 3330 ms 131456 KB Output is correct
10 Correct 3640 ms 129120 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 101824 KB Output is correct
2 Correct 2481 ms 111208 KB Output is correct
3 Correct 2337 ms 110248 KB Output is correct
4 Correct 2213 ms 111516 KB Output is correct
5 Correct 2416 ms 110816 KB Output is correct
6 Correct 1616 ms 136148 KB Output is correct
7 Correct 2292 ms 110284 KB Output is correct
8 Correct 2196 ms 111304 KB Output is correct
9 Correct 2434 ms 110752 KB Output is correct
10 Correct 1581 ms 136088 KB Output is correct
11 Correct 2279 ms 110080 KB Output is correct
12 Correct 64 ms 101444 KB Output is correct
13 Correct 2667 ms 170856 KB Output is correct
14 Correct 4722 ms 193544 KB Output is correct
15 Correct 1732 ms 172896 KB Output is correct
16 Correct 4351 ms 222068 KB Output is correct
17 Correct 4996 ms 194100 KB Output is correct
18 Correct 3672 ms 127496 KB Output is correct
19 Correct 1582 ms 136012 KB Output is correct
20 Correct 3330 ms 131456 KB Output is correct
21 Correct 3640 ms 129120 KB Output is correct
22 Correct 7253 ms 192764 KB Output is correct
23 Correct 5446 ms 220448 KB Output is correct
24 Correct 7096 ms 235176 KB Output is correct
25 Correct 6951 ms 239476 KB Output is correct
26 Correct 7077 ms 219148 KB Output is correct
27 Correct 7210 ms 255968 KB Output is correct
28 Correct 3674 ms 236840 KB Output is correct
29 Correct 7470 ms 218680 KB Output is correct
30 Correct 7396 ms 218064 KB Output is correct
31 Correct 7427 ms 218724 KB Output is correct
32 Correct 4478 ms 158648 KB Output is correct
33 Correct 2463 ms 173056 KB Output is correct
34 Correct 3591 ms 136172 KB Output is correct
35 Correct 3274 ms 135744 KB Output is correct
36 Correct 3432 ms 139096 KB Output is correct
37 Correct 3520 ms 138964 KB Output is correct