oj.uz

Submission #270668

# Submission time Handle Problem Language Result Execution time Memory
270668 2020-08-17T21:21:44 Z MKopchev Factories (JOI14_factories) C++14
100 / 100
 7285 ms 293920 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 12672 KB Output is correct
2 Correct 539 ms 22344 KB Output is correct
3 Correct 684 ms 22392 KB Output is correct
4 Correct 667 ms 22264 KB Output is correct
5 Correct 638 ms 22576 KB Output is correct
6 Correct 387 ms 22140 KB Output is correct
7 Correct 672 ms 22276 KB Output is correct
8 Correct 710 ms 22392 KB Output is correct
9 Correct 641 ms 22520 KB Output is correct
10 Correct 349 ms 22136 KB Output is correct
11 Correct 669 ms 22264 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12544 KB Output is correct
2 Correct 3271 ms 263140 KB Output is correct
3 Correct 4865 ms 265436 KB Output is correct
4 Correct 1184 ms 263652 KB Output is correct
5 Correct 5727 ms 293920 KB Output is correct
6 Correct 4868 ms 266816 KB Output is correct
7 Correct 2290 ms 67704 KB Output is correct
8 Correct 741 ms 68012 KB Output is correct
9 Correct 2213 ms 71616 KB Output is correct
10 Correct 2446 ms 68728 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 12672 KB Output is correct
2 Correct 539 ms 22344 KB Output is correct
3 Correct 684 ms 22392 KB Output is correct
4 Correct 667 ms 22264 KB Output is correct
5 Correct 638 ms 22576 KB Output is correct
6 Correct 387 ms 22140 KB Output is correct
7 Correct 672 ms 22276 KB Output is correct
8 Correct 710 ms 22392 KB Output is correct
9 Correct 641 ms 22520 KB Output is correct
10 Correct 349 ms 22136 KB Output is correct
11 Correct 669 ms 22264 KB Output is correct
12 Correct 10 ms 12544 KB Output is correct
13 Correct 3271 ms 263140 KB Output is correct
14 Correct 4865 ms 265436 KB Output is correct
15 Correct 1184 ms 263652 KB Output is correct
16 Correct 5727 ms 293920 KB Output is correct
17 Correct 4868 ms 266816 KB Output is correct
18 Correct 2290 ms 67704 KB Output is correct
19 Correct 741 ms 68012 KB Output is correct
20 Correct 2213 ms 71616 KB Output is correct
21 Correct 2446 ms 68728 KB Output is correct
22 Correct 4474 ms 264532 KB Output is correct
23 Correct 4668 ms 266864 KB Output is correct
24 Correct 6514 ms 267136 KB Output is correct
25 Correct 6697 ms 270724 KB Output is correct
26 Correct 6575 ms 267496 KB Output is correct
27 Correct 7285 ms 290564 KB Output is correct
28 Correct 1619 ms 267680 KB Output is correct
29 Correct 6580 ms 266884 KB Output is correct
30 Correct 6363 ms 266272 KB Output is correct
31 Correct 6615 ms 267160 KB Output is correct
32 Correct 2166 ms 73980 KB Output is correct
33 Correct 850 ms 69764 KB Output is correct
34 Correct 1867 ms 66808 KB Output is correct
35 Correct 1839 ms 66808 KB Output is correct
36 Correct 2328 ms 67448 KB Output is correct
37 Correct 2422 ms 67436 KB Output is correct