Submission #765201

#	Time	Username	Problem	Language	Result	Execution time	Memory
765201		vjudge1	Roadside Advertisements (NOI17_roadsideadverts)	C++17	7 / 100	84 ms	9840 KiB

roadsideadverts

//Bismillahir-Rahmanir-Rahim

#include <bits/stdc++.h>
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#define pb push_back
#define pii pair <int, int>
#define pll pair <long long, long long>
#define pld pair <ld, ld>
#define ll long long
#define ld long double
#define x first
#define y second
#define all(v) v.begin(),v.end()
#define sz(s) (int)s.size()
#define skip continue
#define bpop(x) (ll)__builtin_popcountll(x)

using namespace std;

const int N = 5e4 + 7;
const int M = 3e5 + 7;
const int MAXA = 1e6 + 7;
const int inf = 1e9 + 7;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ld eps = 1e-4;

pii dir[] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

#define int long long

vector <pii> g[N];
bitset <4 * N> z;
int n, q, T, a[N], sz[N], d[N], p[N], heavy[N], head[N], tin[N], V[N], ord[N], t[4 * N];
void dfs(int v) {
    sz[v] = 1, heavy[v] = 0;
    for (auto to : g[v]) {
        if (to.x == p[v])skip;
        p[to.x] = v, d[to.x] = d[v] + 1;
        dfs(to.x);
        sz[v] += sz[to.x];
        if (sz[to.x] > sz[heavy[v]])heavy[v] = to.x;
    }
}
void push(int v, int tl, int tr) {
    if (z[v] == 0)return;
    if (tl != tr)z[v * 2] = z[v * 2 + 1] = 1;
}
void update(int v, int tl, int tr, int pos, int x) {
    if (tl == tr) {
        t[v] = x;
        //cout << pos << ' ' << pos << ':' << x << '\n';
        return;
    }
    int mid = (tl + tr) / 2;
    if (pos <= mid)update(v * 2, tl, mid, pos, x);
    else update(v * 2 + 1, mid + 1, tr, pos, x);
    t[v] = t[v * 2] + t[v * 2 + 1];
    //cout << tl << ' ' << tr << ':' << t[v] << '\n';
}
int get(int v, int tl, int tr, int l, int r) {
    push(v, tl, tr);
    if (tr < l || tl > r)return 0;
    if (tl >= l && tr <= r) {
        int x = t[v] * (1 - z[v]);
        z[v] = 1;
        push(v, tl, tr);
        return x;
    }
    int mid = (tl + tr) / 2;
    return get(v * 2, tl, mid, l, r) + get(v * 2 + 1, mid + 1, tr, l, r);
}
void decompose(int v, int h) {
    tin[v] = ++T, head[v] = h, ord[T] = v;
    //cout << v << ':' << T << '\n';
    if (heavy[v])decompose(heavy[v], h);
    for (auto to : g[v]) {
        if (to.x != p[v] && to.x != heavy[v])decompose(to.x, to.x);
        if (to.x != p[v])update(1, 1, n, tin[to.x], to.y);
    }
}
int hld_get(int a, int b) {
    int res = 0;
    while (head[a] != head[b]) {
        if (d[head[a]] > d[head[b]])swap(a, b);
        res += get(1, 1, n, tin[head[b]], tin[b]), b = p[head[b]];
    }
    if (d[a] > d[b])swap(a, b);
    res += get(1, 1, n, tin[a] + 1, tin[b]);
    return res;
}
void solve() {
    cin >> n;
    for (int i = 1;i < n;i++) {
        int a, b, w;
        cin >> a >> b >> w;
        a++, b++;
        g[a].pb({b, w}), g[b].pb({a, w});
    }
    dfs(1), decompose(1, 1);
    cin >> q;
    vector <int> verts(5);
    for (int i = 1;i <= q;i++) {
        for (int j = 0;j < 5;j++)cin >> verts[j], verts[j]++;
        z.reset();
        int ans = 0;
        for (int x = 0;x < 5;x++) {
            for (int y = x + 1;y < 5;y++)ans += hld_get(verts[x], verts[y]);
        }
        cout << ans << '\n';
    }
}
signed main() {
    //srand(time(NULL));
    //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("cows.in", "r", stdin);
    //freopen("cows.out", "w", stdout);
    int test;
    test = 1;
    //cin >> test;
    for (int i = 1;i <= test;i++) {
        //cout << "Case " << i << ": ";
        solve();
    }
    return 0;
}

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