Submission #1279193

#TimeUsernameProblemLanguageResultExecution timeMemory
1279193hiepsimauhongFactories (JOI14_factories)C++20
Compilation error
0 ms0 KiB
#include <bits/stdc++.h>

using namespace std;

#define int long long

#define FOR(I, L, R) for(int I(L) ; I <= (int)R ; ++I)
#define FOD(I, R, L) for(int I(R) ; I >= (int)L ; --I)
#define FOA(I, A) for(auto &I : A)

#define print(A,L,R) FOR(OK, L, R){if(A[OK]<=-oo / 10||A[OK]>=oo)cout<<"- ";else cout<<A[OK]<<' ';}cout<<'\n';
#define prints(A) FOA(OK, A){cout<<OK<<' ';}cout << '\n';
#define printz(A,L,R) FOR(OK, 0, L){FOR(KO, 0, R){if(A[OK][KO]>-oo&&A[OK][KO]<oo)cout<<A[OK][KO]<<' ';else cout << "- ";} cout << '\n';}cout << '\n';

#define fs first
#define sd second
#define ii pair<int,int>
#define iii pair<int, ii>
#define all(A) A.begin(), A.end()
#define quickly cin.tie(0) -> ios_base::sync_with_stdio(0);

const int N = 5e5 + 5;
const int mod = 1e9 + 7;
const int oo = 1e18;

int n, q;
vector<ii> g[N];

struct LCA{
        int up[N][21], high[N], h[N];

        void build(int u, int par){
                FOA(e, g[u]){
                        int v = e.fs, w = e.sd;

                        if(v == par){
                                continue;
                        }
                        h[v] = h[u] + 1;
                        high[v] = high[u] + w;
                        up[v][0] = u;

                        FOR(i, 1, 20){
                                up[v][i] = up[up[v][i - 1]][i - 1];
                        }

                        build(v, u);
                }
        }

        int get(int u, int v){
                if(h[v] < h[u]) swap(u, v);

                int c = h[v] - h[u];

                FOR(i, 0, 20){
                        if(c >> i & 1){
                                v = up[v][i];
                        }
                }

                if(u == v) return u;

                FOD(i, 20, 0){
                        if(up[v][i] == up[u][i]){
                                continue;
                        }
                        v = up[v][i];
                        u = up[u][i];
                }

                return up[v][0];
        }

        int path(int u, int v){
                return high[u] + high[v] - 2 * high[get(u, v)];
        }
} lca;

namespace Centroid{
        int sz[N], near[N], parent[N];
        bool cen[N];
        vector<int> ing[N];

        void DFS(int u, int par){
                sz[u] = 1;

                FOA(e, g[u]){
                        int v = e.fs;
                        if(v == par || cen[v]){
                                continue;
                        }
                        DFS(v, u);

                        sz[u] += sz[v];
                }
        }

        int find_centroid(int u, int par, int mx){
                FOA(e, g[u]){
                        int v = e.fs;
                        if(v == par || cen[v]){
                                continue;
                        }

                        if(mx / 2 < sz[v]){
                                return find_centroid(v, u, mx);
                        }
                }
                return u;
        }

        void tree(int u, int pre){
                DFS(u, -1);
                int centroid = find_centroid(u, -1, sz[u]);
                cen[centroid] = 1;

                ing[pre].push_back(centroid);
                parent[centroid] = pre;

                FOA(e, g[centroid]){
                        int v = e.fs;
                        if(!cen[v]){
                                tree(v, centroid);
                        }
                }
        }

        void update(int u){
                int v = u;

                while(v != 0){
                        near[v] = min(near[v], lca.path(u, v));
                        v = parent[v];
                }
        }

        void del(int u){
                int v = u;

                while(v != 0){
                        near[v] = oo;
                        v = parent[v];
                }
        }

        int query(int u){
                int v = u;
                int res = oo;

                while(v != 0){
                        res = min(res, near[v] + lca.path(u, v));
                        v = parent[v];
                }

                return res;
        }

} using namespace Centroid;

signed main(){ quickly
        cin >> n >> q;

        FOR(i, 1, n - 1){
                int u, v, w;
                cin >> u >> v >> w;

                ++u; ++v;
                g[u].push_back({v, w});
                g[v].push_back({u, w});
        }

        lca.build(1, -1);
        tree(1, 0);

        FOR(i, 1, n){
                del(i);
        }

        while(q--){
                int s, t;
                cin >> s >> t;

                vector<int> left, right;
                int ans = oo;

                FOR(i, 1, s){
                        int u; cin >> u;
                        ++u;
                        left.push_back(u);
                        update(u);
                }

                FOR(i, 1, t){
                        int u; cin >> u;
                        ++u;
                        right.push_back(u);
                        ans = min(ans, query(u));
                }

                cout << ans << '\n';

                FOA(i, left){
                        del(i);
                }
        }
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccWJbI6W.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc4o3FdM.o:factories.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccWJbI6W.o: in function `main':
grader.cpp:(.text.startup+0x3b0): undefined reference to `Init(int, int*, int*, int*)'
/usr/bin/ld: grader.cpp:(.text.startup+0x43b): undefined reference to `Query(int, int*, int, int*)'
collect2: error: ld returned 1 exit status