Submission #1184173

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184173		tin_le	Factories (JOI14_factories)	C++17	100 / 100	3987 ms	326272 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define vt vector
#define all(x) begin(x), end(x)
#define allr(x) rbegin(x), rend(x)
#define ub upper_bound
#define lb lower_bound
#define db double
#define ld long db
#define ll long long
#define ull unsigned long long
#define vll vt<ll>  
#define vvll vt<vll>
#define pll pair<ll, ll>    
#define vpll vt<pll>
#define vvpll vt<vpll>
#define vc vt<char> 
#define vvc vt<vc>
#define vi vt<int>
#define vvi vt<vi>
#define vvvi vt<vvi>
#define pii pair<int, int>
#define vpii vt<pii>
#define vs vt<string>
#define vvs vt<vs>
#define vb vt<bool>
#define vvb vt<vb>
#define vvpii vt<vpii>
#define vd vt<db>
#define ar(x) array<int, x>
#define var(x) vt<ar(x)>
#define vvar(x) vt<var(x)>
#define al(x) array<ll, x>
#define vall(x) vt<al(x)>
#define vvall(x) vt<vall(x)>
#define mset(m, v) memset(m, v, sizeof(m))
#define pb push_back
#define ff first
#define ss second
#define sv string_view
#define MP make_pair
#define MT make_tuple
#define rsz resize

template<typename T, size_t N>
istream& operator>>(istream& is, array<T, N>& arr) {
    for (size_t i = 0; i < N; i++) { is >> arr[i]; } return is;
}

template<typename T, size_t N>
istream& operator>>(istream& is, vector<array<T, N>>& vec) {
    for (auto &arr : vec) { is >> arr; } return is;
}
    
template <typename T1, typename T2>  istream &operator>>(istream& in, pair<T1, T2>& input) {    return in >> input.ff >> input.ss; }
    
template <typename T> istream &operator>>(istream &in, vector<T> &v) { for (auto &el : v) in >> el; return in; }
template<typename K, typename V>
auto operator<<(std::ostream &o, const std::map<K, V> &m) -> std::ostream& {
    o << "{"; int i = 0;
    for (const auto &[key, value] : m) { if (i++) o << " , "; o << key << " : " << value; }
    return o << "}";
}

#ifdef LOCAL
#define debug(x...) debug_out(#x, x)
void debug_out(const char* names) { std::cerr << std::endl; }
template <typename T, typename... Args>
void debug_out(const char* names, T value, Args... args) {
    const char* comma = strchr(names, ',');
    std::cerr << "[" << (comma ? std::string(names, comma) : names) << " = " << value << "]";
    if (sizeof...(args)) { std::cerr << ", "; debug_out(comma + 1, args...); }   
    else { std::cerr << std::endl; }
}
template<typename T1, typename T2>
std::ostream& operator<<(std::ostream& o, const std::pair<T1, T2>& p) { return o << "{" << p.ff << " , " << p.ss << "}"; }
auto operator<<(auto &o, const auto &x) -> decltype(end(x), o) {
    o << "{"; int i = 0; for (const auto &e : x) { if (i++) o << " , "; o << e; } return o << "}";
} // remove for leetcode
#include <sys/resource.h>
#include <sys/time.h>
void printMemoryUsage() {
    struct rusage usage;
    getrusage(RUSAGE_SELF, &usage);
    double memoryMB = usage.ru_maxrss / 1024.0;
    cerr << "Memory usage: " << memoryMB << " MB" << "\n";
}

#define startClock clock_t tStart = clock();
#define endClock std::cout << std::fixed << std::setprecision(10) << "\nTime Taken: " << (double)(clock() - tStart) / CLOCKS_PER_SEC << " seconds" << std::endl;
#else
#define debug(...)
#define startClock
#define endClock

