oj.uz

Submission #549618

# Submission time Handle Problem Language Result Execution time Memory
549618 2022-04-16T07:06:24 Z SmolBrain Factories (JOI14_factories) C++17
100 / 100
 6685 ms 210132 KB 
// Om Namah Shivaya
// GM in 108 days

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define endl '\n'
#define pb push_back
#define conts continue
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
#define ff first
#define ss second
#define ceil2(x,y) ((x+y-1) / (y))
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#ifndef ONLINE_JUDGE
#define debug(x) cout << #x <<" = "; print(x); cout << endl
#else
#define debug(x)
#endif

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

bool iseven(ll n) {if ((n & 1) == 0) return true; return false;}

void print(ll t) {cout << t;}
void print(int t) {cout << t;}
void print(string t) {cout << t;}
void print(char t) {cout << t;}
void print(double t) {cout << t;}
void print(ld t) {cout << t;}

template <class T, class V> void print(pair <T, V> p);
template <class T> void print(vector <T> v);
template <class T> void print(set <T> v);
template <class T, class V> void print(map <T, V> v);
template <class T> void print(multiset <T> v);
template <class T, class V> void print(pair <T, V> p) {cout << "{"; print(p.ff); cout << ","; print(p.ss); cout << "}";}
template <class T> void print(vector <T> v) {cout << "[ "; for (T i : v) {print(i); cout << " ";} cout << "]";}
template <class T> void print(set <T> v) {cout << "[ "; for (T i : v) {print(i); cout << " ";} cout << "]";}
template <class T> void print(multiset <T> v) {cout << "[ "; for (T i : v) {print(i); cout << " ";} cout << "]";}
template <class T, class V> void print(map <T, V> v) {cout << "[ "; for (auto i : v) {print(i); cout << " ";} cout << "]";}
template<typename T> void amin(T &a, T b) { a = min(a, b); }
template<typename T> void amax(T &a, T b) { a = max(a, b); }

void usaco(string filename) {
    freopen((filename + ".in").c_str(), "r", stdin);
    freopen((filename + ".out").c_str(), "w", stdout);
}

const int MOD = 1e9 + 7;
const int maxn = 5e5 + 5;
const int inf1 = 1e9 + 5;
const ll inf2 = ll(1e18) + 5;

#include "factories.h"

vector<int> adj[maxn];
vector<pii> adj2[maxn];
vector<pll> adj3[maxn];

struct lca_algo {
    // LCA template (for graphs with 1-based indexing)

    int LOG = 1;
    vector<int> depth;
    vector<vector<int>> up;

    lca_algo() {

    }

    lca_algo(int n) {
        lca_init(n);
    }

    void lca_init(int n) {
        while ((1 << LOG) < n) LOG++;
        up = vector<vector<int>>(n + 1, vector<int>(LOG, 0));
        depth = vector<int>(n + 1);

        lca_dfs(0, -1);
    }

    void lca_dfs(int node, int par) {
        trav(child, adj[node]) {
            if (child == par) conts;

            up[child][0] = node;
            rep1(j, LOG - 1) {
                up[child][j] = up[up[child][j - 1]][j - 1];
            }

            depth[child] = depth[node] + 1;

            lca_dfs(child, node);
        }
    }

    int lift(int u, int k) {
        rep(j, LOG) {
            if (k & (1 << j)) {
                u = up[u][j];
            }
        }

        return u;
    }

    int query(int u, int v) {
        if (depth[u] < depth[v]) swap(u, v);
        int k = depth[u] - depth[v];
        u = lift(u, k);

        if (u == v) return u;

        rev(j, LOG - 1, 0) {
            if (up[u][j] != up[v][j]) {
                u = up[u][j];
                v = up[v][j];
            }
        }

        u = up[u][0];
        return u;
    }
};

vector<int> depth(maxn), tin(maxn), tout(maxn);
vector<ll> dis(maxn);
int timer = 0;
lca_algo LCA;
vector<bool> vis(maxn), type2(maxn);

void dfs1(int node, int par) {
    tin[node] = timer++;

    for (auto [child, w] : adj2[node]) {
        if (child == par) conts;

        depth[child] = depth[node] + 1;
        dis[child] = dis[node] + w;
        dfs1(child, node);
    }

    tout[node] = timer++;
}

void Init(int n, int a[], int b[], int d[]) {
    // editorial approach
    // used this code as reference: https://oj.uz/submission/529330
    // thanks to LucaDantas, the author of this code

    rep(i, n - 1) {
        int u = a[i], v = b[i], w = d[i];
        adj[u].pb(v), adj[v].pb(u);
        adj2[u].pb({v, w}), adj2[v].pb({u, w});
    }

    LCA = lca_algo(n);
    dfs1(0, -1);
}

ll getdis(ll u, ll v) {
    ll lca = LCA.query(u, v);
    ll res = dis[u] + dis[v] - 2 * dis[lca];
    return res;
}

