Submission #1152226

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152226		jnjwnwnw	Roadside Advertisements (NOI17_roadsideadverts)	C++17	7 / 100	105 ms	13500 KiB

roadsideadverts

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

#define ll long long
#define fff(i, a, b) for(int i = a; i < b; i++)
#define fffm(i, a, b) for(int i = a; i > b; i--)
#define N 50004
#define LGN 18

ll anc[N][LGN], sm[N], dep[N];

int n, q;
vector<pair<int, ll>> adj[N];
void dfs1(int nod, int frm, int cum_sm, int dpth){
    sm[nod] = cum_sm;
    anc[nod][0] = frm;
    dep[nod] = dpth;
    for(auto [a, b]: adj[nod]){
        if (a != frm){
            dfs1(a, nod, cum_sm+b, dpth+1);
        }
    }
}

void lca_init(){
    fff(j, 1, LGN){
        fff(i, 0, n){
            anc[i][j] = anc[anc[i][j-1]][j-1];
        }
    }
}
int kthanc(int a, int k){
    fff(i, 0, LGN){
        if (k & (1<<i)){
            a = anc[a][i];
        }
    }
    return a;
}

int lca(int a, int b){
    if (dep[a] > dep[b]) swap(a, b);
    b = kthanc(b, dep[b]-dep[a]);
    if (a == b) return a;
    fffm(i, LGN-1, -1){
        if (anc[a][i] != anc[b][i]){
            a = anc[a][i];
            b = anc[b][i];
        }
    } return anc[a][0];
}


int main(){
    cin >> n;
    fff(i, 0, n-1){
        ll u, v, w; cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    dfs1(0, 0, 0, 0);
    lca_init();
    // fff(i, 0, n) cout << anc[i][0] << endl;
    // cout << lca(4, 3) << endl;
    cin >> q;
    while(q--){
        int a, b, c, d, e; cin >> a >> b >> c >> d >> e; 
        ll sm1 = sm[a] + sm[b] + sm[c] + sm[d] + sm[e];
        ll sm2 = sm[lca(a, b)] + sm[lca(a, c)] + sm[lca(a, d)] + sm[lca(a, e)] + sm[lca(b, c)] + sm[lca(b, d)] + sm[lca(b, e)] +  sm[lca(c, d)] + sm[lca(c, e)] + sm[lca(d, e)];
        // cout << lca(a, b) << lca(a, c) << lca(a, d) << lca(a, e) << lca(b, c) << lca(b, d) << lca(b, e) << lca(c, d) << lca(c, e) << lca(d, e) << endl;
        ll sm3 = sm[lca(lca(a, b), c)] + sm[lca(lca(a, b), d)] + sm[lca(lca(a, b), e)] + sm[lca(lca(a, c), d)] + sm[lca(lca(a, c), e)]+ sm[lca(lca(a, d), e)] + sm[lca(lca(b, c), d)] +  sm[lca(lca(b, c), e)] +  sm[lca(lca(b, d), e)] + sm[lca(lca(c, d), e)];
        // cout << sm[lca(lca(b, c), d)] + sm[lca(lca(b, c), e)] +  sm[lca(lca(b, d), e)] + sm[lca(lca(c, d), e)] << endl;
        ll sm4 = sm[lca(lca(a, b), lca(c, d))] + sm[lca(lca(a, b), lca(c, e))] + sm[lca(lca(a, b), lca(e, d))] + sm[lca(lca(a, e), lca(c, d))] + sm[lca(lca(e, b), lca(c, d))];
        ll sm5 = sm[lca(lca(lca(a, b), lca(c, d)), e)];
        // cout << sm1 << " " << sm2 << " " << sm3 << " " << sm4 << " " << sm5 << endl;
        cout << sm1 - sm2 + sm3 - sm4 + sm5 << endl;

    }
}

• Subtask 1: 7 / 7
• Subtask 2: 0 / 23
• Subtask 3: 0 / 40
• Subtask 4: 0 / 30