oj.uz

Submission #339692

# Submission time Handle Problem Language Result Execution time Memory
339692 2020-12-25T23:34:55 Z gmyu Factories (JOI14_factories) C++14
15 / 100
 422 ms 49388 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 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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 13548 KB Output is correct
2 Correct 373 ms 25056 KB Output is correct
3 Correct 408 ms 25196 KB Output is correct
4 Correct 392 ms 25068 KB Output is correct
5 Correct 413 ms 25708 KB Output is correct
6 Correct 312 ms 24556 KB Output is correct
7 Correct 399 ms 32364 KB Output is correct
8 Correct 407 ms 32500 KB Output is correct
9 Correct 422 ms 32720 KB Output is correct
10 Correct 325 ms 31644 KB Output is correct
11 Correct 399 ms 32408 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 13428 KB Output is correct
2 Runtime error 421 ms 49388 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 13548 KB Output is correct
2 Correct 373 ms 25056 KB Output is correct
3 Correct 408 ms 25196 KB Output is correct
4 Correct 392 ms 25068 KB Output is correct
5 Correct 413 ms 25708 KB Output is correct
6 Correct 312 ms 24556 KB Output is correct
7 Correct 399 ms 32364 KB Output is correct
8 Correct 407 ms 32500 KB Output is correct
9 Correct 422 ms 32720 KB Output is correct
10 Correct 325 ms 31644 KB Output is correct
11 Correct 399 ms 32408 KB Output is correct
12 Correct 11 ms 13428 KB Output is correct
13 Runtime error 421 ms 49388 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -