oj.uz

Submission #672916

# Submission time Handle Problem Language Result Execution time Memory
672916 2022-12-19T02:06:20 Z vuavisao Roadside Advertisements (NOI17_roadsideadverts) C++14
30 / 100
 34 ms 12016 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) {
            while(!stk.empty() && inside(stk.top(), u[i])) {
                res += s_dist[stk.top()] - s_dist[u[i]];
                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 10140 KB Output is correct
2 Correct 32 ms 11896 KB Output is correct
3 Correct 34 ms 11888 KB Output is correct
4 Correct 30 ms 12012 KB Output is correct
5 Correct 29 ms 11980 KB Output is correct
6 Correct 31 ms 12016 KB Output is correct
7 Correct 32 ms 11924 KB Output is correct
8 Correct 33 ms 11968 KB Output is correct
9 Correct 32 ms 11952 KB Output is correct
10 Correct 30 ms 11892 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 7976 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 10140 KB Output is correct
3 Correct 32 ms 11896 KB Output is correct
4 Correct 34 ms 11888 KB Output is correct
5 Correct 30 ms 12012 KB Output is correct
6 Correct 29 ms 11980 KB Output is correct
7 Correct 31 ms 12016 KB Output is correct
8 Correct 32 ms 11924 KB Output is correct
9 Correct 33 ms 11968 KB Output is correct
10 Correct 32 ms 11952 KB Output is correct
11 Correct 30 ms 11892 KB Output is correct
12 Incorrect 21 ms 7976 KB Output isn't correct
13 Halted 0 ms 0 KB -