Submission #1317230

#TimeUsernameProblemLanguageResultExecution timeMemory
1317230h1drogenFactories (JOI14_factories)C++17
Compilation error
0 ms0 KiB
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll unsigned long long
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define f first
#define s second  
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define imp cout<<-1<<"\n"
#define pb push_back
#define pii pair<int,int>
#define piii pair<int,pair<int,int>>
#define ls v<<1
#define rs v<<1|1
#define fast ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ptree tree *
const int mod=998244353;
const int INF = 1e18;
const int sqr=317;
const int N=5e5+500;
mt19937 rng(12345312);
vector<vector<pii>>g;
vector<vector<int>>gr;
vector<int>sz;
vector<int>best;
vector<int>dp;
vector<int>tin;
vector<int>tout;
vector<int>us;
int up[21][N];
int tim=0;
vector<map<int,int>>cent;
void dfs(int v,int p,int sum){
    tin[v]=tim++;
    dp[v]=sum;
    up[0][v]=p;
    for(int i=1;i<=20;i++){
        up[i][v]=up[i-1][up[i-1][v]];
    }
    for(auto [to,c]:g[v]){
        if(to!=p){
            dfs(to,v,sum+c);
        }
    }
    tout[v]=tim;
}
void precalc(int v,int p){
    sz[v]=1;
    for(auto [to,c]:g[v]){
        if(to!=p and !us[to]){
            precalc(to,v);
            sz[v]+=sz[to];
        }
    }
}
int get(int v,int p,int n){
    for(auto k:g[v]){
        if(sz[k.f]>n/2 and k.f!=p and !us[k.f])
            return get(k.f,v,n);
    }
    return v;
}
bool check(int a,int b){
    return tin[a]<=tin[b] and tout[b]<=tout[a];
}
int lca(int a,int b){
    if(check(a,b)) return a;
    if(check(b,a)) return b;
    for(int i=20;i>=0;i--){
        if(!check(up[i][a],b)) 
            a=up[i][a];
    }
    return up[0][a];
}
int dist(int a,int b){
    return dp[a]+dp[b]-dp[lca(a,b)]*2;
}
vector<int>par;
void build(int v,int p){
	precalc(v,-1);
	int c=get(v,-1,sz[v]);
	us[c]=1;
	par[c]=p;
	for(auto k:g[c]){
		if(!us[k.f]){
			build(k.f,c);
		}
	}
}
void upd(int v,int x){
	best[v]=min(dist(v,x),best[v]);
	if(par[v]<0)
		return;
	upd(par[v],x);
}
void nulify(int v,int x){
	best[v]=1e18;
	if(par[v]<0)
		return;
	nulify(par[v],x);
}
int ans=1e18;
void res(int v,int x){
	ans=min(dist(v,x)+best[v],ans);
	if(par[v]<0)
		return;
	res(par[v],x);
}
void solve(){
    int n,m;
    cin>>n>>m;
    g.resize(n+1);
    par.resize(n+1);
    us.resize(n+1);
    dp.resize(n+1);
    cent.resize(n+1);
    best.resize(n+1);
    sz.resize(n+1);
    tin.resize(n+1);
    tout.resize(n+1);
    for(int i=1;i<n;i++){
        int a,b,c;
        cin>>a>>b>>c;
        g[a].pb({b,c});
        g[b].pb({a,c});
    }
    dfs(0,0,0);
    build(0,-1);
    for(int i=0;i<n;i++){
    	best[i]=1e18;
    }
    for(int ii=0;ii<m;ii++){
    	int a,b;
    	cin>>a>>b;
    	ans=1e18;
    	vector<int>g(a);
    	for(int i=0;i<a;i++){
    		cin>>g[i];
    		upd(g[i],g[i]);
    	}
    	int c;
    	for(int i=0;i<b;i++){
    		cin>>c;
    		res(c,c);
    	}
    	cout<<ans<<"\n";
    	for(int i=0;i<a;i++){
    		nulify(g[i],g[i]);
    	}
    }
}
signed main(){
    fast;
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
}

Compilation message (stderr)

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