Submission #113450

#	Time	Username	Problem	Language	Result	Execution time	Memory
113450		popovicirobert	Factories (JOI14_factories)	C++14	100 / 100	4790 ms	224356 KiB

factories

#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 (stderr)

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 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67