제출 #765321

#제출 시각아이디문제언어결과실행 시간메모리
765321vjudge1Roadside Advertisements (NOI17_roadsideadverts)C++17
100 / 100
44 ms11384 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> # define all(x) (x).begin(), (x).end() 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, d[maxn], timer; int tin[maxn], tout[maxn]; vector <pii> g[maxn]; int up[maxn][18]; void dfs (int v = 1, int pa = 1) { up[v][0] = pa; for (int j = 1; j <= 16; ++j) { up[v][j] = up[up[v][j - 1]][j - 1]; } tin[v] = ++timer; for (pii it : g[v]) { int to = it.ff, w = it.ss; if (to == pa) continue; d[to] = d[v] + w; dfs(to, v); } tout[v] = timer; } bool anc (int u, int v) { return tin[u] <= tin[v] && tout[v] <= tout[u]; } int lca (int u, int v) { if (anc(u, v)) return u; if (anc(v, u)) return v; for (int j = 16; j >= 0; --j) { if (!anc(up[u][j], v)) { u = up[u][j]; } } return up[u][0]; } int dist (int x, int y) { return d[x] + d[y] - 2 * d[lca(x, y)]; } void ma1n (/* SABR */) { cin >> n; for (int i = 1; i < n; ++i) { int u, v, w; cin >> u >> v >> w; u++, v++; g[u].pb({v, w}); g[v].pb({u, w}); } dfs (); cin >> q; while (q--) { vector <pair <int, int> > x(5); for (int i = 0; i < 5; ++i) { cin >> x[i].ss; x[i].ss++; x[i].ff = tin[x[i].ss]; } sort(all(x)); int ans = 0; for (int i = 0; i < 5; ++i) { int nxt = (i + 1) % 5; int lc = lca(x[i].ss, x[nxt].ss); ans += dist(x[i].ss, x[nxt].ss); } cout << ans / 2 << 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!!!

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

roadsideadverts.cpp: In function 'void ma1n()':
roadsideadverts.cpp:102:17: warning: unused variable 'lc' [-Wunused-variable]
  102 |             int lc = lca(x[i].ss, x[nxt].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...