제출 #896711

#제출 시각아이디문제언어결과실행 시간메모리
896711ShaShi경주 (Race) (IOI11_race)C++17
100 / 100
309 ms73044 KiB
#include "race.h" #include <bits/stdc++.h> // #define int long long #define F first #define S second #define all(x) x.begin(), x.end() #define kill(x) cout << x << endl, exit(0); #define mp make_pair #define pii pair<ll, ll> #define pb push_back using namespace std; typedef long long ll; const int MAXN = (int)1e6 + 7; const int MOD = 998244353; const int INF = (int)1e9 + 7; ll n, m, t, u, v, w, tmp, tmp2, tmp3, tmp4, ans, k; ll arr[MAXN], cost[MAXN], sz[MAXN]; pii love[MAXN]; bool hate[MAXN]; vector<pii> adj[MAXN]; void DFSsz(int v, int p=-1) { sz[v] = 1; for (auto cur:adj[v]) { int u = cur.F, w = cur.S; if (!hate[u] && u != p) { DFSsz(u, v); sz[v] += sz[u]; } } } int centroid(int tot, int v, int p=-1) { for (auto cur:adj[v]) { int u = cur.F, w = cur.S; if (u != p && !hate[u] && 2*sz[u] > tot) return centroid(tot, u, v); } return v; } void check_mol(int v, int cent, int p, pii dis, bool x) { if (dis.S > k) return; for (auto cur:adj[v]) { int u = cur.F, w = cur.S; if (u != p && !hate[u]) check_mol(u, cent, v, mp(dis.F+1, dis.S+w), x); } if (!x) { if (love[k-dis.S].F == cent) { ans = min(ans, dis.F+love[k-dis.S].S); } } else { if (love[dis.S].F != cent) { love[dis.S].F = cent; love[dis.S].S = dis.F; } else { love[dis.S].S = min(love[dis.S].S, dis.F); } } } void solve(int v) { DFSsz(v); int cent = centroid(sz[v], v); for (auto cur:adj[cent]) { int u = cur.F, w = cur.S; if (hate[u]) continue; check_mol(u, cent, cent, mp(1, w), 0); check_mol(u, cent, cent, mp(1, w), 1); } if (love[k].F == cent) ans = min(ans, love[k].S); hate[cent] = 1; for (auto cur:adj[cent]) if (!hate[cur.F]) solve(cur.F); } int best_path(int N, int K, int H[][2], int L[]) { n = N, k=K; for (int i=0; i<n-1; i++) { u = H[i][0]; v = H[i][1]; w = L[i]; u++, v++; adj[u].pb(mp(v, w)); adj[v].pb(mp(u, w)); } ans = INF; solve(1); if (ans == INF) return -1; return ans; }

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

race.cpp: In function 'void DFSsz(int, int)':
race.cpp:31:18: warning: unused variable 'w' [-Wunused-variable]
   31 |   int u = cur.F, w = cur.S;
      |                  ^
race.cpp: In function 'int centroid(int, int, int)':
race.cpp:43:18: warning: unused variable 'w' [-Wunused-variable]
   43 |   int u = cur.F, w = cur.S;
      |                  ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...