Submission #246709

#	Time	Username	Problem	Language	Result	Execution time	Memory
246709		LifeHappen__	Factories (JOI14_factories)	C++14	Compilation error	0 ms	0 KiB

factories

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

using namespace std;

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

#define int long long

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, int>
#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 INF = 1e18;
int n, que, dep[N], pd[N][32], d[N], in[N], id, out[N], dd[N], s, t;
int pf[N], sf[N], ans;
int st[N], top;
vector <ii> ad[N];
vector <ii> adj[N];
vector <int> del;

void Init(int _n, int A[], int B[], int D[]) {
    n = _n;
    forinc(i, 0, n - 2) {
        int u = A[i], v = B[i], c = D[i];
        u++; v++;
        ad[u].eb(v, c);
        ad[v].eb(u, c);
    }
}
void dfs(int u, int par) {
    in[u] = ++id;
    forinc(i, 1, log2(n)) pd[u][i] = pd[pd[u][i - 1]][i - 1];
    forv(v, ad[u]) if(v.fi != par) {
        pd[v.fi][0] = u;
        dep[v.fi] = dep[u] + 1;
        d[v.fi] = d[u] + v.se;
        dfs(v.fi, u);
    }
    out[u] = ++id;
}
int lca(int u, int v) {
    if(dep[u] < dep[v]) swap(u, v);
    int dif = dep[u] - dep[v];
    fordec(i, log2(n), 0) if(dif >> i & 1) u = pd[u][i];
    if(u == v) return u;
    fordec(i, log2(n), 0) if(pd[u][i] != pd[v][i]) u = pd[u][i], v = pd[v][i];
    return pd[u][0];
}
bool cmp(int x, int y) {
    return in[x] < in[y];
}
int dist(int u, int v) {
    int par = lca(u, v);
    return d[u] + d[v] - 2 * d[par];
}
void dfs1(int u, int par) {
    int &x = pf[u], &y = sf[u];
    x = dd[u]&1 ? 0 : INF, y = dd[u]&2 ? 0 : INF;
    forv(v, adj[u]) {
        if(v.fi != par) {
            dfs1(v.fi, u);
            x = min(x, pf[v.fi] + v.se);
            y = min(y, sf[v.fi] + v.se);
        }
    }
    ans = min(ans, x + y);
}
long long Query(int _s, int X[], int _t, int Y[]) {
    ans = INF;
    s = _s, t  = _t;
    vector <int> node;
    forinc(i, 0, _s - 1) {
        int v = X[i];
        v++, dd[v] = 1, node.pb(v);
    }
    forinc(i, 0, _t - 1) {
        int v = Y[i];
        v++, dd[v] |= 2, node.pb(v);
    }
    sort(all(node), [](int x, int y){return ii(st[x],out[x])<ii(st[y],out[y]);});
    forinc(i, 0, node.size() - 2) node.pb(lca(node[i], node[i + 1]));
    sort(all(node)); node.erase(unique(all(node)), end(node));
    sort(all(node), cmp);
    top = 0;
    forinc(i, 0, node.size() - 1) {
        while(top && out[node[i]] >= out[node[st[top]]]) top--;
        if(top) {
            int u = node[i], v = node[st[top]];
            adj[u].eb(v, dist(u, v));
            adj[v].eb(u, dist(v, u));
        }
        st[++top] = i;
    }
    dfs1(node[0], -1);
    forv(w, node) pf[w] = sf[w] = dd[w] = 0, adj[w].clear();
    return ans;
}
/*
signed main() {
    ios_base::sync_with_stdio(false);
    if(fopen("inp.txt", "r")) {
        freopen("inp.txt", "r", stdin);
        //freopen("out.txt", "w", stdout);
    }
    int _n, que;
    static int a[5000], b[5000], c[5000];
    cin >> _n >> que;
    forinc(i, 0, _n - 2) {
        int u, v, c;
        cin >> a[i] >> b[i] >> d[i];
    }
    Init(_n, a, b, d);
    dfs(1, -1);
    while(que--) {
        int _s, _t, v;
        cin >> _s >> _t;
        static int p[5005], q[5005];
        forinc(i, 0, _s - 1) cin >> v, p[i] = v;
        forinc(i, 0, _t - 1) cin >> v, q[i] = v;
        cout << Query(_s, p, _t, q) << '\n';
    }
}
*/

Compilation message (stderr)

/tmp/ccoeKn1w.o: In function `main':
grader.cpp:(.text.startup+0x36d): undefined reference to `Init(int, int*, int*, int*)'
grader.cpp:(.text.startup+0x3ed): undefined reference to `Query(int, int*, int, int*)'
collect2: error: ld returned 1 exit status