Submission #765162

#TimeUsernameProblemLanguageResultExecution timeMemory
765162vjudge1Roadside Advertisements (NOI17_roadsideadverts)C++17
47 / 100
1062 ms9880 KiB
//Bismillahir-Rahmanir-Rahim # include <bits/stdc++.h> # define pb push_back # define ff first # define ss second # define nl "\n" # define sz(x) ((int)(x).size()) # define deb(x) cerr << #x << " = " << x << endl; # define pll pair <ll, ll> # define pii pair <int, int> typedef long long ll; typedef unsigned long long ull; typedef long double ld; const ll maxn = 5e4 + 2; const ll inf = 2e18 + 0; const ll mod = 1e9 + 7; const ll dx[] = {-1, 1, 0, 0}; const ll dy[] = {0, 0, -1, 1}; const ll P = 67; using namespace std; int n, q, timer; vector <pii> g[maxn]; int uu[maxn], vv[maxn], ww[maxn]; int tin[maxn], d[maxn]; int sz[maxn], mx[maxn]; int par[maxn], st[maxn]; void dfs (int v = 1, int pa = 1) { sz[v] = 1, mx[v] = -1; for (pii it : g[v]) { int to = it.ff, w = it.ss; if (to == pa) continue; dfs(to, v); sz[v] += sz[to]; if (mx[v] == -1 || sz[mx[v]] < sz[to]) mx[v] = to; } } void hld (int v = 1, int pa = 1) { tin[v] = ++timer; par[v] = pa; d[v] = d[pa] + 1; if (mx[v] != -1) { st[mx[v]] = st[v]; hld(mx[v], v); } for (pii it : g[v]) { int to = it.ff, w = it.ss; if (to == pa || to == mx[v]) continue; st[to] = to; hld(to, v); } } struct segtree { int t[maxn * 4], z[maxn * 4]; void build (int v = 1, int tl = 1, int tr = n) { t[v] = 0, z[v] = -1; if (tl == tr) { return; } int tm = (tl + tr) >> 1; build(v * 2, tl, tm); build(v * 2 + 1, tm + 1, tr); } void push (int v, int tl, int tr) { if (z[v] != -1 && tl != tr) { t[v * 2] = t[v * 2 + 1] = z[v]; z[v * 2] = z[v * 2 + 1] = z[v]; } } void update (int l, int r, int v = 1, int tl = 1, int tr = n) { push(v, tl, tr); if (tr < l || r < tl) return; if (l <= tl && tr <= r) { t[v] = 1; z[v] = 1; return; } int tm = (tl + tr) >> 1; update(l, r, v * 2, tl, tm); update(l, r, v * 2 + 1, tm + 1, tr); } int get (int pos, int v = 1, int tl = 1, int tr = n) { push(v, tl, tr); if (tl == tr) { return t[v]; } int tm = (tl + tr) >> 1; if (pos <= tm) { return get(pos, v * 2, tl, tm); } else { return get(pos, v * 2 + 1, tm + 1, tr); } } } t; int lca (int u, int v) { while (1) { int x = st[u], y = st[v]; if (x == y) { if (tin[u] < tin[v]) { return u; } else { return v; } } else if (d[x] >= d[y]) { u = par[x]; } else { v = par[y]; } } return -1; } void upd (int u, int v) { while (1) { int x = st[u], y = st[v]; if (x == y) { int l = min(tin[u], tin[v]); int r = max(tin[u], tin[v]); t.update(l + 1, r); break; } if (d[x] >= d[y]) { int l = min(tin[u], tin[x]); int r = max(tin[u], tin[x]); t.update(l, r); u = par[x]; } else { int l = min(tin[y], tin[v]); int r = max(tin[y], tin[v]); t.update(l, r); v = par[y]; } } } void ma1n (/* SABR */) { cin >> n; for (int i = 1; i < n; ++i) { cin >> uu[i] >> vv[i] >> ww[i]; uu[i]++, vv[i]++; g[uu[i]].pb({vv[i], ww[i]}); g[vv[i]].pb({uu[i], ww[i]}); } dfs (); hld (); cin >> q; while (q--) { vector <int> x(5); t.build(); for (int &a : x) { cin >> a; a++; } int lc = lca(x[0], x[1]); for (int i = 2; i < 5; ++i) { lc = lca(lc, x[i]); } for (int i = 0; i < 5; ++i) { upd(x[i], lc); } int res = 0; for (int i = 1; i < n; ++i) { if (uu[i] == par[vv[i]]) { if (t.get(tin[vv[i]])) { res += ww[i]; } } else { if (t.get(tin[uu[i]])) { res += ww[i]; } } } cout << res << nl; } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); // freopen("file.in", "r", stdin); // freopen("file.out", "w", stdout); int ttt = 1; // cin >> ttt; for (int test = 1; test <= ttt; ++test) { // cout << "Case " << test << ":" << '\n'; ma1n(); } return 0; } // 998batrr | BbIWEJI 3A TObOU!!! // tourist | BbIWEJI 3A TObOU!!!

Compilation message (stderr)

roadsideadverts.cpp: In function 'void dfs(int, int)':
roadsideadverts.cpp:39:25: warning: unused variable 'w' [-Wunused-variable]
   39 |         int to = it.ff, w = it.ss;
      |                         ^
roadsideadverts.cpp: In function 'void hld(int, int)':
roadsideadverts.cpp:60:25: warning: unused variable 'w' [-Wunused-variable]
   60 |         int to = it.ff, w = it.ss;
      |                         ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...