Submission #246726

#	Time	Username	Problem	Language	Result	Execution time	Memory
246726		LifeHappen__	Factories (JOI14_factories)	C++14	100 / 100	4305 ms	151784 KiB

factories

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

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef long long ll;
typedef unsigned long long ull;
typedef double db;

#define forinc(a, b, c) for(int a = b, _c = c; a <= _c; ++a)
#define fordec(a, b, c) for(int a = b, _c = c; a >= _c; --a)
#define rep(i, a) forinc(i, 1, a)
#define repv(i, a) forinc(i, 0, a - 1)
#define forv(a, b) for(auto &a : b)

#define ii pair<int, long long>
#define fi first
#define se second
#define reset(f, x) memset(f, x, sizeof(f))
#define all(a) begin(a), end(a)
#define pb push_back
#define eb emplace_back
#define mp make_pair

#define bit(x, i) (x >> (i - 1) & 1ll)
#define on(x, i) (x | (1ll << (i - 1)))
#define off(x, i) (x & ~(1ll << (i - 1)))

const int N = 5e5 + 5;
const int _N = 5005;
const long long INF = 1e16;
int n, que;
vector<ii> ad[N];
int st[N], en[N], id, pd[N][25], dd[N];
long long d[N], ans, pf[N], sf[N];

void Init(int n, int A[], int B[], int D[]) {
    repv(i, n - 1) {
        int u = A[i], v = B[i], c = D[i];
        u++; v++;
        ad[u].eb(v, c);
        ad[v].eb(u, c);
    }
    function<void(int, int)> dfs = [&](int u, int par) {
        st[u] = ++id;
        forinc(i, 1, 20) pd[u][i] = pd[pd[u][i - 1]][i - 1];
        forv(v, ad[u]) if(v.fi != par) {
            pd[v.fi][0] = u;
            d[v.fi] = d[u] + 1ll * v.se;
            dfs(v.fi, u);
        }
        en[u] = ++id;
    };
    dfs(1, 0);
    forinc(i, 1, n) ad[i].clear();
}
int anc(int u, int v) {
    return (st[u] <= st[v] && en[u] >= en[v]) || !u;
}
int lca(int u, int v){
    if(anc(u, v)) return u;
    if(anc(v, u)) return v;
    fordec(i, 20, 0) if(!anc(pd[u][i], v)) u = pd[u][i];
    return pd[u][0];
}
bool cmp(int x, int y) {return make_pair(st[x], en[x]) < make_pair(st[y], en[y]);}
long long dist(int u, int v) {return 1ll * d[u] + 1ll * d[v] - 2ll * d[lca(u, v)];}
long long Query(int s, int S[], int t, int T[]) {
    vector<int> no;
    repv(i, s) no.pb(S[i] + 1), dd[S[i] + 1] = 1;
    repv(i, t) no.pb(T[i] + 1), dd[T[i] + 1] |= 2;
    sort(all(no), cmp);
    repv(i, no.size() - 1) no.pb(lca(no[i], no[i + 1]));
    sort(all(no)); no.erase(unique(all(no)), end(no));
    sort(all(no), cmp);
    stack<int> kek;
    forv(v, no) {
        while(kek.size() && en[v] >= en[kek.top()]) kek.pop();
        if(kek.size()) {
            ad[kek.top()].eb(v, d[v] - d[kek.top()]);
        }
        kek.push(v);
    }
    ans = INF;
    function<void(int)> dfs = [&](int u) {
        long long &x = pf[u], &y = sf[u];
        x = (dd[u] & 1) ? 0 : INF;
        y = (dd[u] & 2) ? 0 : INF;
        forv(v, ad[u]) {
            dfs(v.fi);
            x = min(x, pf[v.fi] + 1ll * v.se);
            y = min(y, sf[v.fi] + 1ll * v.se);
        }
        ans = min(ans, x + y);
    };
    ans = INF;
    dfs(no[0]);
    forv(v, no) pf[v] = sf[v] = dd[v] = 0, ad[v].clear();
    return ans;
}
/*
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    //if(fopen("inp.txt", "r")){
        freopen("inp.txt", "r", stdin);
    //}
    cin >> n >> que;
    static int A[_N], B[_N], D[_N];
    repv(i, n - 1) cin >> A[i] >> B[i] >> D[i];
    Init(n, A, B, D);
    while(que--) {
        int s, t;
        cin >> s >> t;
        static int S[_N], T[_N];
        repv(i, s) cin >> S[i];
        repv(i, t) cin >> T[i];
        cout << Query(s, S, t, T) << '\n';
    }
}
*/

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