제출 #1230868

#제출 시각아이디문제언어결과실행 시간메모리
1230868long290429공장들 (JOI14_factories)C++20
컴파일 에러
0 ms0 KiB
#include<bits/stdc++.h>
using namespace std;
const int maxn=500005;
int tin[maxn],tout[maxn];
int dep[maxn],dtr[maxn];
vector<pair<int,int>> adj[maxn];
int tt,lg;
vector<vector<int>> up;
long long inf=LLONG_MAX/4,ans;
void dfs(int u,int par) {
  tin[u]=++tt;
  up[u][0]=par;
  for(int i=1;i<=lg;++i) {
    if(up[u][i-1]!=-1) {
      up[u][i]=up[up[u][i-1]][i-1];
    }
    else break;
  }
  for(pair<int,int> p:adj[u]) {
    int v=p.first,w=p.second;
    if(v==par) continue;
    dep[v]=dep[u]+1;
    dtr[v]=dtr[u]+w;
    dfs(v,u);
  }
  tout[u]=tt;
}
int lca(int u,int v) {
  if(dep[u]<dep[v]) swap(u,v);
  int k=dep[u]-dep[v];
  for(int i=0;k>0;++i) {
    if(k&1) {
      u=up[u][i];
    }
    k>>=1;
  }
  if(u==v) return u;
  for(int i=lg;i>=0;--i) {
    if(up[u][i]!=-1&&up[v][i]!=-1&&up[u][i]!=up[v][i]) {
      u=up[u][i];
      v=up[v][i];
    }
  }
  return up[u][0];
}
void solve(int a[],int n,int b[],int m) {
  vector<pair<int,int>> c(n+m);
  for(int i=0;i<n+m;++i) {
    if(i<n) c[i]=make_pair(tin[a[i]],a[i]);
    else c[i]=make_pair(tin[b[i-n]],b[i-n]);
  }
  sort(c.begin(),c.end());
  int sz=c.size();
  for(int i=1;i<sz;++i) {
    int anc=lca(c[i].second,c[i-1].second);
    c.push_back({tin[anc],anc});
  }
  sort(c.begin(),c.end());
  c.erase(unique(c.begin(),c.end()),c.end());
  sz=c.size();
  unordered_map<int,int> idx;
  idx.reserve(sz);
  for(int i=0;i<sz;++i) {
    idx[c[i].second]=i;
  }
  vector<int> st;
  vector<vector<pair<int,int>>> vt(sz);
  for(pair<int,int> p:c){
    int u=p.second;
    int id=idx[u];
    while(!st.empty()&&!(tin[c[st.back()].second]<=tin[u]&&tout[u]<=tout[c[st.back()].second])) {
      st.pop_back();
    }
    if(!st.empty()) {
      int v=st.back();
      int node=c[v].second;
      int len=dtr[u]-dtr[node];
      vt[v].push_back({id,len});
      vt[id].push_back({v,len});
    }
    st.push_back(id);
  }
  vector<long long> da(sz,inf),db(sz,inf);
  for(int i=0;i<n;++i) {
    da[idx[a[i]]]=0;
  }
  for(int i=0;i<m;++i) {
    db[idx[b[i]]]=0;
  }
  ans=inf;
  function<void(int,int)> dfs1=[&](int u,int par) {
    for(pair<int,int> p:vt[u]) {
      int v=p.first,w=p.second;
      if(v==par) continue;
      dfs1(v,u);
      da[u]=min(da[u],da[v]+w);
      db[u]=min(db[u],db[v]+w);
    }
    ans=min(ans,da[u]+db[u]);
  };
  dfs1(st[0],-1);
  function<void(int,int)> dfs2=[&](int u,int par) {
    for(pair<int,int> p:vt[u]) {
      int v=p.first,w=p.second;
      if(v==par) continue;
      da[v]=min(da[v],da[u]+w);
      db[v]=min(db[v],db[u]+w);
      ans=min(ans,da[v]+db[v]);
      dfs2(v,u);
    }
  };
  dfs2(st[0],-1);
  cout << ans << "\n";
}
int main() {
  int n,q;
  cin >> n >> q;
  for(int i=1;i<n;++i) {
    int u,v,val;
    cin >> u >> v >> val;
    adj[u].push_back({v,val});
    adj[v].push_back({u,val});
  }
  tt=0;
  dep[0]=0;
  dtr[0]=0;
  lg=floor(log2(n));
  up.assign(n,vector<int>(lg+1,-1));
  dfs(0,-1);
  while(q--) {
    int x,y;
    cin >> x >> y;
    int a[x],b[y];
    for(int i=0;i<x;++i) {
      cin >> a[i];
    }
    for(int j=0;j<y;++j) {
      cin >> b[j];
    }
    solve(a,x,b,y);
  }
}

컴파일 시 표준 에러 (stderr) 메시지

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