Submission #364524

#	Time	Username	Problem	Language	Result	Execution time	Memory
364524		eric_xiao	Factories (JOI14_factories)	C++14	33 / 100	8070 ms	262648 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;
ll pre[500009],dep[500009],td[500009];
ll anc[500009][20],cnt = 0;
vector<ll> G[500009],d[500009];
vector<ll> G2[500009],d2[500009];
void DFS(ll u,ll p)
{
    anc[u][0] = p;
    cnt++;
    pre[u] = cnt;
    //cerr << u << "_" << td[u] << "_" << dep[u] << endl;
    for(int i = 1;i < 20;i++)
    {
        anc[u][i] = anc[anc[u][i-1]][i-1];
    }
    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);
    }
}
ll LCA(ll a,ll b)
{
    if(a == 0 || b == 0) return 0LL;
    if(td[a] < td[b]) swap(a,b);
    int left = td[a] - td[b];
    for(int i = 0;i < 20;i++)
    {
        if((left>>i) & 1) a = anc[a][i];
    }
    if(a == b) return a;
    for(int i = 19;i >= 0;i--)
    {
        if(anc[a][i] != anc[b][i])
        {
            a = anc[a][i];
            b = anc[b][i];
        }
    }
    return anc[a][0];
}
const bool cmp(const ll &a,const ll & 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;
    DFS(1,0);
}
vector<ll> vs;
ll temp[500009];
ll stk[500009];
ll ans = 10000000000000000;
ll s,x[500009],t,y[500009];
ll ec = 0;
void add_edge(ll a,ll 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 dis[500009];
set<ll> used;
void DKS()
{
    priority_queue<pii,vector<pii>,greater<pii> > pq;
    for(auto tt : used)
    {
        dis[tt] = 10000000000000000;
    }
    for(int i = 0;i < s;i++)
    {
        pq.push({0,x[i]});
    }
    while(!pq.empty())
    {
        ll u = pq.top().ss,tt = pq.top().ff;
        pq.pop();
        if(tt >= dis[u]) continue;
        dis[u] = tt;
        for(int i = 0;i < G2[u].size();i++)
        {
            ll v = G2[u][i];
            if(dis[v] < 10000000000000000) continue;
            pq.push({dis[u] + d2[u][i],v});
        }
    }
    for(int i = 0;i < t;i++)
    {
        ans = min(ans,dis[y[i]]);
    }
}
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;
    ec = 0;
    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(long long int, long long int)':
factories.cpp:22:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(int i = 0;i < G[u].size();i++)
      |                   ~~^~~~~~~~~~~~~
factories.cpp: In function 'void DKS()':
factories.cpp:102:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         for(int i = 0;i < G2[u].size();i++)
      |                       ~~^~~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:147:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |     for(int i = 0;i < vs.size();i++)
      |                   ~~^~~~~~~~~~~

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