oj.uz

Submission #339696

# Submission time Handle Problem Language Result Execution time Memory
339696 2020-12-25T23:47:38 Z gmyu Factories (JOI14_factories) C++14
100 / 100
 6698 ms 419660 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];
int qct;

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;
    int cleared;
};
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; cents[c].cleared = -1;

    /// 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);
    qct=0;
}

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

    qct++;

    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];
            if(cents[c].cleared != qct) {
                cents[c].mdist = w;
                cents[c].cleared = qct;
            } else {
                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];
            if(cents[c].cleared == qct) {
                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 49 ms 63596 KB Output is correct
2 Correct 420 ms 74476 KB Output is correct
3 Correct 446 ms 74860 KB Output is correct
4 Correct 434 ms 74732 KB Output is correct
5 Correct 453 ms 75160 KB Output is correct
6 Correct 331 ms 73964 KB Output is correct
7 Correct 443 ms 73472 KB Output is correct
8 Correct 442 ms 73580 KB Output is correct
9 Correct 453 ms 74016 KB Output is correct
10 Correct 329 ms 72812 KB Output is correct
11 Correct 444 ms 73452 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 63212 KB Output is correct
2 Correct 3769 ms 270484 KB Output is correct
3 Correct 5202 ms 323788 KB Output is correct
4 Correct 2454 ms 200308 KB Output is correct
5 Correct 6248 ms 392552 KB Output is correct
6 Correct 5271 ms 325064 KB Output is correct
7 Correct 1601 ms 128372 KB Output is correct
8 Correct 934 ms 113120 KB Output is correct
9 Correct 1755 ms 141676 KB Output is correct
10 Correct 1607 ms 129516 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 63596 KB Output is correct
2 Correct 420 ms 74476 KB Output is correct
3 Correct 446 ms 74860 KB Output is correct
4 Correct 434 ms 74732 KB Output is correct
5 Correct 453 ms 75160 KB Output is correct
6 Correct 331 ms 73964 KB Output is correct
7 Correct 443 ms 73472 KB Output is correct
8 Correct 442 ms 73580 KB Output is correct
9 Correct 453 ms 74016 KB Output is correct
10 Correct 329 ms 72812 KB Output is correct
11 Correct 444 ms 73452 KB Output is correct
12 Correct 42 ms 63212 KB Output is correct
13 Correct 3769 ms 270484 KB Output is correct
14 Correct 5202 ms 323788 KB Output is correct
15 Correct 2454 ms 200308 KB Output is correct
16 Correct 6248 ms 392552 KB Output is correct
17 Correct 5271 ms 325064 KB Output is correct
18 Correct 1601 ms 128372 KB Output is correct
19 Correct 934 ms 113120 KB Output is correct
20 Correct 1755 ms 141676 KB Output is correct
21 Correct 1607 ms 129516 KB Output is correct
22 Correct 4109 ms 294380 KB Output is correct
23 Correct 4225 ms 298608 KB Output is correct
24 Correct 5700 ms 349148 KB Output is correct
25 Correct 5742 ms 352616 KB Output is correct
26 Correct 5697 ms 349276 KB Output is correct
27 Correct 6698 ms 419660 KB Output is correct
28 Correct 2768 ms 227668 KB Output is correct
29 Correct 5672 ms 349224 KB Output is correct
30 Correct 5685 ms 349348 KB Output is correct
31 Correct 5686 ms 348856 KB Output is correct
32 Correct 1747 ms 142316 KB Output is correct
33 Correct 912 ms 113764 KB Output is correct
34 Correct 1315 ms 122388 KB Output is correct
35 Correct 1349 ms 122956 KB Output is correct
36 Correct 1552 ms 126556 KB Output is correct
37 Correct 1559 ms 126700 KB Output is correct