Submission #1281712

#TimeUsernameProblemLanguageResultExecution timeMemory
1281712dhuyyyyFactories (JOI14_factories)C++20
Compilation error
0 ms0 KiB
#include<bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;

using ll = long long;
using ii = pair<int, int>;
using aa = array<int,3>;

const int N = 5e5+5;

int n, m, q, u, v, c, x, root, k1, k2, res;

int sz[N], dist[N];

bool num[N], vis[N], okay[N];

vector <ii> adj[N], anc[N];

stack <int> st;

void getSize(int u,int p){
    sz[u] = 1;
    for (ii it : adj[u]){
        if (num[it.fi] || it.fi == p) continue;
        getSize(it.fi,u);
        sz[u] += sz[it.fi];
    }
}
int getCentroid(int u,int p,int n){
    for (ii it : adj[u]){
        if (num[it.fi] || it.fi == p) continue;
        if (sz[it.fi] * 2 > n) return getCentroid(it.fi,u,n);
    }
    return u;
}
void dfs(int u,int p,int root,int length){
    anc[u].push_back({root,length});
    for (ii it : adj[u]){
        if (num[it.fi] || it.fi == p) continue;
        dfs(it.fi,u,root,length + it.se);
    }
}
void decompose(int u){
    getSize(u,0);
    m = sz[u];
    root = getCentroid(u,0,m);
    num[root] = 1;
    for (ii it : adj[root]){
        if (num[it.fi]) continue;
        dfs(it.fi,root,root,it.se);
    }
    for (ii it : adj[root]){
        if (num[it.fi]) continue;
        decompose(it.fi);
    }
}
void update(int u){
    for (ii it : anc[u]){
        if (dist[it.fi] > it.se){
            dist[it.fi] = it.se;
            if (!vis[it.fi]){
                st.push(it.fi);
                vis[it.fi] = 1;
            }
        }
    }
}
void get(int u){
    for (ii it : anc[u]){
        res = min(res,dist[it.fi] + it.se);
    }
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin >> n >> q;
    for (int i = 1; i < n; i++){
        cin >> u >> v >> c;
        u++; v++;
        adj[u].push_back({v,c});
        adj[v].push_back({u,c});
    }
    decompose(1);
    for (int i = 1; i <= n; i++) dist[i] = 1e18;
    while (q--){
        res = (int)1e18;
        cin >> k1 >> k2;
        for (int i = 1; i <= k1; i++){
            cin >> x;
            x++;
            dist[x] = 0;
            update(x);
            st.push(x);
        }
        for (int i = 1; i <= k2; i++){
            cin >> x;
            x++;
            res = min(res,dist[x]);
            get(x);
        }
        cout << res << '\n';
        while (!st.empty()){
            vis[st.top()] = 1;
            dist[st.top()] = 1e18;
            st.pop();
        }
    }
    return 0;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccVmsnjb.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cccwL47S.o:factories.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccVmsnjb.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