Submission #339692

#	Time	Username	Problem	Language	Result	Execution time	Memory
339692		gmyu	Factories (JOI14_factories)	C++14	15 / 100	422 ms	49388 KiB

factories

/*
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 100007
#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 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67