Submission #270668

#	Time	Username	Problem	Language	Result	Execution time	Memory
270668		MKopchev	Factories (JOI14_factories)	C++14	100 / 100	7285 ms	293920 KiB

factories

#include "factories.h"
#include<bits/stdc++.h>

#define MAX_N          500000
#define MAX_Q          100000
#define MAX_SUM_ST    1000000
#define MAX_VALUE  1000000000

using namespace std;
const int nmax=5e5+42;
const long long inf=1e18;

static int N, Q;
static int A[MAX_N], B[MAX_N], D[MAX_N];
static int S[MAX_N];
static int T[MAX_N];
static int X[MAX_SUM_ST];
static int Y[MAX_SUM_ST];

static int Qx[MAX_N];
static int Qy[MAX_N];

int n;

vector< pair<int/*to*/,int/*cost*/> > adj[nmax];

int height[nmax];

long long depth[nmax];

int t,in[nmax],out[nmax];

pair<int/*height*/,int/*node*/> table[22][2*nmax];

void dfs(int node,int par,int h,long long sum)
{
    height[node]=h;
    depth[node]=sum;

    t++;
    in[node]=t;

    table[0][t]={height[node],node};

    for(auto k:adj[node])
        if(k.first!=par)
        {
            dfs(k.first,node,h+1,sum+k.second);
            t++;
            table[0][t]={height[node],node};
        }
    out[node]=t;
}

bool been[nmax];

int SZ[nmax];

void dfs_sz(int node,int par)
{
    SZ[node]=1;
    for(auto k:adj[node])
        if(k.first!=par&&been[k.first]==0)
        {
            dfs_sz(k.first,node);
            SZ[node]+=SZ[k.first];
        }
}

int centroid(int node)
{
    dfs_sz(node,node);

    int req=SZ[node]/2;

    while(SZ[node]>req)
    {
        bool stop=1;

        for(auto k:adj[node])
            if(SZ[node]>SZ[k.first]&&SZ[k.first]>req)
            {
                node=k.first;
                stop=0;
            }
        if(stop)break;
    }
    return node;
}

int centroid_paths[nmax][25],pointer[nmax];

void note_paths(int node,int par,int centroid)
{
    pointer[node]++;
    centroid_paths[node][pointer[node]]=centroid;

    for(auto k:adj[node])
        if(k.first!=par&&been[k.first]==0)
            note_paths(k.first,node,centroid);
}

void create_centroid(int node)
{
    node=centroid(node);

    note_paths(node,node,node);

    been[node]=1;

    for(auto k:adj[node])
        if(been[k.first]==0)create_centroid(k.first);
}

long long mini[nmax];

int inv[nmax*2];

void Init(int N, int A[], int B[], int D[]) {
    n=N;

    for(int i=0;i<n-1;i++)
    {
        adj[A[i]].push_back({B[i],D[i]});
        adj[B[i]].push_back({A[i],D[i]});
    }

    dfs(0,0,0,0);

    for(int h=1;(1<<h)<=t;h++)
        for(int i=1;i+(1<<h)-1<=t;i++)
            table[h][i]=min(table[h-1][i],table[h-1][i+(1<<(h-1))]);

    for(int h=1;h<=t;h++)
    {
        while((1<<inv[h])+(1<<inv[h])<h)inv[h]++;
    }
    create_centroid(0);

    for(int i=0;i<n;i++)mini[i]=inf;
}

pair<int/*height*/,int/*node*/> ask_min(int le,int ri)
{
    int sz=inv[ri-le+1];

    return min(table[sz][le],table[sz][ri-(1<<sz)+1]);
}
int LCA(int u,int v)
{
    return ask_min(min(in[u],in[v]),max(out[u],out[v])).second;
}
long long dist(int u,int v)
{
    return depth[u]+depth[v]-2*depth[LCA(u,v)];
}

void mark(int node)
{
    for(int p=1;p<=pointer[node];p++)
        mini[centroid_paths[node][p]]=min(mini[centroid_paths[node][p]],dist(centroid_paths[node][p],node));
}

long long closest(int node)
{
    long long ret=inf;

    for(int p=1;p<=pointer[node];p++)
        ret=min(ret,mini[centroid_paths[node][p]]+dist(centroid_paths[node][p],node));

    return ret;
}
void unmark(int node)
{
    for(int p=1;p<=pointer[node];p++)
        mini[centroid_paths[node][p]]=inf;
}
long long Query(int S, int X[], int T, int Y[])
{
    for(int i=0;i<S;i++)
        mark(X[i]);

    long long ret=inf;

    for(int j=0;j<T;j++)
        ret=min(ret,closest(Y[j]));

    for(int i=0;i<S;i++)
        unmark(X[i]);

    return ret;
}

Compilation message (stderr)

factories.cpp:21:12: warning: 'Qy' defined but not used [-Wunused-variable]
   21 | static int Qy[MAX_N];
      |            ^~
factories.cpp:20:12: warning: 'Qx' defined but not used [-Wunused-variable]
   20 | static int Qx[MAX_N];
      |            ^~
factories.cpp:18:12: warning: 'Y' defined but not used [-Wunused-variable]
   18 | static int Y[MAX_SUM_ST];
      |            ^
factories.cpp:17:12: warning: 'X' defined but not used [-Wunused-variable]
   17 | static int X[MAX_SUM_ST];
      |            ^
factories.cpp:16:12: warning: 'T' defined but not used [-Wunused-variable]
   16 | static int T[MAX_N];
      |            ^
factories.cpp:15:12: warning: 'S' defined but not used [-Wunused-variable]
   15 | static int S[MAX_N];
      |            ^
factories.cpp:14:32: warning: 'D' defined but not used [-Wunused-variable]
   14 | static int A[MAX_N], B[MAX_N], D[MAX_N];
      |                                ^
factories.cpp:14:22: warning: 'B' defined but not used [-Wunused-variable]
   14 | static int A[MAX_N], B[MAX_N], D[MAX_N];
      |                      ^
factories.cpp:14:12: warning: 'A' defined but not used [-Wunused-variable]
   14 | static int A[MAX_N], B[MAX_N], D[MAX_N];
      |            ^
factories.cpp:13:15: warning: 'Q' defined but not used [-Wunused-variable]
   13 | static int N, Q;
      |               ^
factories.cpp:13:12: warning: 'N' defined but not used [-Wunused-variable]
   13 | static int N, Q;
      |            ^

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