Submission #1248513

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248513		nrg_studio	Factories (JOI14_factories)	C++20	Compilation error	0 ms	0 KiB

factories

#include <bits/stdc++.h>
//#include "factories.h"
using namespace std;

#define ll long long
#define pb push_back
#define pii pair<int,int>
#define f first
#define s second
#define chmin(a, b) a = min(a,b)
#define chmax(a, b) a = max(a,b)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define all(x) x.begin(),x.end()
#define vec vector

const int N = 5e5;
int sz[N];
bool del[N] = {false};
vec<pair<int,int>> adj[N];

//vec<pair<int,ll>> anc[N];
pair<int,ll> tree[N];
ll dist[N];

int upd_sizes(int cur, int par=-1) {
    sz[cur] = 1;
    for (auto[x,w] : adj[cur]) {
        if (x!=par && !del[x]) {
            sz[cur] += upd_sizes(x,cur);
        }
    }
    return sz[cur];
}
int find_cent(int cur, int n2, int par=-1) {
    for (auto[x,w] : adj[cur]) {
        if (x!=par && !del[x]) {
            if (sz[cur]>n2/2) {return find_cent(x,n2,cur);}
        }
    } return cur;
}
void upd_dist(int cur, int cent, ll d, int par=-1) {
    if (cur!=cent) {tree[cur].second = d;}
    for (auto[x,w] : adj[cur]) {
        if (x!=par && !del[x]) {
            upd_dist(x,cent,d+w,cur);
        }
    }
}
void decomp(int cur=0, int par=-1) {
    int cent = find_cent(cur,upd_sizes(cur));
    del[cent] = true;
    tree[cent].first = par;
    upd_dist(cent,cent,0);

    for (auto[x,w] : adj[cent]) {
        if (!del[x]) {
            decomp(x,cent);
        }
    }
}

void Init(int n, int a[], int b[], int d[]) {
    for (int i=0;i<n-1;i++) {
        adj[a[i]].pb({b[i],d[i]});
        adj[b[i]].pb({a[i],d[i]});
    }
    decomp();
    for (int i=0;i<n;i++) {dist[i] = 1e18;}
    //for (int i=0;i<n;i++) {cout << tree[i].first << '\n';}
}

ll Query(int s, int x[], int t, int y[]) {
    for (int i=0;i<s;i++) {
        for (ll x2=x[i],d=0;x2!=-1;d+=tree[x2].second,x2=tree[x2].first) {
            chmin(dist[x2],d);
        }
        //while (x2!=-1) {chmin(dist[x],)}
        //for (auto[c,w] : anc[x[i]]) {chmin(dist[c],w);}
    }
    ll ans = 1e18;
    for (int i=0;i<t;i++) {
        for (ll x2=y[i],d=0;x2!=-1;d+=tree[x2].second,x2=tree[x2].first) {
            chmin(ans,d+dist[x2]);
        }
        //for (auto[c,w] : anc[y[i]]) {chmin(ans,w+dist[c]);}
    }

    for (int i=0;i<s;i++) {
        for (ll x2=x[i],d=0;x2!=-1;d+=tree[x2].second,x2=tree[x2].first) {
            dist[x2] = 1e18;
        }
        //for (auto[c,w] : anc[x[i]]) {dist[c] = 1e18;}
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    int n, q; cin >> n >> q;
    int a[n], b[n], d[n];
    for (int i=0;i<n-1;i++) {cin >> a[i] >> b[i] >> d[i];}
    Init(n,a,b,d);
    //return 0;
    
    for (int i=0;i<q;i++) {
        int s, t; cin >> s >> t;
        int x[s], y[t];
        for (int i=0;i<s;i++) {cin >> x[i];}
        for (int i=0;i<t;i++) {cin >> y[i];}
        cout << Query(s,x,t,y) << '\n';
    }

    /* centroid decomp
    need to rollback updates though
    still (n+q)logn i think

    iterate company 1 (update min dist to anc)
    try each company 2
    reset each in company 1
    */
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccuInqw8.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccpFb4cq.o:factories.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status