ll Query(int n, int a[], int m, int b[]) {
    vector<pii> vals;
    rep(i, n) vals.pb({tin[a[i]], a[i]});
    rep(i, m) vals.pb({tin[b[i]], b[i]});

    sort(all(vals));

    rep(i, n + m - 1) {
        int u = vals[i].ss, v = vals[i + 1].ss;
        int lca = LCA.query(u, v);
        vals.pb({tin[lca], lca});
    }

    sort(all(vals));
    auto it = unique(all(vals));
    vals.resize(it - vals.begin());
    int siz = sz(vals);

    set<pii> st;

    rep(i, siz) {
        int u = vals[i].ss;
        auto it = st.upper_bound({tout[u], -1});

        if (it != st.end()) {
            auto [mxdepth, v] = *it;
            ll w = getdis(u, v);
            adj3[u].pb({v, w}), adj3[v].pb({u, w});
        }

        st.insert({tout[u], u});
    }

    rep(i, m) type2[b[i]] = 1;

    ll ans = 0;

    priority_queue< pll, vector<pll>, greater<pll> > pq;
    rep(i, n) pq.push({0, a[i]});

    while (!pq.empty()) {
        auto [cost, node] = pq.top();
        pq.pop();

        if (vis[node]) conts;
        vis[node] = 1;

        if (type2[node]) {
            ans = cost;
            break;
        }

        for (auto [child, w] : adj3[node]) {
            pq.push({cost + w, child});
        }
    }
    
    // resetting values
    rep(i, siz) {
        int u = vals[i].ss;
        adj3[u].clear();
        vis[u] = 0;
    }

    rep(i, m) type2[b[i]] = 0;

    return ans;
}

Compilation message

factories.cpp: In function 'void usaco(std::string)':
factories.cpp:64:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |     freopen((filename + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
factories.cpp:65:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |     freopen((filename + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 45780 KB Output is correct
2 Correct 1455 ms 54844 KB Output is correct
3 Correct 1566 ms 54636 KB Output is correct
4 Correct 1518 ms 55188 KB Output is correct
5 Correct 1211 ms 55208 KB Output is correct
6 Correct 998 ms 54924 KB Output is correct
7 Correct 1565 ms 54864 KB Output is correct
8 Correct 1602 ms 55028 KB Output is correct
9 Correct 1120 ms 55160 KB Output is correct
10 Correct 987 ms 54920 KB Output is correct
11 Correct 1645 ms 54716 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 45652 KB Output is correct
2 Correct 2763 ms 167908 KB Output is correct
3 Correct 4577 ms 171204 KB Output is correct
4 Correct 1904 ms 169996 KB Output is correct
5 Correct 3664 ms 204424 KB Output is correct
6 Correct 4978 ms 172684 KB Output is correct
7 Correct 3780 ms 77844 KB Output is correct
8 Correct 1612 ms 78124 KB Output is correct
9 Correct 2581 ms 82872 KB Output is correct
10 Correct 3601 ms 78944 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 45780 KB Output is correct
2 Correct 1455 ms 54844 KB Output is correct
3 Correct 1566 ms 54636 KB Output is correct
4 Correct 1518 ms 55188 KB Output is correct
5 Correct 1211 ms 55208 KB Output is correct
6 Correct 998 ms 54924 KB Output is correct
7 Correct 1565 ms 54864 KB Output is correct
8 Correct 1602 ms 55028 KB Output is correct
9 Correct 1120 ms 55160 KB Output is correct
10 Correct 987 ms 54920 KB Output is correct
11 Correct 1645 ms 54716 KB Output is correct
12 Correct 25 ms 45652 KB Output is correct
13 Correct 2763 ms 167908 KB Output is correct
14 Correct 4577 ms 171204 KB Output is correct
15 Correct 1904 ms 169996 KB Output is correct
16 Correct 3664 ms 204424 KB Output is correct
17 Correct 4978 ms 172684 KB Output is correct
18 Correct 3780 ms 77844 KB Output is correct
19 Correct 1612 ms 78124 KB Output is correct
20 Correct 2581 ms 82872 KB Output is correct
21 Correct 3601 ms 78944 KB Output is correct
22 Correct 5793 ms 186764 KB Output is correct
23 Correct 5645 ms 185260 KB Output is correct
24 Correct 6275 ms 193812 KB Output is correct
25 Correct 6068 ms 195412 KB Output is correct
26 Correct 6430 ms 179568 KB Output is correct
27 Correct 5362 ms 210132 KB Output is correct
28 Correct 3605 ms 190832 KB Output is correct
29 Correct 6598 ms 178312 KB Output is correct
30 Correct 6575 ms 177280 KB Output is correct
31 Correct 6685 ms 178328 KB Output is correct
32 Correct 2754 ms 94468 KB Output is correct
33 Correct 2256 ms 91440 KB Output is correct
34 Correct 3114 ms 78032 KB Output is correct
35 Correct 2964 ms 77636 KB Output is correct
36 Correct 3651 ms 78508 KB Output is correct
37 Correct 3572 ms 78336 KB Output is correct