oj.uz

Submission #765135

# Submission time Handle Problem Language Result Execution time Memory
765135 2023-06-24T08:37:01 Z vjudge1 Roadside Advertisements (NOI17_roadsideadverts) C++17
70 / 100
 232 ms 57800 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];
int a, b, c, d, e;
ll ans = 0;
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];
}

int dfs2(int v, int pa, int cal){
    bool ok = 0;
    if(v == b || v == c || v == d || v == e){
        ans += cal;
        ok = 1;
    }
    for(pii to: g[v]){
        if(to.f == pa)continue;
        int c;
        if(!ok)c = dfs2(to.f, v, to.s + cal);
        else c = dfs2(to.f, v, to.s);
        if(c){
            ok = 1;
        }
    }
    return ok;
}

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;
    if(m <= 100){
        for(int i = 1;i <= m;i++){
            cin >> a >> b >> c >> d >> e;
            a++, b++, c++, d++, e++;
            dfs2(a, -1, 0);
            cout << ans << ent;
            ans = 0;
        }
        return;
    }
    for(int i = 1;i <= m;i++){
        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;
        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;
        ans = 0;
    }
}

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 21 ms 47468 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 55788 KB Output is correct
2 Correct 49 ms 57728 KB Output is correct
3 Correct 50 ms 57696 KB Output is correct
4 Correct 60 ms 57616 KB Output is correct
5 Correct 50 ms 57632 KB Output is correct
6 Correct 66 ms 57800 KB Output is correct
7 Correct 50 ms 57692 KB Output is correct
8 Correct 49 ms 57712 KB Output is correct
9 Correct 51 ms 57700 KB Output is correct
10 Correct 51 ms 57664 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 54028 KB Output is correct
2 Correct 222 ms 57000 KB Output is correct
3 Correct 229 ms 57008 KB Output is correct
4 Correct 232 ms 56920 KB Output is correct
5 Correct 220 ms 57004 KB Output is correct
6 Correct 217 ms 56928 KB Output is correct
7 Correct 220 ms 56984 KB Output is correct
8 Correct 224 ms 57100 KB Output is correct
9 Correct 217 ms 57008 KB Output is correct
10 Correct 223 ms 57008 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47468 KB Output is correct
2 Correct 50 ms 55788 KB Output is correct
3 Correct 49 ms 57728 KB Output is correct
4 Correct 50 ms 57696 KB Output is correct
5 Correct 60 ms 57616 KB Output is correct
6 Correct 50 ms 57632 KB Output is correct
7 Correct 66 ms 57800 KB Output is correct
8 Correct 50 ms 57692 KB Output is correct
9 Correct 49 ms 57712 KB Output is correct
10 Correct 51 ms 57700 KB Output is correct
11 Correct 51 ms 57664 KB Output is correct
12 Correct 135 ms 54028 KB Output is correct
13 Correct 222 ms 57000 KB Output is correct
14 Correct 229 ms 57008 KB Output is correct
15 Correct 232 ms 56920 KB Output is correct
16 Correct 220 ms 57004 KB Output is correct
17 Correct 217 ms 56928 KB Output is correct
18 Correct 220 ms 56984 KB Output is correct
19 Correct 224 ms 57100 KB Output is correct
20 Correct 217 ms 57008 KB Output is correct
21 Correct 223 ms 57008 KB Output is correct
22 Correct 53 ms 56008 KB Output is correct
23 Incorrect 50 ms 54064 KB Output isn't correct
24 Halted 0 ms 0 KB -