oj.uz

Submission #672917

# Submission time Handle Problem Language Result Execution time Memory
672917 2022-12-19T02:07:00 Z vuavisao Roadside Advertisements (NOI17_roadsideadverts) C++14
30 / 100
 39 ms 15932 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define ll long long
using namespace std;

const ll N = 5e4 + 10;

ll n, q;
vector<pair<ll, ll>> g[N];

ll Lg, dist[N], parent[20][N];
ll s_dist[N];

ll cnt, in[N], out[N];

void dfs(ll u);
void dfs(ll u) {
    in[u] = ++ cnt;
    for(const auto& psy : g[u]) {
        ll v = psy.first, w = psy.second;
        if(v == parent[0][u]) continue;
        parent[0][v] = u;
        dist[v] = dist[u] + 1;
        s_dist[v] = s_dist[u] + w;
        dfs(v);
    }
    out[u] = cnt;
}

ll lca(ll u, ll v);
ll lca(ll u, ll v) {
    if(dist[u] < dist[v]) swap(u, v);
    ll delta = dist[u] - dist[v];
    for(ll i = Lg; i >= 0; -- i) {
        if(delta >> i & 1) u = parent[i][u];
    }
    if(u == v) return u;
    for(ll i = Lg; i >= 0; -- i) {
        if(parent[i][u] == parent[i][v]) continue;
        u = parent[i][u];
        v = parent[i][v];
    }
    return parent[0][u];
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen("NOI17_roadsideadverts.inp", "r")) {
        freopen("NOI17_roadsideadverts.inp", "r", stdin);
        freopen("NOI17_roadsideadverts.out", "w", stdout);
    }
    cin >> n;
    for(ll i = 2; i <= n; ++ i) {
        ll u, v, w; cin >> u >> v >> w;
        ++ u, ++ v;
        g[u].push_back(make_pair(v, w));
        g[v].push_back(make_pair(u, w));
    }
    dfs(1);
    Lg = __lg(n);
    for(ll j = 1; j <= Lg; ++ j) {
        for(ll i = 1; i <= n; ++ i) {
            parent[j][i] = parent[j - 1][parent[j - 1][i]];
        }
    }
    cin >> q;
    while(q-- > 0) {
        ll u[5];
        for(ll i = 0; i < 5; ++ i) {
            cin >> u[i]; ++ u[i];
        }
        sort(u + 0, u + 5, [&] (ll lhs, ll rhs) {
            return in[lhs] > in[rhs];
        });
        auto inside = [&] (ll u, ll v) {
            /// u inside v
            return in[v] <= in[u] && out[u] <= out[v];
        };
        ll res = 0;
        stack<ll> stk = {};
        for(ll i = 0; i < 5; ++ i) {
            while(!stk.empty() && inside(stk.top(), u[i])) {
                res += s_dist[stk.top()] - s_dist[u[i]];
                stk.pop();
            }
            stk.push(u[i]);
        }
        if((ll) stk.size() > 1) {
            ll last = 0;
            while(!stk.empty()) {
                if(last == 0) {
                    ll u = stk.top(); stk.pop();
                    ll v = stk.top(); stk.pop();
                    ll anc = lca(u, v);
                    res += s_dist[u] + s_dist[v] - 2 * s_dist[anc];
//                    cerr << u << ' ' << v << '\n';
                    last = anc;
                }
                else {
                    ll v = stk.top(); stk.pop();
                    ll anc = lca(last, v);
                    res += s_dist[last] + s_dist[v] - 2 * s_dist[anc];
                    last = anc;
                }
            }
        }
        cout << res << '\n';
    }
    return 0;
}

/// Code by vuavisao

Compilation message

roadsideadverts.cpp: In function 'int32_t main()':
roadsideadverts.cpp:52:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         freopen("NOI17_roadsideadverts.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
roadsideadverts.cpp:53:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         freopen("NOI17_roadsideadverts.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 13768 KB Output is correct
2 Correct 33 ms 15876 KB Output is correct
3 Correct 33 ms 15860 KB Output is correct
4 Correct 33 ms 15880 KB Output is correct
5 Correct 33 ms 15820 KB Output is correct
6 Correct 33 ms 15852 KB Output is correct
7 Correct 39 ms 15916 KB Output is correct
8 Correct 38 ms 15932 KB Output is correct
9 Correct 39 ms 15912 KB Output is correct
10 Correct 35 ms 15824 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 11932 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 36 ms 13768 KB Output is correct
3 Correct 33 ms 15876 KB Output is correct
4 Correct 33 ms 15860 KB Output is correct
5 Correct 33 ms 15880 KB Output is correct
6 Correct 33 ms 15820 KB Output is correct
7 Correct 33 ms 15852 KB Output is correct
8 Correct 39 ms 15916 KB Output is correct
9 Correct 38 ms 15932 KB Output is correct
10 Correct 39 ms 15912 KB Output is correct
11 Correct 35 ms 15824 KB Output is correct
12 Incorrect 26 ms 11932 KB Output isn't correct
13 Halted 0 ms 0 KB -