oj.uz

Submission #318964

# Submission time Handle Problem Language Result Execution time Memory
318964 2020-11-03T15:13:57 Z Dymo Factories (JOI14_factories) C++14
15 / 100
 1125 ms 46312 KB 
#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];
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]=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);
}
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

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3308 KB Output is correct
2 Correct 1125 ms 21952 KB Output is correct
3 Correct 1084 ms 21860 KB Output is correct
4 Correct 1085 ms 22212 KB Output is correct
5 Correct 934 ms 22500 KB Output is correct
6 Correct 950 ms 22024 KB Output is correct
7 Correct 1093 ms 21876 KB Output is correct
8 Correct 1068 ms 22484 KB Output is correct
9 Correct 943 ms 22304 KB Output is correct
10 Correct 940 ms 21944 KB Output is correct
11 Correct 1104 ms 21916 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3052 KB Output is correct
2 Runtime error 415 ms 46312 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3308 KB Output is correct
2 Correct 1125 ms 21952 KB Output is correct
3 Correct 1084 ms 21860 KB Output is correct
4 Correct 1085 ms 22212 KB Output is correct
5 Correct 934 ms 22500 KB Output is correct
6 Correct 950 ms 22024 KB Output is correct
7 Correct 1093 ms 21876 KB Output is correct
8 Correct 1068 ms 22484 KB Output is correct
9 Correct 943 ms 22304 KB Output is correct
10 Correct 940 ms 21944 KB Output is correct
11 Correct 1104 ms 21916 KB Output is correct
12 Correct 5 ms 3052 KB Output is correct
13 Runtime error 415 ms 46312 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -