oj.uz

Submission #339693

# Submission time Handle Problem Language Result Execution time Memory
339693 2020-12-25T23:36:07 Z gmyu Factories (JOI14_factories) C++14
15 / 100
 8000 ms 268200 KB 
/*
ID: USACO_template
LANG: C++
PROG: https://oj.uz/problem/view/JOI14_factories
*/
#include <iostream>  //cin , cout
#include <fstream>   //fin, fout
#include <stdio.h>   // scanf , pringf
#include <cstdio>
#include <algorithm> // sort , stuff
#include <stack>     // stacks
#include <queue>     // queues
#include <map>
#include <string>
#include <set>

#include "factories.h"

using namespace std;

typedef pair<int, int>          pii;
typedef vector<int>             vi;     /// adjlist without weight
typedef vector<pii>             vii;    /// adjlist with weight
typedef vector<pair<int,pii>>   vpip;   /// edge with weight
typedef long long               ll;

#define mp  make_pair
#define fst first
#define snd second
#define pb  push_back
#define sz(x) (int)(x).size()
#define trav(u, adj_v) for (auto& u: adj_v)

const int MOD = 1e9+7;  // 998244353;
const int MX  = 2e5+5;   //
const ll  INF = 1e18;    //

#define MAXV 500007
#define MAXE 100007


bool debug;

int N, Q;
vi adjlist[MAXV];
map<int, ll> adjmap[MAXV];

struct NODE {
    vector<int> cenlist;      /// list of centroid ID for each node
    vector<ll> cenDist;    /// corresponding distance of node to each centroid
    int subtreeSize;
};
NODE nodes[MAXV];

/// centroid property
struct CENTR {
    int from;               /// the original point for centroid is from (child of upper level centroid)
    ll mdist;               /// shortest distance from red to this centriod
    bool visited;
};
CENTR cents[MAXV];

int dfs_size(int cur, int parent) {
    nodes[cur].subtreeSize = 1;
    for (int v : adjlist[cur])
        if (v != parent && !cents[v].visited)
            nodes[cur].subtreeSize += dfs_size(v, cur);
    return nodes[cur].subtreeSize;
}
int find_cent(int cur, int parent, int cenSize) {
    for (int v : adjlist[cur])
        if (v != parent && !cents[v].visited)
            if (nodes[v].subtreeSize * 2 > cenSize) // not using >=, keep centroid close to top
                return find_cent(v, cur, cenSize);
    return cur;
}
static void dfs_depth(int cur, int parent, int cid, ll depth) {
    nodes[cur].cenlist.pb(cid);
    nodes[cur].cenDist.pb(depth);
    for (int v : adjlist[cur])
        if (v != parent && !cents[v].visited)
            dfs_depth(v, cur, cid, depth + adjmap[cur][v]);
}
void buildCentriod(int top, int parent) {
    /// find centriod
    dfs_size(top, parent);
    int c = find_cent(top, parent, nodes[top].subtreeSize);
    cents[c].from = top; cents[c].mdist = INF;
    cents[c].visited = true;

    /// assign tree behavior relative to this centroid
    dfs_depth(c, 0, c, 0LL);

    /// dfs, NlgN complexity
    for (int v : adjlist[c])
        if (!cents[v].visited) buildCentriod(v, c);
}

void Init(int _N, int A[], int B[], int D[]) {
    N = _N;
    for(int i=0; i<N-1; i++) {
        int u = A[i]+1, v = B[i]+1; ll w = D[i];
        adjlist[u].pb(v); adjlist[v].pb(u);
        adjmap[u][v] = w; adjmap[v][u] = w;
    }

    buildCentriod(1, 0);
}

long long Query(int S, int X[], int T, int Y[]) {

    for(int i=1; i<=N; i++) cents[i].mdist = INF;

    for(int i=0; i<S; i++) {
        int a = X[i] + 1;
        for(int j = 0; j < sz(nodes[a].cenlist); j++) {
            int c = nodes[a].cenlist[j];
            ll w = nodes[a].cenDist[j];
            cents[c].mdist = min(cents[c].mdist, w);
        }
    }

    ll ret = INF;

    for(int i=0; i<T; i++) {
        int a = Y[i] + 1;
        for(int j = 0; j < sz(nodes[a].cenlist); j++) {
            int c = nodes[a].cenlist[j];
            ll w = nodes[a].cenDist[j] + cents[c].mdist;
            ret = min(ret, w);
        }
    }

    return ret;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 63468 KB Output is correct
2 Correct 421 ms 72940 KB Output is correct
3 Correct 432 ms 73452 KB Output is correct
4 Correct 419 ms 73580 KB Output is correct
5 Correct 445 ms 73964 KB Output is correct
6 Correct 357 ms 72844 KB Output is correct
7 Correct 437 ms 73040 KB Output is correct
8 Correct 435 ms 73068 KB Output is correct
9 Correct 445 ms 73516 KB Output is correct
10 Correct 353 ms 72300 KB Output is correct
11 Correct 426 ms 73068 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 63360 KB Output is correct
2 Execution timed out 8048 ms 268200 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 63468 KB Output is correct
2 Correct 421 ms 72940 KB Output is correct
3 Correct 432 ms 73452 KB Output is correct
4 Correct 419 ms 73580 KB Output is correct
5 Correct 445 ms 73964 KB Output is correct
6 Correct 357 ms 72844 KB Output is correct
7 Correct 437 ms 73040 KB Output is correct
8 Correct 435 ms 73068 KB Output is correct
9 Correct 445 ms 73516 KB Output is correct
10 Correct 353 ms 72300 KB Output is correct
11 Correct 426 ms 73068 KB Output is correct
12 Correct 43 ms 63360 KB Output is correct
13 Execution timed out 8048 ms 268200 KB Time limit exceeded
14 Halted 0 ms 0 KB -