oj.uz

Submission #645561

# Submission time Handle Problem Language Result Execution time Memory
645561 2022-09-27T10:53:55 Z fdnfksd Factories (JOI14_factories) C++14
18 / 100
 4512 ms 293372 KB 
#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll maxN=2e6+10;
#define taskname "codeforce"
ll dp1[maxN],dp2[maxN],mn1[maxN],mn2[maxN];
const ll inf=1e15;
#define pli pair<ll,ll>
#define fi first
#define se second
vector<pli>g[maxN];
vector<pli>c[maxN];
ll vt[maxN];
void dfs1(ll u,ll p)
{
    dp1[u]=inf;
    mn1[u]=mn2[u]=inf;
    for(auto vv:c[u])
    {
        ll v=vv.fi;
        ll w=vv.se;
        //if(v==p) {continue;}
        dfs1(v,u);
        dp1[u]=min(dp1[v]+w,dp1[u]);
        if(dp1[v]+w<=mn1[u])
        {
            mn2[u]=mn1[u];
            mn1[u]=dp1[v]+w;
        }
        else if(dp1[v]+w<=mn2[u])
        {
            mn2[u]=dp1[v]+w;
        }
    }
    if(vt[u]>=2) dp1[u]=0;
}
void dfs2(ll u,ll p,ll w)
{
    dp2[u]=inf;
    if(vt[u]>=2) dp2[u]=0;
    else
    {
        if(p!=0)
        {
            if(vt[p]>=2) dp2[u]=w;
            else
            {
                if(dp1[u]+w==mn1[p]) dp2[u]=mn2[p]+w;
                else dp2[u]=mn1[p]+w;
                dp2[u]=min(dp2[u],dp2[p]+w);
            }
        }
    }
    
    for(auto vv:c[u])
    {
        ll v=vv.fi;
        ll w=vv.se;
        //if(v==p) continue;
        dfs2(v,u,w);
    }
}
#define pb push_back
ll in[maxN],out[maxN];
bool cmp(ll x,ll y)
{
    return in[x]<in[y];
}
ll cnt[maxN];
ll h[maxN];
ll dd[maxN],tg=0;
ll par[maxN][21];
void dfs(ll u=1,ll p=1)
{
    in[u]=++tg;
    par[u][0]=p;
    for(int i=1;i<=20;i++) par[u][i]=par[par[u][i-1]][i-1];
    for(auto vv:g[u])
    {
        ll v=vv.fi;
        ll w=vv.se;
        if(v!=p)
        {
            h[v]=h[u]+1;
            dd[v]=dd[u]+w;
            dfs(v,u);
        }
    }
    out[u]=tg;
}
ll LCA(ll u, ll v)
{
    if(h[u]<h[v]) swap(u,v);
    ll log=log2(h[u])+1;
    for(int i=log;i>=0;i--)
    {
        if(h[par[u][i]]>=h[v]) u=par[u][i];
    }
    if(u==v) return u;
    for(int i=log;i>=0;i--)
    {
        if(par[u][i]!=par[v][i]) u=par[u][i],v=par[v][i];
    }
    return par[u][0];
}
ll dis(ll u,ll v)
{
    return dd[u]+dd[v]-2*dd[LCA(u,v)];
}
bool isParent(ll x,ll y)
{
    return in[x]<=in[y]&&out[y]<=out[x];
}
void Init(int N,int A[],int B[],int D[])
{
    for(int i=0;i<N-1;i++)
    {
        g[A[i]].pb({B[i],D[i]});
        g[B[i]].pb({A[i],D[i]});
    }
    dfs();
}
ll Query(int s,int x[],int t,int y[])
{
    vector<ll> vv;
    for(int i=0;i<s;i++) vv.pb(x[i]),vt[x[i]]+=1;
    for(int i=0;i<t;i++) vv.pb(y[i]),vt[y[i]]+=2;
    sort(vv.begin(),vv.end(),cmp);
    ll k=vv.size();
    for(int i=1;i<k;i++)
    {
        ll v=LCA(vv[i],vv[i-1]);
        vv.pb(v);
    }
    sort(vv.begin(),vv.end(),cmp);
    stack<int>st;
    for(int i=0;i<vv.size();i++)
    {
        if(cnt[vv[i]]==0)
        {
            while(!st.empty()&&(!isParent(st.top(),vv[i]))) st.pop();
            if(!st.empty()) c[st.top()].pb({vv[i],dis(st.top(),vv[i])});
            st.push(vv[i]);
            cnt[vv[i]]=1;
        }
    }
    //cout << '\n';
    dfs1(vv[0],0);
    dfs2(vv[0],0,0);
    ll ans=inf;
    for(int i=0;i<vv.size();i++)
    {
        if(vt[vv[i]]==1||vt[vv[i]]==3)
        {
            ans=min(ans,min(dp1[vv[i]],dp2[vv[i]]));
        }
    }
    for(int i=0;i<vv.size();i++)
    {
        cnt[vv[i]]=0;
        c[vv[i]].clear();
        vt[vv[i]]=0;
    }
    return ans;
}

Compilation message

factories.cpp: In function 'll Query(int, int*, int, int*)':
factories.cpp:138:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |     for(int i=0;i<vv.size();i++)
      |                 ~^~~~~~~~~~
factories.cpp:152:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |     for(int i=0;i<vv.size();i++)
      |                 ~^~~~~~~~~~
factories.cpp:159:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |     for(int i=0;i<vv.size();i++)
      |                 ~^~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 94956 KB Output is correct
2 Correct 1152 ms 104528 KB Output is correct
3 Correct 1352 ms 104860 KB Output is correct
4 Correct 1280 ms 104928 KB Output is correct
5 Incorrect 1249 ms 105360 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 94540 KB Output is correct
2 Correct 1958 ms 254168 KB Output is correct
3 Correct 4313 ms 258100 KB Output is correct
4 Correct 1229 ms 251900 KB Output is correct
5 Correct 3473 ms 293372 KB Output is correct
6 Correct 4512 ms 259784 KB Output is correct
7 Correct 3623 ms 135636 KB Output is correct
8 Correct 1172 ms 135152 KB Output is correct
9 Correct 2935 ms 143040 KB Output is correct
10 Correct 3612 ms 137040 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 94956 KB Output is correct
2 Correct 1152 ms 104528 KB Output is correct
3 Correct 1352 ms 104860 KB Output is correct
4 Correct 1280 ms 104928 KB Output is correct
5 Incorrect 1249 ms 105360 KB Output isn't correct
6 Halted 0 ms 0 KB -