oj.uz

Submission #113450

# Submission time Handle Problem Language Result Execution time Memory
113450 2019-05-25T15:30:07 Z popovicirobert Factories (JOI14_factories) C++14
100 / 100
 4790 ms 224356 KB 
#include "factories.h"
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const ll INF = 1e18;

struct SegTree {

    vector <ll> aint;
    int n;

    inline void init(int _n) {
        n = _n;
        aint.resize(2 * n, INF);
    }

    inline void refresh(int nod) {
        aint[nod] = min(aint[2 * nod], aint[2 * nod + 1]);
    }

    inline void update(int pos, ll val) {
        pos += n;
        aint[pos] = val;

        while(pos > 1) {
            pos >>= 1;
            refresh(pos);
        }

    }

    inline ll query(int l, int r) {
        l += n, r += n;

        ll ans = INF;

        while(l < r) {
            if(l & 1) {
                ans = min(ans, aint[l]);
                l++;
            }
            if(r & 1) {
                r--;
                ans = min(ans, aint[r]);
            }

            l >>= 1;
            r >>= 1;
        }

        return ans;
    }

}sta, stb;

vector < vector < pair <int, int> > > g;
vector <ll> dst;
vector <int> idl, idr, first, lvl, lg;

vector < vector <int> > rmq;

void dfs(int nod, int par, int &id, int &sz) {

    lvl[nod] = lvl[par] + 1;
    idl[nod] = id++;

    rmq[++sz][0] = nod;
    first[nod] = sz;

    for(auto it : g[nod]) {
        if(it.first != par) {
            dst[it.first] = dst[nod] + it.second;
            dfs(it.first, nod, id, sz);
            rmq[++sz][0] = nod;
        }
    }

    idr[nod] = id;
}

int n;

void Init(int _n, int A[], int B[], int D[]) {

    n = _n;

    g.resize(n + 1);
    int i;

    for(i = 0; i < n - 1; i++) {
        A[i]++, B[i]++;
        g[A[i]].push_back({B[i], D[i]});
        g[B[i]].push_back({A[i], D[i]});
    }

    dst.resize(n + 1), idl.resize(n + 1), idr.resize(n + 1), first.resize(n + 1), lvl.resize(n + 1);
    rmq.resize(2 * n + 1, vector <int>(20));

    int id = 0, sz = 0;
    dfs(1, 0, id, sz);

    lg.resize(sz + 1);
    for(i = 2; i <= sz; i++) {
        lg[i] = lg[i >> 1] + 1;
    }

    for(int bit = 1; (1 << bit) <= sz; bit++) {
        for(i = 1; i + (1 << bit) <= sz + 1; i++) {
            int a = rmq[i][bit - 1], b = rmq[i + (1 << (bit - 1))][bit - 1];

            if(lvl[a] < lvl[b]) {
                rmq[i][bit] = a;
            }
            else {
                rmq[i][bit] = b;
            }
        }
    }

    sta.init(n), stb.init(n);

}

inline int get(int x, int y) {
    x = first[x], y = first[y];
    if(x > y) swap(x, y);

    int bit = lg[y - x + 1];

    if(lvl[rmq[x][bit]] < lvl[rmq[y - (1 << bit) + 1][bit]]) {
        return rmq[x][bit];
    }
    return rmq[y - (1 << bit) + 1][bit];
}



