제출 #765188

#제출 시각아이디문제언어결과실행 시간메모리
765188vjudge1Roadside Advertisements (NOI17_roadsideadverts)C++17
47 / 100
1068 ms9528 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]; ll pref[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 x, 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] = x; z[v] = x; return; } int tm = (tl + tr) >> 1; update(l, r, x, v * 2, tl, tm); update(l, r, x, v * 2 + 1, tm + 1, tr); t[v] = (t[v * 2] && t[v * 2 + 1]); } int get (int v = 1, int tl = 1, int tr = n) { push(v, tl, tr); if (t[v]) { return pref[tr] - pref[tl - 1]; } if (tl == tr) return 0; int tm = (tl + tr) >> 1; return get(v * 2, tl, tm) + get(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, 1); break; } if (d[x] >= d[y]) { int l = min(tin[u], tin[x]); int r = max(tin[u], tin[x]); t.update(l, r, 1); u = par[x]; } else { int l = min(tin[y], tin[v]); int r = max(tin[y], tin[v]); t.update(l, r, 1); 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 (); st[1] = 1; hld (); for (int i = 1; i < n; ++i) { if (uu[i] == par[vv[i]]) { pref[tin[vv[i]]] += ww[i]; } else { pref[tin[uu[i]]] += ww[i]; } } for (int i = 1; i <= n; ++i) { pref[i] += pref[i - 1]; } 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 = t.get(); cout << res << endl; } } 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!!!

컴파일 시 표준 에러 (stderr) 메시지

roadsideadverts.cpp: In function 'void dfs(int, int)':
roadsideadverts.cpp:40:25: warning: unused variable 'w' [-Wunused-variable]
   40 |         int to = it.ff, w = it.ss;
      |                         ^
roadsideadverts.cpp: In function 'void hld(int, int)':
roadsideadverts.cpp:61:25: warning: unused variable 'w' [-Wunused-variable]
   61 |         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...