oj.uz

Submission #321718

# Submission time Handle Problem Language Result Execution time Memory
321718 2020-11-13T05:19:42 Z arujbansal Roadside Advertisements (NOI17_roadsideadverts) C++17
100 / 100
 125 ms 16236 KB 
#include <bits/stdc++.h>

#define FAST_IO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define setIO(i, o) freopen(i, "r", stdin), freopen(o, "w", stdout)
#define seed() srand(chrono::steady_clock::now().time_since_epoch().count())
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int) (x).size()
#define lc(i) 2*i
#define rc(i) 2*i+1
//#define int long long
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vii = vector<ii>;
using vi = vector<int>;
using vvi = vector<vi>;
using vb = vector<bool>;
using vvb = vector<vb>;

ll rng() {
    ll a = rand();
    ll b = rand();
    return a * (RAND_MAX + 1ll) + b;
}

const int N = 5e4 + 5, MOD = 1e9 + 7, INF = 1e9 + 5;
vii g[N];
//int nodeWt[N];

struct LCA {
    int n, k, timer;
    vector<int> tin, tout;
    vector<vector<pair<int, int>>> par;

    void init(int x) {
        n = x;
        k = 31 - __builtin_clz(n);
        timer = 0;
        tin.resize(n);
        tout.resize(n);
        par.assign(n, vector<pair<int, int>>(k + 1, {0, 0}));
    }

    void dfs(int u = 0, int p = -1, int lastWt = 0) {
        tin[u] = timer++;
//        nodeWt[u] = lastWt;

        par[u][0].first = (p == -1 ? 0 : p);
        par[u][0].second = lastWt;

        for (int j = 1; j <= k; j++) {
            par[u][j].first = par[par[u][j - 1].first][j - 1].first;
            par[u][j].second = par[u][j - 1].second + par[par[u][j - 1].first][j  - 1].second;
        }

        for (const auto &[v, wt] : g[u]) if (v != p) dfs(v, u, wt);
        tout[u] = timer - 1;
    }

    bool isAnc(int x, int v) {
        return tin[x] <= tin[v] && tout[x] >= tout[v];
    }

    int getLCA(int u, int v) {
        if (isAnc(u, v)) return u;
        if (isAnc(v, u)) return v;
        for (int j = k; j >= 0; j--) if (!isAnc(par[u][j].first, v)) u = par[u][j].first;
        return par[u][0].first;
    }

    int getCost(int u, int v) {
        if (u == v) return 0;

        int ans = 0;

        for (int j = k; j >= 0; j--) {
            if (isAnc(par[u][j].first, v)) continue;
            ans += par[u][j].second;
            u = par[u][j].first;
        }

        return ans + par[u][0].second;
    }
};

void solve() {
    int n;
    cin >> n;

    for (int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;

        g[u].eb(v, w);
        g[v].eb(u, w);
    }

    LCA binlift;
    binlift.init(n);
    binlift.dfs();

    int q;
    cin >> q;

    while (q--) {
        vi qry(5);
        for (auto &x : qry) cin >> x;

        sort(all(qry), [&](const auto &x, const auto &y) { return binlift.tin[x] < binlift.tin[y]; });

//        for (const auto &x : qry) cout << x << " ";
//        cout << "\n";

        int root = binlift.getLCA(qry[0], qry[1]);
        for (int i = 2; i < 5; i++) root = binlift.getLCA(root, qry[i]);

        int ans = binlift.getCost(qry[0], root);

        for (int i = 1; i < 5; i++) {
            int lca = binlift.getLCA(qry[i - 1], qry[i]);
//            cout << "LCA: " << lca << " v: " << qry[i] << "\n";
            ans += binlift.getCost(qry[i], lca);
//            cout << ans << "\n";
        }

//        cout << binlift.par[2][0].second;

        cout << ans << "\n";
    }
}

signed main() {
    FAST_IO;
#ifdef arujbansal_local
    setIO("input.txt", "output.txt");
#endif

    seed();

    int tc = 1;
//    cin >> tc;
    while (tc--) solve();
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1516 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 13420 KB Output is correct
2 Correct 114 ms 14956 KB Output is correct
3 Correct 115 ms 15980 KB Output is correct
4 Correct 117 ms 16236 KB Output is correct
5 Correct 113 ms 15980 KB Output is correct
6 Correct 114 ms 15980 KB Output is correct
7 Correct 122 ms 16236 KB Output is correct
8 Correct 113 ms 15980 KB Output is correct
9 Correct 119 ms 15980 KB Output is correct
10 Correct 123 ms 15944 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 11972 KB Output is correct
2 Correct 73 ms 14316 KB Output is correct
3 Correct 74 ms 14444 KB Output is correct
4 Correct 71 ms 15084 KB Output is correct
5 Correct 77 ms 15084 KB Output is correct
6 Correct 70 ms 15084 KB Output is correct
7 Correct 70 ms 15288 KB Output is correct
8 Correct 73 ms 15084 KB Output is correct
9 Correct 78 ms 15084 KB Output is correct
10 Correct 70 ms 15084 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1516 KB Output is correct
2 Correct 110 ms 13420 KB Output is correct
3 Correct 114 ms 14956 KB Output is correct
4 Correct 115 ms 15980 KB Output is correct
5 Correct 117 ms 16236 KB Output is correct
6 Correct 113 ms 15980 KB Output is correct
7 Correct 114 ms 15980 KB Output is correct
8 Correct 122 ms 16236 KB Output is correct
9 Correct 113 ms 15980 KB Output is correct
10 Correct 119 ms 15980 KB Output is correct
11 Correct 123 ms 15944 KB Output is correct
12 Correct 56 ms 11972 KB Output is correct
13 Correct 73 ms 14316 KB Output is correct
14 Correct 74 ms 14444 KB Output is correct
15 Correct 71 ms 15084 KB Output is correct
16 Correct 77 ms 15084 KB Output is correct
17 Correct 70 ms 15084 KB Output is correct
18 Correct 70 ms 15288 KB Output is correct
19 Correct 73 ms 15084 KB Output is correct
20 Correct 78 ms 15084 KB Output is correct
21 Correct 70 ms 15084 KB Output is correct
22 Correct 110 ms 14444 KB Output is correct
23 Correct 71 ms 13344 KB Output is correct
24 Correct 114 ms 15468 KB Output is correct
25 Correct 123 ms 15468 KB Output is correct
26 Correct 125 ms 15596 KB Output is correct
27 Correct 115 ms 15468 KB Output is correct
28 Correct 120 ms 15468 KB Output is correct
29 Correct 120 ms 15596 KB Output is correct
30 Correct 118 ms 15468 KB Output is correct
31 Correct 120 ms 15468 KB Output is correct