oj.uz

Submission #672918

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

const int N = 5e4 + 10;

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

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

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

void dfs(int u);
void dfs(int u) {
    in[u] = ++ cnt;
    for(const auto& psy : g[u]) {
        int 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;
}

int lca(int u, int v);
int lca(int u, int v) {
    if(dist[u] < dist[v]) swap(u, v);
    int delta = dist[u] - dist[v];
    for(int i = Lg; i >= 0; -- i) {
        if(delta >> i & 1) u = parent[i][u];
    }
    if(u == v) return u;
    for(int 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(int i = 2; i <= n; ++ i) {
        int 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(int j = 1; j <= Lg; ++ j) {
        for(int i = 1; i <= n; ++ i) {
            parent[j][i] = parent[j - 1][parent[j - 1][i]];
        }
    }
    cin >> q;
    while(q-- > 0) {
        int u[5];
        for(int i = 0; i < 5; ++ i) {
            cin >> u[i]; ++ u[i];
        }
        sort(u + 0, u + 5, [&] (int lhs, int rhs) {
            return in[lhs] > in[rhs];
        });
        auto inside = [&] (int u, int v) {
            /// u inside v
            return in[v] <= in[u] && out[u] <= out[v];
        };
        int res = 0;
        stack<int> stk = {};
        for(int i = 0; i < 5; ++ i) {
            int last = 0;
            while(!stk.empty() && inside(stk.top(), u[i])) {
                res += s_dist[stk.top()] - s_dist[u[i]];
                if(last == 0) {
                    last = stk.top();
                }
                else {
                    int anc = lca(last, stk.top());
                    res -= s_dist[anc] - s_dist[u[i]];
                    last = anc;
                }
                stk.pop();
            }
            stk.push(u[i]);
        }
        if((int) stk.size() > 1) {
            int last = 0;
            while(!stk.empty()) {
                if(last == 0) {
                    int u = stk.top(); stk.pop();
                    int v = stk.top(); stk.pop();
                    int anc = lca(u, v);
                    res += s_dist[u] + s_dist[v] - 2 * s_dist[anc];
//                    cerr << u << ' ' << v << '\n';
                    last = anc;
                }
                else {
                    int v = stk.top(); stk.pop();
                    int 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 32 ms 9020 KB Output is correct
2 Correct 31 ms 10852 KB Output is correct
3 Correct 30 ms 10952 KB Output is correct
4 Correct 38 ms 10956 KB Output is correct
5 Correct 30 ms 10848 KB Output is correct
6 Correct 29 ms 10936 KB Output is correct
7 Correct 29 ms 10908 KB Output is correct
8 Correct 29 ms 10936 KB Output is correct
9 Correct 30 ms 10872 KB Output is correct
10 Correct 29 ms 10936 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 7252 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 32 ms 9020 KB Output is correct
3 Correct 31 ms 10852 KB Output is correct
4 Correct 30 ms 10952 KB Output is correct
5 Correct 38 ms 10956 KB Output is correct
6 Correct 30 ms 10848 KB Output is correct
7 Correct 29 ms 10936 KB Output is correct
8 Correct 29 ms 10908 KB Output is correct
9 Correct 29 ms 10936 KB Output is correct
10 Correct 30 ms 10872 KB Output is correct
11 Correct 29 ms 10936 KB Output is correct
12 Incorrect 19 ms 7252 KB Output isn't correct
13 Halted 0 ms 0 KB -