Submission #376171

#TimeUsernameProblemLanguageResultExecution timeMemory
376171casperwangDesignated Cities (JOI19_designated_cities)C++14
33 / 100
1229 ms105060 KiB
#include <bits/stdc++.h> #define int long long #define pb emplace_back #define pii pair<int,int> #define ff first #define ss second using namespace std; #define debug(args...) kout("[ " + string(#args) + " ]", args) void kout() { cerr << endl; } template <class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ',kout(b...); } template <class T> void pary(T L, T R) { while (L != R) cerr << *L << " \n"[++L==R]; } struct Edge { int to, val; Edge(int t, int v) { to = t, val = v; } }; const int MAXN = 200000; const int INF = 1e18; int N, Q; int a, b, c, d; vector <int> path[MAXN+1]; vector <Edge> E; pii dfs[MAXN+1]; int ord[MAXN*2+1]; int cnt; int dis[MAXN+1]; bool vis[MAXN+1]; int cal; int ans[MAXN+1]; class Seg { private: pii arr[MAXN*8+5]; int tag[MAXN*8+5]; void pull(int now) { arr[now] = max(arr[now*2], arr[now*2+1]); } void push(int now, int len) { if (!tag[now]) return; arr[now].ff += tag[now]; if (len > 1) { tag[now*2 ] += tag[now]; tag[now*2+1] += tag[now]; } tag[now] = 0; } public: void build(int now=1, int l=1, int r=2*N) { tag[now] = 0; if (l == r) { arr[now] = pii(dis[ord[l]], ord[l]); return; } int mid = l + r >> 1; build(now*2 , l, mid); build(now*2+1,mid+1,r); pull(now); } void mdy(int ml, int mr, int k, int now=1, int l=1, int r=2*N) { push(now, r-l+1); if (ml <= l && r <= mr) { tag[now] += k; push(now, r-l+1); return; } else if (l > mr || r < ml) return; int mid = l + r >> 1; mdy(ml, mr, k, now*2 , l, mid); mdy(ml, mr, k, now*2+1,mid+1,r); pull(now); } pii qry() { return arr[1]; } } seg; void dfs_init(int now, int par) { dfs[now].ff = ++cnt; ord[cnt] = now; for (int id : path[now]) { Edge e = E[id]; if (e.to == par) continue; dis[e.to] = dis[now] + e.val; cal += e.val; dfs_init(e.to, now); } dfs[now].ss = ++cnt; ord[cnt] = now; } void dfs_1(int now, int par) { ans[1] = min(ans[1], cal); for (int id : path[now]) { Edge e = E[id], re = E[id^1]; if (e.to == par) continue; cal += re.val - e.val; dfs_1(e.to, now); cal -= re.val - e.val; } } void dfs_2(int now, int par) { if (cal - seg.qry().ff < ans[2]) { ans[2] = cal - seg.qry().ff; a = now, b = seg.qry().ss; } for (int id : path[now]) { Edge e = E[id], re = E[id^1]; if (e.to == par) continue; cal += re.val - e.val; seg.mdy(dfs[e.to].ff, dfs[e.to].ss, -e.val); seg.mdy(1, dfs[e.to].ff, re.val); seg.mdy(dfs[e.to].ss, 2*N, re.val); dfs_2(e.to, now); cal -= re.val - e.val; seg.mdy(dfs[e.to].ff, dfs[e.to].ss, e.val); seg.mdy(1, dfs[e.to].ff, -re.val); seg.mdy(dfs[e.to].ss, 2*N, -re.val); } } vector<int> line(int s, int t) { queue <int> nxt; vector <int> par(N+1); nxt.push(s); par[s] = s; while (nxt.size()) { int now = nxt.front(); nxt.pop(); for (int id : path[now]) { Edge e = E[id]; if (!par[e.to]) { par[e.to] = now; nxt.push(e.to); } } } vector <int> res; while (par[t] != t) { res.pb(t); t = par[t]; } res.pb(s); return res; } void dfs_dis(int now, int par) { dfs[now].ff = ++cnt; ord[cnt] = now; for (int id : path[now]) { Edge e = E[id]; if (e.to == par || vis[e.to]) continue; dis[e.to] = dis[now] + e.val; dfs_dis(e.to, now); } dfs[now].ss = ++cnt; ord[cnt] = now; } void solve() { cal = 0; dfs_init(1, 0); dfs_1(1, 0); seg.build(); dfs_2(1, 0); vector <int> v = line(a, b); for (int i : v) vis[i] = true, dis[i] = 0; cnt = 0; for (int i : v) dfs_dis(i, 0); seg.build(); for (int i = 3; i <= N; i++) { ans[i] = ans[i-1] - seg.qry().ff; int nid = seg.qry().ss; if (vis[nid]) break; while (true) { int nxt = -1, c = 0; for (int id : path[nid]) { Edge e = E[id], re = E[id^1]; if (dis[e.to] + re.val == dis[nid]) nxt = e.to, c = re.val; } seg.mdy(dfs[nid].ff, dfs[nid].ss, -c); vis[nid] = true; if (nxt == -1 || vis[nxt]) break; nid = nxt; } } } signed main() { ios_base::sync_with_stdio(0), cin.tie(0); cin >> N; for (int i = 1; i < N; i++) { cin >> a >> b >> c >> d; path[a].pb(E.size()); E.pb(b, c); path[b].pb(E.size()); E.pb(a, d); ans[i] = INF; } solve(); cin >> Q; for (int i = 1; i <= Q; i++) { cin >> a; cout << ans[a] << '\n'; } }

Compilation message (stderr)

designated_cities.cpp: In member function 'void Seg::build(long long int, long long int, long long int)':
designated_cities.cpp:57:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |    int mid = l + r >> 1;
      |              ~~^~~
designated_cities.cpp: In member function 'void Seg::mdy(long long int, long long int, long long int, long long int, long long int, long long int)':
designated_cities.cpp:69:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |    int mid = l + r >> 1;
      |              ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...