제출 #318953

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
318953		Dymo	공장들 (JOI14_factories)	C++14	0 / 100	22 ms	11244 KiB

factories

#include<bits/stdc++.h>

using namespace std;


#define pb    push_back
#define eb   emplace_back
#define ll  long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define endl "\n"
const ll maxn=1e5+54;
const ll mod =1e9+7  ;
const ll base=1e18;
vector<pll> adj[maxn];
ll dep[maxn];
ll dep1[maxn];
ll anc[maxn][20];
ll col[maxn];

vector<ll> adj1[maxn];
ll f[maxn];
ll l[maxn];
ll cnt=0;
void dfs(ll u,ll par)
{
    cnt++;
    f[u]=cnt;
    anc[u][0]=par;
    for (int i=1;i<19;i++)
    {
        anc[u][i]=anc[anc[u][i-1]][i-1];

    }
    for (auto to:adj[u])
    {
        if (to.ff==par) continue;
        dep[to.ff]=dep[u]+1;
        dep1[to.ff]=dep[u]+to.ss;
        dfs(to.ff,u);
    }
    l[u]=cnt;

}
ll lca(ll x,ll y)
{
    if (dep[x]< dep[y]) swap(x,y);
    ll kc= dep[x]-dep[y];
    for (int i=18;i>=0;i--)
    {
        if (kc&(1ll<<i))
        {
            x=anc[x][i];
        }
    }
    if (x==y) return x;
    for (int i=18;i>=0;i--)
    {
        if (anc[x][i]!=anc[y][i])
        {
            x=anc[x][i];
            y=anc[y][i];
        }
    }
    return anc[x][0];
}
ll kc(ll x,ll y)
{
    return dep1[x]+dep1[y]-2*(dep1[lca(x,y)]);
}
ll dp1[maxn];
ll dp2[maxn];
ll ans=1e18;
void dfs1(ll u)
{
  dp1[u]=dp2[u]=1e15;
  if (col[u]==1) dp1[u]=0;
  else if (col[u]==2) dp2[u]=0;
  for (auto to:adj1[u])
  {
      dfs1(to);
      dp1[u]=min(dp1[u],dp1[to]+kc(to,u));
      dp2[u]=min(dp2[u],dp2[to]+kc(to,u));
  }
  ans=min(ans,dp1[u]+dp2[u]);
}
void Init(int N,int A[],int B[],int D[])
{
    ll n= N;
    for (int i=0;i<n-1;i++)
    {
        A[i]++;
        B[i]++;

        adj[A[i]].pb(make_pair(B[i],D[i]));
        adj[B[i]].pb(make_pair(A[i],D[i]));
    }
    dfs(1,0);
}
long long Query(int S,int X[],int T,int Y[])
{
    ans=1e18;
    vector<pll> vt;
   for (int i=0;i<S;i++)
   {
       X[i]++;
       col[X[i]]=1;
       vt.pb(make_pair(f[X[i]],X[i]));

   }
   for (int i=0;i<T;i++)
   {
       Y[i]++;
       col[Y[i]]=2;
       vt.pb(make_pair(f[Y[i]],Y[i]));
   }
   sort(vt.begin(),vt.end());
   vector<pll> nw;
   for (int i=1;i<vt.size();i++)
   {
       ll h=lca(vt[i].ss,vt[i-1].ss);
       nw.pb(make_pair(f[h],h));
   }
   for (auto p:vt)
   {
       nw.pb(p);
   }
   nw.pb(make_pair(f[1],1));
   sort(nw.begin(),nw.end());
   nw.resize(unique(nw.begin(),nw.end())-nw.begin());
   stack<ll> st;
   for (auto p:nw)
   {
       while (st.size()&&l[st.top()]<p.ff) st.pop();
       if (st.size())
       {
           adj1[st.top()].pb(p.ss);
       }
       st.push(p.ss);
   }
   dfs1(1);
   for (auto p:nw)
   {
       col[p.ss]=0;
       adj1[p.ss].clear();
   }
   cout <<ans<<endl;

}
/*int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if (fopen("t.txt", "r"))
    {
        freopen("test.txt", "r", stdin);
      //  freopen("team.out", "w", stdout);
    }

}*/

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

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:120:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |    for (int i=1;i<vt.size();i++)
      |                 ~^~~~~~~~~~
factories.cpp:150:1: warning: no return statement in function returning non-void [-Wreturn-type]
  150 | }
      | ^

• Subtask 1: 0 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67