Submission #1230724

#TimeUsernameProblemLanguageResultExecution timeMemory
1230724hehebjp123공장들 (JOI14_factories)C++20
Compilation error
0 ms0 KiB
#include <bits/stdc++.h>

#define ll long long
#define pb push_back
#define ii pair<ll,ll>
#define fi first
#define se second
#define all(a) a.begin(),a.end()

using namespace std;


const int N = 5e5 + 5;
const ll inf=1e18;
const int LOG = 20;

vector<ii> v[N];
vector<pair<int, int>> adj[N];
int up[N][LOG];
int depth[N];
ll dist[N];
ll tin[N],tout[N],timer=0;
void dfs(int u, int p) {
    up[u][0] = p;
    for (int i = 1; i < LOG; i++) {
            up[u][i] = up[up[u][i - 1]][i - 1];
    }
    tin[u]=++timer;
    for (auto [v, w] : adj[u]) {
        if (v != p) {
            depth[v] = depth[u] + 1;
            dist[v] = dist[u] + w;
            dfs(v, u);
        }
    }
    tout[u]=timer;
}

int lca(int u, int v) {
    if (depth[u] < depth[v])
        swap(u, v);

    for (int i = LOG - 1; i >= 0; i--)
        if (up[u][i] != -1 && depth[up[u][i]] >= depth[v])
            u = up[u][i];

    if (u == v) return u;

    for (int i = LOG - 1; i >= 0; i--) {
        if (up[u][i] != -1 && up[u][i] != up[v][i]) {
            u = up[u][i];
            v = up[v][i];
        }
    }

    return up[u][0];
}

ll get_dist(int u, int v) {
    int ancestor = lca(u, v);
    return dist[u] + dist[v] - 2 * dist[ancestor];
}
bool sort_tin(ll &a,ll &b)
{
    return (tin[a]<tin[b]);
}
bool is_ancestor(ll u,ll v)
{
    return (tin[u]<=tin[v]&&tout[v]<=tout[u]);
}
ll ans,i,n,q,j,x,y;
ll dp[N];
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> q;
    for (int i = 1; i < n; i++) {
        int x, y, w;
        cin >> x >> y >> w;
        adj[x].pb({y, w});
        adj[y].pb({x, w});
    }
    for(ll i=0;i<LOG;i++)
    up[0][i]=0;
    depth[1] = 0;
    dist[1] = 0;
    dfs(0, 0);
    memset(dp,-1,sizeof(dp));
    vector<bool>visited(n,0);
    while (q--) {
            ans=inf;
        ll s,t;
        cin>>s>>t;
        vector<ll> x(s),y(t);
        for(auto &k:x) {cin>>k;}
        for(auto &k:y) {cin>>k;dp[k]=0;}
        vector<ll>special=x;

        for(auto k:y) special.pb(k);
        sort(all(special),sort_tin);
        vector<ll> node=special;
        for(i=1;i<special.size();i++)
            node.pb(lca(special[i-1],special[i]));
        sort(all(node),sort_tin);
        node.erase(unique(all(node)),node.end());
        stack<ll> st;
        st.push(node[0]);
        for(i=1;i<node.size();i++)
        {
            ll u=node[i];
            while(!is_ancestor(st.top(),u)) st.pop();
            ll x=st.top();
            ll dis=get_dist(u,x);
            //cout<<x<<" "<<u<<" "<<dis<<'\n';
            v[u].pb({x,dis});
            v[x].pb({u,dis});
            st.push(u);
        }
        priority_queue<ii,vector<ii>,greater<ii>>pq;
        for(auto k:x) pq.push({0,k});
        while(1)
        {
            ii top=pq.top();
            pq.pop();
            ll dis=top.fi,u=top.se;
           // cout<<dis<<" "<<u<<'\n';
            if(dp[u]==0)
            {
                ans=dis;
                break;
            }
            if(visited[u]) continue;
            visited[u]=1;
            for(auto [x,d]:v[u])
            pq.push({d+dis,x});
        }
        cout<<ans<<'\n';
        for(auto k:node) {dp[k]=-1;v[k].clear();}
        for(auto k:node) visited[k]=0;
    }

    return 0;
}
/*
7 1
0 1 4
1 2 4
2 3 5
2 4 6
4 5 5
1 6 3
2 2
0 6
3 4

*/

Compilation message (stderr)

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