oj.uz

Submission #270664

# Submission time Handle Problem Language Result Execution time Memory
270664 2020-08-17T21:15:31 Z MKopchev Factories (JOI14_factories) C++14
33 / 100
 8000 ms 322640 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]+1)/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;
}

vector<int> centroid_paths[nmax];

void note_paths(int node,int par,int centroid)
{
    centroid_paths[node].push_back(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(auto k:centroid_paths[node])
        mini[k]=min(mini[k],dist(k,node));
}

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

    for(auto k:centroid_paths[node])
        ret=min(ret,mini[k]+dist(k,node));

    return ret;
}
void unmark(int node)
{
    for(auto k:centroid_paths[node])
        mini[k]=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 28 ms 24320 KB Output is correct
2 Correct 566 ms 33688 KB Output is correct
3 Correct 706 ms 33912 KB Output is correct
4 Correct 708 ms 34168 KB Output is correct
5 Correct 683 ms 34168 KB Output is correct
6 Correct 360 ms 33656 KB Output is correct
7 Correct 701 ms 33784 KB Output is correct
8 Correct 719 ms 33832 KB Output is correct
9 Correct 681 ms 34328 KB Output is correct
10 Correct 405 ms 33656 KB Output is correct
11 Correct 743 ms 33784 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 24192 KB Output is correct
2 Correct 3872 ms 261388 KB Output is correct
3 Correct 5548 ms 281096 KB Output is correct
4 Correct 1313 ms 240348 KB Output is correct
5 Correct 6491 ms 322640 KB Output is correct
6 Correct 5722 ms 282052 KB Output is correct
7 Correct 2712 ms 77664 KB Output is correct
8 Correct 828 ms 73148 KB Output is correct
9 Correct 2320 ms 83576 KB Output is correct
10 Correct 2791 ms 78840 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 24320 KB Output is correct
2 Correct 566 ms 33688 KB Output is correct
3 Correct 706 ms 33912 KB Output is correct
4 Correct 708 ms 34168 KB Output is correct
5 Correct 683 ms 34168 KB Output is correct
6 Correct 360 ms 33656 KB Output is correct
7 Correct 701 ms 33784 KB Output is correct
8 Correct 719 ms 33832 KB Output is correct
9 Correct 681 ms 34328 KB Output is correct
10 Correct 405 ms 33656 KB Output is correct
11 Correct 743 ms 33784 KB Output is correct
12 Correct 18 ms 24192 KB Output is correct
13 Correct 3872 ms 261388 KB Output is correct
14 Correct 5548 ms 281096 KB Output is correct
15 Correct 1313 ms 240348 KB Output is correct
16 Correct 6491 ms 322640 KB Output is correct
17 Correct 5722 ms 282052 KB Output is correct
18 Correct 2712 ms 77664 KB Output is correct
19 Correct 828 ms 73148 KB Output is correct
20 Correct 2320 ms 83576 KB Output is correct
21 Correct 2791 ms 78840 KB Output is correct
22 Correct 5044 ms 262288 KB Output is correct
23 Correct 5393 ms 265064 KB Output is correct
24 Correct 7562 ms 282364 KB Output is correct
25 Correct 7816 ms 286032 KB Output is correct
26 Correct 7831 ms 282800 KB Output is correct
27 Execution timed out 8087 ms 317732 KB Time limit exceeded
28 Halted 0 ms 0 KB -