Submission #364544

#	Time	Username	Problem	Language	Result	Execution time	Memory
364544		eric_xiao	Factories (JOI14_factories)	C++14	33 / 100	8119 ms	274064 KiB

factories

#include<bits/stdc++.h>
#include "factories.h"
#define ll long long
#define pii pair<ll,ll>
#define ff first
#define ss second
using namespace std;
int pre[500009],td[500009],fst[500009];
ll dep[500009],inv[500009];
int st[22][1500009],cnt = 0;
vector<int> G[500009],d[500009];
vector<int> G2[500009];
vector<ll> d2[500009];
vector<int> ov;
void DFS(int u,int p)
{
    cnt++;
    pre[u] = cnt;
    inv[pre[u]] = u;
    fst[u] = ov.size();
    ov.push_back(pre[u]);
    for(int i = 0;i < G[u].size();i++)
    {
        int v = G[u][i];
        if(v == p) continue;
        dep[v] = dep[u] + d[u][i];
        td[v] = td[u] + 1;
        DFS(v,u);
        ov.push_back(pre[u]);
    }
}
int LCA(int a,int b)
{
    if(a == b) return a;
    if(a == 0 || b == 0) return 0LL;
    if(fst[a] > fst[b]) swap(a,b);
    int ret;
    int tp = __lg(fst[b]-fst[a]);
    //cout << fst[a] << " " << fst[b] << " " << tp << " " << min(st[tp][fst[a]],st[tp][fst[b] - (1<<tp)]) << endl;
    return inv[min(st[tp][fst[a]],st[tp][fst[b] - (1<<tp)])];
//    ret = min()
}
const bool cmp(const int &a,const int & b)
{
    return pre[a] < pre[b];
}
void Init(int N, int A[], int B[], int D[]) {
    for(int i = 0;i < N-1;i++)
    {
        A[i]++;
        B[i]++;
        G[A[i]].push_back(B[i]);
        G[B[i]].push_back(A[i]);
        d[A[i]].push_back(D[i]);
        d[B[i]].push_back(D[i]);
    }
    td[1] = 1;
    ov.push_back(0);
    DFS(1,0);
    for(int i = 0;i < ov.size();i++)
    {
        st[0][i] = ov[i];

    }
    for(int i = 1;i < 22;i++)
    {
        for(int j = 0;j+(1<<(i-1)) < ov.size();j++)
        {
            st[i][j] = min(st[i-1][j],st[i-1][j+(1<<(i-1))]);
            //cout << st[i][j] << " ";
        }
        //cout << endl;
    }

}
vector<ll> vs;
int temp[500009];
int stk[500009];
ll ans = 10000000000000000;
int s,x[500009],t,y[500009];
void add_edge(int a,int b)
{
    ll tp = abs(dep[a]-dep[b]);
    //cerr << a << "_" << b << "_" << tp << endl;
    G2[a].push_back(b);
    G2[b].push_back(a);
    d2[a].push_back(tp);
    d2[b].push_back(tp);
}
ll iss[500009],ist[500009];
ll dp1[500009],dp2[500009];
set<int> used;
void DFS2(int u,int p)
{
    if(iss[u]) dp1[u] = 0;
    if(ist[u]) dp2[u] = 0;
    for(int i = 0;i < G2[u].size();i++)
    {
        int v = G2[u][i];
        if(v == p) continue;
        DFS2(v,u);
        dp1[u] = min(dp1[v]+d2[u][i],dp1[u]);
        dp2[u] = min(dp2[v]+d2[u][i],dp2[u]);
    }
    //cout << u << "_" << dp1[u] << "_" << dp2[u] << endl;
    ans = min(ans,dp1[u] + dp2[u]);

}
void DKS()
{
    int i;
    for(i = 0;i < s;i++)
    {
        iss[x[i]] = 1;
    }
    for(i = 0;i < t;i++)
    {
        ist[y[i]] = 1;
    }
    for(auto tt : used)
    {
        dp1[tt] = dp2[tt] = 10000000000000000;
    }
    DFS2(x[0],0);
    for(i = 0;i < s;i++)
    {
        iss[x[i]] = 0;
    }
    for(i = 0;i < t;i++)
    {
        ist[y[i]] = 0;
    }

}
long long Query(int S, int X[], int T, int Y[]) {
    vs.clear();
    s = S;
    used.clear();
    for(int i = 0;i < S;i++)
    {
        X[i]++;
        used.insert(X[i]);
        x[i] = X[i];
        G2[X[i]].clear();
        d2[X[i]].clear();
        temp[X[i]] = 1;
        vs.push_back(X[i]);
    }
    int fg = 0;
    t = T;
    for(int i = 0;i < T;i++)
    {
        Y[i]++;
        used.insert(Y[i]);
        y[i] = Y[i];
        G2[Y[i]].clear();
        d2[Y[i]].clear();
        vs.push_back(Y[i]);
        if(temp[Y[i]] == 1) fg = 1;
    }
    for(int i = 0;i < S;i++) temp[X[i]] = 0;
    if(fg == 1) return 0;
    sort(vs.begin(),vs.end(),cmp);
    stk[0] = 0;
    int sz = 1;
    ans = 10000000000000000;
    for(int i = 0;i < vs.size();i++)
    {
        ll u = vs[i];
        ll p = LCA(u,stk[sz-1]);
        //cerr << vs[i] << " p = " << p << endl;
        if(!used.count(p))
        {
            used.insert(p);
            G2[p].clear();
            d2[p].clear();
        }
        if(p == stk[sz-1]) stk[sz++] = u;
        else
        {
            while(sz > 1 && td[stk[sz-2]] >= td[p])
            {
                add_edge(stk[sz-1],stk[sz-2]);
                sz--;
            }
            if(stk[sz-1] != p)
            {
                add_edge(stk[sz-1],p);
                stk[sz-1] = p;
            }
            stk[sz++] = u;
        }
    }
    for (int i = 1; i < sz - 1; ++i) add_edge(stk[i], stk[i + 1]);
    DKS();
    return ans;
}

Compilation message (stderr)

factories.cpp: In function 'void DFS(int, int)':
factories.cpp:22:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(int i = 0;i < G[u].size();i++)
      |                   ~~^~~~~~~~~~~~~
factories.cpp: In function 'int LCA(int, int)':
factories.cpp:37:9: warning: unused variable 'ret' [-Wunused-variable]
   37 |     int ret;
      |         ^~~
factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:60:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for(int i = 0;i < ov.size();i++)
      |                   ~~^~~~~~~~~~~
factories.cpp:67:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |         for(int j = 0;j+(1<<(i-1)) < ov.size();j++)
      |                       ~~~~~~~~~~~~~^~~~~~~~~~~
factories.cpp: In function 'void DFS2(int, int)':
factories.cpp:97:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for(int i = 0;i < G2[u].size();i++)
      |                   ~~^~~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:167:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 |     for(int i = 0;i < vs.size();i++)
      |                   ~~^~~~~~~~~~~

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