Submission #1245636

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

factories

#include<bits/stdc++.h>
#include<algorithm>
#include<random>
#include<chrono>
#include<cstdlib>
#include<ctime>
#include<numeric>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<iomanip>
#define int long long
#define ll long long
#define L LLONG_MAX
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define sz(a) ((int)a.size())
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define REP(i,k,j) for(int i=k;i>=j;i--)
#define FORD(i,a) for(auto i:a)
#define MASK(i) ((1)<<(i))
#define rngdcl mt19937_64 rng(chrono::steady_clock::now().time_asince_epoch().count())
#define random(l,r) ((l)+(rng()%(r-l+1)))
using namespace std;
const int nmax=1e5+1;
int n,q;
vector<pii> adj[nmax];
vector<pii> fac[nmax];
int ans[nmax];
int depth[nmax],treesize[nmax],vst[nmax];
int mn[nmax][2];

void input()
{
    cin >> n >> q;
    FOR(i,1,n-1)
    {
        int u,v,w; cin >> u >> v >> w;
        u++; v++;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }
    FOR(i,1,q)
    {
        int u,v; cin >> u >> v;
        FOR(j,1,u)
        {
            int x; cin >> x;
            x++;
            fac[x].push_back({i,0});
        }
        FOR(j,1,v)
        {
            int x; cin >> x;
            x++;
            fac[x].push_back({i,1});
        }
    }
}

void pre_dfs(int u,int v)
{
    treesize[u]=1;
    FORD(i,adj[u])
    {
        if(i.fi==v || vst[i.fi]) continue;
        depth[i.fi]=depth[u]+i.se;
        pre_dfs(i.fi,u);
        treesize[u]+=treesize[i.fi];
    }
}

int centroid(int u,int v,int n)
{
    FORD(i,adj[u])
    {
        if(i.fi==v || vst[i.fi]) continue;
        if(treesize[i.fi]>n/2) return centroid(i.fi,u,n);
    }
    return u;
}

void add(int u,int v)
{
    FORD(i,adj[u])
    {
        if(i.fi==v || vst[i.fi]) continue;
        add(i.fi,u);
    }
    FORD(i,fac[u]) mn[i.fi][i.se]=min(mn[i.fi][i.se],depth[u]);
}

void get(int u,int v)
{
    FORD(i,adj[u])
    {
        if(i.fi==v || vst[i.fi]) continue;
        get(i.fi,u);
    }
    FORD(i,fac[u]) if(mn[i.fi][1-i.se]!=L) ans[i.fi]=min(ans[i.fi],depth[u]+mn[i.fi][1-i.se]);
}

void reset(int u,int v)
{
    FORD(i,adj[u])
    {
        if(i.fi==v || vst[i.fi]) continue;
        reset(i.fi,u);
    }
    FORD(i,fac[u]) mn[i.fi][i.se]=L;
}

void dnc(int ct)
{
    depth[ct]=0;
    pre_dfs(ct,0);
    vst[ct]=true;
    
    FORD(i,adj[ct]) if(!vst[i.fi])
    {
        get(i.fi,ct);
        add(i.fi,ct);
    }
    FORD(i,fac[ct]) if(mn[i.fi][1-i.se]!=L) ans[i.fi]=min(ans[i.fi],mn[i.fi][1-i.se]);
    FORD(i,adj[ct]) if(!vst[i.fi]) reset(i.fi,ct);
    
    FORD(i,adj[ct])
    {
        if(vst[i.fi]) continue;
        dnc(centroid(i.fi,0,treesize[i.fi]));
    }
}

void solve()
{
    FOR(i,1,q)
    {
        mn[i][0]=L;
        mn[i][1]=L;
        ans[i]=L;
    }
    //tim centroid dau tien
    pre_dfs(1,0);
    int ct=centroid(1,0,n);
    
    dnc(ct);
    FOR(i,1,q) cout << ans[i] << '\n';
}

signed main()
{
    //freopen(".inp", "r", stdin);
    //freopen(".out", "w", stdout);
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    input();
    solve();
}

Compilation message (stderr)

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