oj.uz

Submission #270662

# Submission time Handle Problem Language Result Execution time Memory
270662 2020-08-17T21:12:52 Z MKopchev Factories (JOI14_factories) C++14
33 / 100
 8000 ms 346136 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=1e6+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][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 43 ms 47864 KB Output is correct
2 Correct 588 ms 57256 KB Output is correct
3 Correct 741 ms 57280 KB Output is correct
4 Correct 725 ms 57336 KB Output is correct
5 Correct 725 ms 57708 KB Output is correct
6 Correct 384 ms 57208 KB Output is correct
7 Correct 735 ms 57636 KB Output is correct
8 Correct 740 ms 57336 KB Output is correct
9 Correct 695 ms 57592 KB Output is correct
10 Correct 376 ms 57080 KB Output is correct
11 Correct 721 ms 57464 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 47608 KB Output is correct
2 Correct 3792 ms 284716 KB Output is correct
3 Correct 5454 ms 304712 KB Output is correct
4 Correct 1363 ms 263772 KB Output is correct
5 Correct 6628 ms 346136 KB Output is correct
6 Correct 5557 ms 305808 KB Output is correct
7 Correct 2843 ms 100900 KB Output is correct
8 Correct 829 ms 96996 KB Output is correct
9 Correct 2482 ms 107576 KB Output is correct
10 Correct 2861 ms 102896 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 47864 KB Output is correct
2 Correct 588 ms 57256 KB Output is correct
3 Correct 741 ms 57280 KB Output is correct
4 Correct 725 ms 57336 KB Output is correct
5 Correct 725 ms 57708 KB Output is correct
6 Correct 384 ms 57208 KB Output is correct
7 Correct 735 ms 57636 KB Output is correct
8 Correct 740 ms 57336 KB Output is correct
9 Correct 695 ms 57592 KB Output is correct
10 Correct 376 ms 57080 KB Output is correct
11 Correct 721 ms 57464 KB Output is correct
12 Correct 34 ms 47608 KB Output is correct
13 Correct 3792 ms 284716 KB Output is correct
14 Correct 5454 ms 304712 KB Output is correct
15 Correct 1363 ms 263772 KB Output is correct
16 Correct 6628 ms 346136 KB Output is correct
17 Correct 5557 ms 305808 KB Output is correct
18 Correct 2843 ms 100900 KB Output is correct
19 Correct 829 ms 96996 KB Output is correct
20 Correct 2482 ms 107576 KB Output is correct
21 Correct 2861 ms 102896 KB Output is correct
22 Correct 5158 ms 285984 KB Output is correct
23 Correct 5339 ms 288784 KB Output is correct
24 Correct 7578 ms 306120 KB Output is correct
25 Correct 7512 ms 309868 KB Output is correct
26 Correct 7624 ms 306604 KB Output is correct
27 Execution timed out 8100 ms 341540 KB Time limit exceeded
28 Halted 0 ms 0 KB -