ll Query(int S, int X[], int T, int Y[]) {

    int i;

    for(i = 0; i < S; i++) {
        X[i]++;
        sta.update(idl[X[i]], dst[X[i]]);
    }
    for(i = 0; i < T; i++) {
        Y[i]++;
        stb.update(idl[Y[i]], dst[Y[i]]);
    }

    static vector <int> nodes;
    nodes.clear();

    for(i = 0; i < S; i++) {
        nodes.push_back(X[i]);
    }
    for(i = 0; i < T; i++) {
        nodes.push_back(Y[i]);
    }

    sort(nodes.begin(), nodes.end(), [&](const int &a, const int &b) {

                return idl[a] < idl[b];

         });

    ll ans = INF;

    for(i = 0; i + 1 < nodes.size(); i++) {
        int nod = get(nodes[i], nodes[i + 1]);

        ans = min(ans, sta.query(idl[nod], idr[nod]) + stb.query(idl[nod], idr[nod]) - 2 * dst[nod]);
    }

    for(i = 0; i < S; i++) {
        sta.update(idl[X[i]], INF);
    }
    for(i = 0; i < T; i++) {
        stb.update(idl[Y[i]], INF);
    }

    return ans;
}

Compilation message

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:171:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i = 0; i + 1 < nodes.size(); i++) {
                ~~~~~~^~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1024 KB Output is correct
2 Correct 731 ms 11512 KB Output is correct
3 Correct 813 ms 11512 KB Output is correct
4 Correct 769 ms 11548 KB Output is correct
5 Correct 750 ms 11900 KB Output is correct
6 Correct 592 ms 11536 KB Output is correct
7 Correct 893 ms 11564 KB Output is correct
8 Correct 819 ms 11456 KB Output is correct
9 Correct 736 ms 11752 KB Output is correct
10 Correct 599 ms 11372 KB Output is correct
11 Correct 871 ms 11468 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 640 KB Output is correct
2 Correct 2826 ms 192880 KB Output is correct
3 Correct 3127 ms 195844 KB Output is correct
4 Correct 2594 ms 194116 KB Output is correct
5 Correct 3116 ms 224356 KB Output is correct
6 Correct 3360 ms 197204 KB Output is correct
7 Correct 2658 ms 48512 KB Output is correct
8 Correct 2146 ms 49084 KB Output is correct
9 Correct 2428 ms 52536 KB Output is correct
10 Correct 2438 ms 49688 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1024 KB Output is correct
2 Correct 731 ms 11512 KB Output is correct
3 Correct 813 ms 11512 KB Output is correct
4 Correct 769 ms 11548 KB Output is correct
5 Correct 750 ms 11900 KB Output is correct
6 Correct 592 ms 11536 KB Output is correct
7 Correct 893 ms 11564 KB Output is correct
8 Correct 819 ms 11456 KB Output is correct
9 Correct 736 ms 11752 KB Output is correct
10 Correct 599 ms 11372 KB Output is correct
11 Correct 871 ms 11468 KB Output is correct
12 Correct 4 ms 640 KB Output is correct
13 Correct 2826 ms 192880 KB Output is correct
14 Correct 3127 ms 195844 KB Output is correct
15 Correct 2594 ms 194116 KB Output is correct
16 Correct 3116 ms 224356 KB Output is correct
17 Correct 3360 ms 197204 KB Output is correct
18 Correct 2658 ms 48512 KB Output is correct
19 Correct 2146 ms 49084 KB Output is correct
20 Correct 2428 ms 52536 KB Output is correct
21 Correct 2438 ms 49688 KB Output is correct
22 Correct 4133 ms 195352 KB Output is correct
23 Correct 3996 ms 197856 KB Output is correct
24 Correct 4723 ms 198220 KB Output is correct
25 Correct 4726 ms 201748 KB Output is correct
26 Correct 4507 ms 198036 KB Output is correct
27 Correct 4661 ms 221468 KB Output is correct
28 Correct 3848 ms 199052 KB Output is correct
29 Correct 4790 ms 197528 KB Output is correct
30 Correct 4531 ms 196988 KB Output is correct
31 Correct 4572 ms 197624 KB Output is correct
32 Correct 1943 ms 54196 KB Output is correct
33 Correct 1610 ms 50244 KB Output is correct
34 Correct 2005 ms 46588 KB Output is correct
35 Correct 2041 ms 46376 KB Output is correct
36 Correct 2413 ms 47092 KB Output is correct
37 Correct 2246 ms 47088 KB Output is correct