Submission #630406

#	Time	Username	Problem	Language	Result	Execution time	Memory
630406		cadmiumsky	Designated Cities (JOI19_designated_cities)	C++14	100 / 100	958 ms	51216 KiB

designated_cities

#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;

#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

const int nmax = 2e5 + 5, inf = 1e15 + 5;

vector<tii> g[nmax];

int height[nmax], atrleaf[nmax], troot[nmax];
int wroot;

void initdfs(int node, int f) {
  atrleaf[node] = node;
  for(auto [x, c, alt] : g[node]) {
    if(x == f) continue;
    troot[x] = troot[node] - c + alt;
    wroot += c;
    initdfs(x, node);
    tie(height[node], atrleaf[node]) = max(make_pair(height[x] + c, atrleaf[x]), make_pair(height[node], atrleaf[node]));
  }
  return;
}

int mxl, mxr, mxcost = inf; 
void diamdfs(int node, int f) {
  int ends[2] = {node, node}, cost[2] = {0, 0};
  for(auto [x, c, alt] : g[node]) {
    if(x == f) continue;
    diamdfs(x, node);
    alt = height[x] + c;
    if(alt >= cost[0])
      tie(ends[1], cost[1]) = pii{ends[0], cost[0]},
      tie(ends[0], cost[0]) = pii{atrleaf[x], alt};
    else if(alt > cost[1])
      tie(ends[1], cost[1]) = pii{atrleaf[x], alt};
  }
  if(wroot - (cost[0] + cost[1]) + troot[node] < mxcost)
    tie(mxl, mxr, mxcost) = tii{ends[0], ends[1], wroot - (cost[0] + cost[1]) + troot[node]};
}

void reinitdfs(int node, int f) {
  atrleaf[node] = node;
  for(auto [x, c, alt] : g[node]) {
    if(x == f) continue;
    troot[x] = troot[node] + c;
    wroot += c;
    reinitdfs(x, node);
    if(troot[atrleaf[node]] < troot[atrleaf[x]])
      atrleaf[node] = atrleaf[x];
  }
  return;
}

priority_queue<int> pq;
void initpqdfs(int node, int f, int offset = 0) {
  if(g[node].size() == 1 && node != f) {
    pq.push(troot[node] - offset);
    return;
  }
  for(auto [x, c, cost] : g[node]) {
    if(x == f) continue;
    if(atrleaf[node] != atrleaf[x])
      initpqdfs(x, node, troot[node]);
    else
      initpqdfs(x, node, offset);
  }
  return;
}

int rez[nmax];

signed main() {
  int n;
  cin >> n;
  for(int i = 0, x, y, a, b; i < n - 1; i++) {
    cin >> x >> y >> a >> b;
    g[x].emplace_back(y, a, b); 
    g[y].emplace_back(x, b, a); 
  }
  int root = 1;
  initdfs(root, root);
  rez[1] = inf;
  for(int i = 1; i <= n; i++)
    rez[1] = min(rez[1], wroot + troot[i]);
  
  
  diamdfs(root, root);
  troot[root = mxl] = 0;;
  rez[2] = mxcost;
  wroot = 0;
  reinitdfs(root, root);
  initpqdfs(root, root);
  
  int ptr = 1;
  
  while(!pq.empty()) {
    wroot -= pq.top();
    rez[++ptr] = wroot;
    pq.pop();
  }
  ++ptr;
  while(ptr <= n)
    rez[ptr] = rez[ptr - 1],
    ptr++;
  
  int q;
  cin >> q;
  for(int i = 0, x; i < q; i++) {
    cin >> x;
    cout << rez[x] << '\n';
  }
}

/**
  De-atâtea nopți aud plouând,
  Aud materia plângând..
  Sînt singur, și mă duce un gând
  Spre locuințele lacustre.

  Și parcă dorm pe scânduri ude,
  În spate mă izbește-un val --
  Tresar prin somn și mi se pare
  Că n-am tras podul de la mal.

  Un gol istoric se întinde,
  Pe-același vremuri mă găsesc..
  Și simt cum de atâta ploaie
  Pilonii grei se prăbușesc.

  De-atâtea nopți aud plouând,
  Tot tresărind, tot așteptând..
  Sînt singur, și mă duce-un gând
  Spre locuințele lacustre.
-- George Bacovia, Lacustră
*/

Compilation message (stderr)

designated_cities.cpp: In function 'void initdfs(ll, ll)':
designated_cities.cpp:22:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   22 |   for(auto [x, c, alt] : g[node]) {
      |            ^
designated_cities.cpp: In function 'void diamdfs(ll, ll)':
designated_cities.cpp:35:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   35 |   for(auto [x, c, alt] : g[node]) {
      |            ^
designated_cities.cpp: In function 'void reinitdfs(ll, ll)':
designated_cities.cpp:51:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   51 |   for(auto [x, c, alt] : g[node]) {
      |            ^
designated_cities.cpp: In function 'void initpqdfs(ll, ll, ll)':
designated_cities.cpp:68:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   68 |   for(auto [x, c, cost] : g[node]) {
      |            ^

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 17 / 17
• Subtask 5: 17 / 17
• Subtask 6: 44 / 44