Submission #318971

#	Time	Username	Problem	Language	Result	Execution time	Memory
318971		Dymo	Factories (JOI14_factories)	C++14	15 / 100	1058 ms	27620 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=5e4+54;
const ll mod =1e9+7  ;
const ll base=1e18;
vector<pll> adj[maxn];
int dep[maxn];
ll dep1[maxn];
int anc[maxn][20];
int col[maxn];

vector<ll> adj1[maxn];
int f[maxn];
int l[maxn];
int 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]=dep1[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]=dep1[u];
  else if (col[u]==2) dp2[u]=dep1[u];
  for (auto to:adj1[u])
  {
      dfs1(to);
      ans=min(ans,dp1[u]+dp2[to]-dep1[u]*2);
        ans=min(ans,dp2[u]+dp1[to]-dep1[u]*2);
      dp1[u]=min(dp1[u],dp1[to]);
      dp2[u]=min(dp2[u],dp2[to]);
  }

}
void Init(int N,int A[],int B[],int D[])
{
    ll n= N;
    for (int i=1;i<=n;i++)
    {
        adj[i].clear();
    }
    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]));
    }
    cnt=0;
    dfs(1,0);
    for (int i=1;i<=n;i++)
    {
        adj[i].clear();
    }
}
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();
   }
  return ans;

}
/*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);
    }

}*/

Compilation message (stderr)

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:131: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]
  131 |    for (int i=1;i<vt.size();i++)
      |                 ~^~~~~~~~~~

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