oj.uz

Submission #765090

# Submission time Handle Problem Language Result Execution time Memory
765090 2023-06-24T08:20:11 Z vjudge1 Roadside Advertisements (NOI17_roadsideadverts) C++17
30 / 100
 64 ms 58012 KB 
#include <bits/stdc++.h>
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
// #pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")
#define ent '\n'
#define f first
#define s second

using namespace std;
typedef long long ll;
typedef pair < int, int> pii;
typedef pair < ll, ll > pll;

const int maxn = 2e6 + 100;
const int mod = 1e9 + 7;
const int INF = 1e9;
const int LOG = 20;
const int K = 400;
const int P = 31;

int n, m;
vector < pii > g[maxn];
int pref[maxn], p[LOG][maxn], tin[maxn], tout[maxn], timer, depth[maxn];

void dfs(int v){
    for(int i = 1;i < LOG;i++){
        p[i][v] = p[i - 1][p[i - 1][v]];
    }
    tin[v] = ++timer;
    for(auto to: g[v]){
        if(to.f == p[0][v])continue;
        p[0][to.f] = v;
        depth[to.f] = depth[v] + 1;
        pref[to.f] = pref[v] + to.s;
        dfs(to.f);
    }
    tout[v] = ++timer;
}

bool upper(int a, int b){return tin[a] <= tin[b] && tout[a] >= tout[b];}

int lca(int a, int b){
    if(upper(a, b))return a;
    if(upper(b, a))return b;
    for(int i = LOG - 1;i >= 0;i--){
        if(!upper(p[i][a], b) && p[i][a] != 0)a = p[i][a];
    }
    return p[0][a];
}

void solve(){
    cin >> n;
    for(int i = 1;i < n;i++){
        int u, v, w;
        cin >> u >> v >> w;
        u++, v++;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    dfs(1);
    cin >> m;
    for(int i = 1;i <= m;i++){
        int a, b, c, d, e;
        cin >> a >> b >> c >> d >> e;
        a++, b++, c++, d++, e++;
        vector < pii > v;
        v.push_back({depth[a], a});
        v.push_back({depth[b], b});
        v.push_back({depth[c], c});
        v.push_back({depth[d], d});
        v.push_back({depth[e], e});
        sort(v.begin(), v.end());
        a = v[0].s, b = v[1].s, c = v[2].s, d = v[3].s, e = v[4].s;
        ll ans = 0;
        int LCA_DE = lca(d, e);
        ans = (pref[e] - pref[LCA_DE]) + (pref[d] - pref[LCA_DE]);
        int LCA_CD = lca(c, LCA_DE);
        if(upper(c, e) == 0 && upper(c, d) == 0){
            ans += (pref[LCA_DE] - pref[LCA_CD]) + (pref[c] - pref[LCA_CD]);
        } else if(depth[c] < depth[LCA_DE]){
            ans += (pref[LCA_DE] - pref[c]);
        }
        int LCA_BC = lca(b, LCA_CD);
        if(upper(b, c) == 0 && upper(b, d) == 0 && upper(b, e) == 0){
            ans += (pref[LCA_CD] - pref[LCA_BC]) + (pref[b] - pref[LCA_BC]);
        } else if(depth[b] < depth[LCA_CD]){
            ans += (pref[LCA_CD] - pref[b]);
        }
        int LCA_AB = lca(a, LCA_BC);
        if(upper(a, b) == 0 && upper(a, c) == 0 && upper(a, d) == 0 && upper(a, e) == 0){
            ans += (pref[LCA_BC] - pref[LCA_AB]) + (pref[a] - pref[LCA_AB]);
        } else if(depth[a] < depth[LCA_BC]){
            ans += (pref[LCA_BC] - pref[a]);
        }
        cout << ans << ent;
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T = 1;
    // cin >> T;
    for(int i = 1;i <= T;i++){
        solve();
    }
}

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 55808 KB Output is correct
2 Correct 51 ms 57932 KB Output is correct
3 Correct 53 ms 57900 KB Output is correct
4 Correct 64 ms 58012 KB Output is correct
5 Correct 60 ms 57932 KB Output is correct
6 Correct 52 ms 57948 KB Output is correct
7 Correct 52 ms 57968 KB Output is correct
8 Correct 51 ms 57908 KB Output is correct
9 Correct 55 ms 57912 KB Output is correct
10 Correct 52 ms 57864 KB Output is correct

Subtask #3
0 / 40.0

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

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 47476 KB Output is correct
2 Correct 56 ms 55808 KB Output is correct
3 Correct 51 ms 57932 KB Output is correct
4 Correct 53 ms 57900 KB Output is correct
5 Correct 64 ms 58012 KB Output is correct
6 Correct 60 ms 57932 KB Output is correct
7 Correct 52 ms 57948 KB Output is correct
8 Correct 52 ms 57968 KB Output is correct
9 Correct 51 ms 57908 KB Output is correct
10 Correct 55 ms 57912 KB Output is correct
11 Correct 52 ms 57864 KB Output is correct
12 Incorrect 40 ms 53920 KB Output isn't correct
13 Halted 0 ms 0 KB -