#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const static ll INF = 1LL << 62;
const static int inf = 1e9 + 100;
template<typename T, typename F = function<T(const T&, const T&)>>
class SparseTable { public: int n, m; vt<vt<T>> st; vi log_table; F func; SparseTable() {} SparseTable(const vt<T>& a, F func) : n(a.size()), func(func) { m = floor(log2(n)) + 1; st.resize(m); for (int j = 0; j < m; j++) st[j].resize(n - (1 << j) + 1); log_table.resize(n + 1); for (int i = 2; i <= n; i++) log_table[i] = log_table[i / 2] + 1; for (int i = 0; i < n; i++) st[0][i] = a[i]; for (int j = 1; j < m; j++) { for (int i = 0; i + (1 << j) <= n; i++) st[j][i] = func(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]); } } T query(int L, int R) { int j = log_table[R - L + 1]; return func(st[j][L], st[j][R - (1 << j) + 1]); } }; template<typename T = int> struct LCA_O1 { vi enter; vpii euler; SparseTable<pii> st; int timer; LCA_O1() {} LCA_O1(const vt<vt<T>> &graph, int root = 0) : timer(0) { int n = graph.size(); enter.resize(n, -1); dfs(root, -1, 0, graph); st = SparseTable<pii>(euler, [](const pii &a, const pii &b) { return (a.first < b.first) ? a : b; }); vpii().swap(euler); } void dfs(int node, int par, int d, const vt<vt<T>> &graph) { enter[node] = timer++; euler.pb({d, node}); for(auto& [nxt, w] : graph[node]) { if(nxt == par) continue; dfs(nxt, node, d + 1, graph); euler.pb({d, node}); timer++; } } int lca(int u, int v) { int L = min(enter[u], enter[v]); int R = max(enter[u], enter[v]); return st.query(L, R).second; } }; template<typename T = int> class GRAPH { public: int n, m; vvi dp; vi parent, subtree; vll depth; vi tin, tout, low, ord; int timer = 0; LCA_O1<T> lca_01; GRAPH() {} GRAPH(const vt<vt<T>>& graph, int root = 0) : lca_01(graph, root) {   n = graph.size(); m = log2(n) + 1; dp.rsz(n, vi(m)); depth.rsz(n); parent.rsz(n, -1); subtree.rsz(n, 1); tin.rsz(n); tout.rsz(n); ord.rsz(n); dfs(graph, root); init(); } void dfs(const vt<vt<T>>& graph, int node = 0, int par = -1) {   tin[node] = timer++; ord[tin[node]] = node; for(auto& [nei, w] : graph[node]) {  if(nei == par) continue;    depth[nei] = depth[node] + w; dp[nei][0] = node; parent[nei] = node; dfs(graph, nei, node); subtree[node] += subtree[nei]; } tout[node] = timer - 1; } bool isAncestor(int u, int v) { return tin[u] <= tin[v] && tin[v] <= tout[u]; } void init() {  for(int j = 1; j < m; j++) {   for(int i = 0; i < n; i++) {    dp[i][j] = dp[dp[i][j - 1]][j - 1]; } } } int lca(int a, int b) { return lca_01.lca(a, b); } ll dist(int u, int v) {    int a = lca_01.lca(u, v);  return depth[u] + depth[v] - 2 * depth[a]; } int k_ancestor(int a, int k) { for(int i = m - 1; i >= 0; i--) {   if((k >> i) & 1) a = dp[a][i]; } return a; } int rooted_lca(int a, int b, int c) { return lca(a, c) ^ lca(a, b) ^ lca(b, c); } int rooted_parent(int u, int v) { return k_ancestor(v, depth[v] - depth[u] - 1); } void reroot(int root) { fill(all(parent), -1); dfs(root); init(); } }; template<typename T> struct CD { int n, root; vt<vt<T>> graph; vi size, parent, vis; ll ans; GRAPH<T> g; vll best; CD(const vt<vt<T>>& graph) : graph(graph), n(graph.size()), g(graph), best(graph.size(), INF) { ans = 0; size.rsz(n); parent.rsz(n, -1); vis.rsz(n); root = init(); } void get_size(int node, int par) { size[node] = 1; for(auto& [nei, w] : graph[node]) { if(nei == par || vis[nei]) continue; get_size(nei, node); size[node] += size[nei]; } } int get_center(int node, int par, int size_of_tree) { for(auto& [nei, w] : graph[node]) { if(nei == par || vis[nei]) continue; if(size[nei] * 2 > size_of_tree) return get_center(nei, node, size_of_tree); } return node; } int get_centroid(int src) { get_size(src, -1); int centroid = get_center(src, -1, size[src]); vis[centroid] = true; return centroid; } int mx; void modify(int node, int par, int depth, int delta) { for(auto& [nei, w] : graph[node]) { if(vis[nei] || nei == par) continue; modify(nei, node, depth + 1, delta); } } void cal(int node, int par, int depth) { for(auto& [nei, w] : graph[node]) { if(vis[nei] || nei == par) continue; cal(nei, node, depth + 1); } } int get_max_depth(int node, int par = -1, int depth = 0) { int max_depth = depth; for(auto& [nei, w] : graph[node]) { if(nei == par || vis[nei]) continue; max_depth = max(max_depth, get_max_depth(nei, node, depth + 1)); } return max_depth; } void run(int root, int par) { mx = get_max_depth(root, par); for(auto& [nei, w] : graph[root]) { if(vis[nei] || nei == par) continue; cal(nei, root, 1); modify(nei, root, 1, 1); } } int init(int root = 0, int par = -1) { root = get_centroid(root); parent[root] = par; run(root, par); for(auto&[nei, w] : graph[root]) { if(nei == par || vis[nei]) continue; init(nei, root); } return root; }
    vi now;
    void update(int node, int delta) {
        int u = node;
        while(u != -1) {
            now.pb(u);
            best[u] = min(best[u], g.dist(u, node));
            u = parent[u];
        }
    }
    CD() {}

    ll get_ans(int node) {
        int u = node;
        ll res = INF;
        while(u != -1){ 
            if(best[u] != INF) {
                res = min(res, g.dist(u, node) + best[u]);
            }
            u = parent[u];
        }
        return res;
    }
};

CD<pii> g;
void Init(int n, int a[], int b[], int d[]) {
    vvpii graph(n);
    for(int i = 0; i < n - 1; i++) {
        int u = a[i], v = b[i], w = d[i];
        graph[u].pb({v, w});
        graph[v].pb({u, w});
    }
    g = CD<pii>(graph);
}

ll Query(int S, int x[], int T, int y[]) {
    for(int i = 0; i < S; i++) {
        g.update(x[i], 1);
    }
    ll res = INF;
    for(int i = 0; i < T; i++) {
        res = min(res, g.get_ans(y[i]));
    }
    auto& curr = g.now;
    for(auto& u : g.now) {
        g.best[u] = INF;
    }
    vi().swap(curr);
    return res;
}

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67