Submission #855488

#	Time	Username	Problem	Language	Result	Execution time	Memory
855488		RiverFlow	Factories (JOI14_factories)	C++14	100 / 100	5479 ms	211308 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>

#define nl "\n"
#define no "NO"
#define yes "YES"
#define fi first
#define se second
#define vec vector
#define task "main"
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
#define unq(x) sort(all(x)); x.resize(unique(all(x)) - x.begin())

using namespace std;

template<typename U, typename V> bool maxi(U &a, V b) {
    if (a < b) { a = b; return 1; } return 0;
}
template<typename U, typename V> bool mini(U &a, V b) {
    if (a > b) { a = b; return 1; } return 0;
}

const int N = (int)5e5 + 9;
const int mod = (int)1e9 + 7;

const long long INF = (long long)1e16;

template<typename T>
struct segment_tree {
    int n; vector<T> t;
    segment_tree () {};
    segment_tree (int _n) {
        n = _n; t.resize(n * 4 + 7);
        FOR(i, 1, 4 * n) t[i] = INF;
    }
    void refine(int id) {
        t[id] = min(t[id << 1], t[id << 1 | 1]);
    }
    void update(int id, int l, int r, int p, long long val) {
        if (l == r) return void(t[id] = val);
        int m = (l + r) >> 1;
        if (p <= m) update(id << 1, l, m, p, val);
        else        update(id << 1 | 1, m + 1, r, p, val);
        refine(id);
    }
    void update(int p, long long val) {
        update(1, 1, n, p, val);
    }
    T get(int id, int l, int r, int u, int v) {
        if (l > v || r < u) return INF;
        if (l >= u && r <= v) return t[id];
        int m = (l + r) / 2;
        return min(get(id << 1, l, m, u, v), get(id << 1 | 1, m + 1, r, u, v));
    }
    T get(int l, int r) {
        return get(1, 1, n, l, r);
    }
};

const int LG = 19;

int h[N], par[N][LG + 1], see[N], tin[N], tout[N];

long long dist[N];

vector<ii> g[N];

int lca(int u, int v) {
    if (u == v) return u;
    if (h[u] < h[v]) swap(u, v);
    FOD(j, LG, 0) if (h[par[u][j]] >= h[v]) u = par[u][j];
    if (u == v) return u;
    FOD(j, LG, 0) if (par[u][j] != par[v][j])
        u = par[u][j], v = par[v][j];
    return par[u][0];
}

segment_tree<long long> A, B;

long long Query(int x, int a[], int y, int b[]) {
    FOR(i, 0, x - 1) ++a[i], see[a[i]] = 1;
    FOR(j, 0, y - 1) ++b[j];
    bool ok = 0; FOR(j, 0, y - 1) if (see[b[j]]) {
        ok = 1; break ;
    }
    FOR(i, 0, x - 1) see[a[i]] = 0;
    if (ok) {
        return 0;
    }
    vector<int> p;
    FOR(i, 0, x - 1) {
        p.push_back(a[i]);
    }
    FOR(i, 0, y - 1) {
        p.push_back(b[i]);
    }
    sort(p.begin(), p.end(), [&](int &x, int &y) {
        return tin[x] < tin[y];
    });
    vec<int> lc;
    FOR(i, 0, sz(p) - 2)
        lc.push_back(lca(p[i], p[i + 1]));
    unq(lc);
    FOR(i, 0, x - 1) {
        A.update(tin[a[i]], dist[a[i]]);
    }
    FOR(i, 0, y - 1) {
        B.update(tin[b[i]], dist[b[i]]);
    }
    long long ans = INF;
    for(int j : lc) {
        long long k1 = A.get(tin[j], tout[j]);
        if (k1 == INF) continue ; k1 -= dist[j];
        long long k2 = B.get(tin[j], tout[j]);
        if (k2 == INF) continue ; k2 -= dist[j];
        ans = min(ans, k1 + k2);
    }
    FOR(i, 0, x - 1) {
        A.update(tin[a[i]], INF);
    }
    FOR(i, 0, y - 1) {
        B.update(tin[b[i]], INF);
    }
    return ans;
}

int _timer = 0;

void dfs(int u, int p) {
    tin[u] = ++_timer;
    FOR(j, 1, LG) par[u][j] = par[par[u][j-1]][j-1];
    for(auto v : g[u]) if (v.fi ^ p) {
        dist[v.fi] = dist[u] + v.se;
        par[v.fi][0] = u;
        h[v.fi] = h[u] + 1;
        dfs(v.fi, u);
    }
    tout[u] = ++_timer;
}

void Init(int n, int x[], int y[], int w[]) {
    FOR(i, 0, n - 2) {
        ++x[i], ++y[i];
        g[x[i]].emplace_back(y[i], w[i]);
        g[y[i]].emplace_back(x[i], w[i]);
    }
    A = segment_tree<long long> (2 * n);
    B = segment_tree<long long> (2 * n);
    dfs(1, 0); h[0] = -1;
}



/*     Let the river flows naturally     */

Compilation message (stderr)

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:119:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  119 |         if (k1 == INF) continue ; k1 -= dist[j];
      |         ^~
factories.cpp:119:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  119 |         if (k1 == INF) continue ; k1 -= dist[j];
      |                                   ^~
factories.cpp:121:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  121 |         if (k2 == INF) continue ; k2 -= dist[j];
      |         ^~
factories.cpp:121:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  121 |         if (k2 == INF) continue ; k2 -= dist[j];
      |                                   ^~

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67