oj.uz

Submission #270665

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

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 27 ms 24312 KB Output is correct
2 Correct 558 ms 33656 KB Output is correct
3 Correct 706 ms 33848 KB Output is correct
4 Correct 704 ms 34168 KB Output is correct
5 Correct 673 ms 34552 KB Output is correct
6 Correct 392 ms 34040 KB Output is correct
7 Correct 787 ms 34248 KB Output is correct
8 Correct 721 ms 34296 KB Output is correct
9 Correct 679 ms 34552 KB Output is correct
10 Correct 359 ms 33912 KB Output is correct
11 Correct 697 ms 34136 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 24192 KB Output is correct
2 Correct 3861 ms 261000 KB Output is correct
3 Correct 5499 ms 280596 KB Output is correct
4 Correct 1364 ms 240480 KB Output is correct
5 Correct 6676 ms 322524 KB Output is correct
6 Correct 5856 ms 281588 KB Output is correct
7 Correct 2747 ms 77048 KB Output is correct
8 Correct 830 ms 72684 KB Output is correct
9 Correct 2302 ms 83320 KB Output is correct
10 Correct 2627 ms 78456 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 24312 KB Output is correct
2 Correct 558 ms 33656 KB Output is correct
3 Correct 706 ms 33848 KB Output is correct
4 Correct 704 ms 34168 KB Output is correct
5 Correct 673 ms 34552 KB Output is correct
6 Correct 392 ms 34040 KB Output is correct
7 Correct 787 ms 34248 KB Output is correct
8 Correct 721 ms 34296 KB Output is correct
9 Correct 679 ms 34552 KB Output is correct
10 Correct 359 ms 33912 KB Output is correct
11 Correct 697 ms 34136 KB Output is correct
12 Correct 19 ms 24192 KB Output is correct
13 Correct 3861 ms 261000 KB Output is correct
14 Correct 5499 ms 280596 KB Output is correct
15 Correct 1364 ms 240480 KB Output is correct
16 Correct 6676 ms 322524 KB Output is correct
17 Correct 5856 ms 281588 KB Output is correct
18 Correct 2747 ms 77048 KB Output is correct
19 Correct 830 ms 72684 KB Output is correct
20 Correct 2302 ms 83320 KB Output is correct
21 Correct 2627 ms 78456 KB Output is correct
22 Correct 5222 ms 262136 KB Output is correct
23 Correct 5284 ms 265224 KB Output is correct
24 Correct 7494 ms 281976 KB Output is correct
25 Correct 7836 ms 285620 KB Output is correct
26 Correct 7570 ms 282488 KB Output is correct
27 Execution timed out 8064 ms 317792 KB Time limit exceeded
28 Halted 0 ms 0 KB -