제출 #107401

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
107401		shoemakerjo	Designated Cities (JOI19_designated_cities)	C++14	7 / 100	451 ms	34808 KiB

designated_cities

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
const int maxn = 200010;
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pil pair<int, pll>
#define mp make_pair

int n, q;

ll seg[maxn*4]; //a max seg tree

//we want the seg-tree to go in euler tour order
int qus[maxn];
vector<pil> adj[maxn];

ll ans[maxn]; //store ans for each value
ll dep[maxn]; //distance from root to me
int par[maxn];
ll plink[maxn];

int rt; //some global root variable
ll esum = 0LL; //total edge sum
//barebones dfs
void dfs(int u, int p = -1) {
  if (p == -1) {
    dep[u] = 0LL;
    par[u] = -1;
  }
  for (pil vp : adj[u]) {
    if (vp.first == p) continue;
    dep[vp.first] = dep[u] + vp.second.first;
    par[vp.first] = u;
    plink[vp.first] = vp.second.second;
    dfs(vp.first, u);
  }
}

void dfs1(int u, ll msum = 0LL) {
  ans[1] = min(ans[1], esum - msum);
  for (pil vp : adj[u]) {
    if (vp.first != par[u]) {
      dfs1(vp.first, msum - vp.second.second +
        vp.second.first);
    }
  }
}

void go1() {
  //finds the answer for 1 by itself
  //when I go to a child, I reverse that edge
  //start with all going down
  ans[1] = esum;
  ll csum = 0LL;
  for (int i = 1; i <= n; i++) {
    if (i != rt) csum += plink[i];
  }
  dfs1(rt, csum);
}

pii go2() {
  return {-1, -1};
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n;
  int a, b;
  ll c, d;
  for (int i = 0; i < n-1; i++) {
    cin >> a >> b >> c >> d;
    adj[a].emplace_back(b, mp(c, d));
    adj[b].emplace_back(a, mp(d, c));
    esum += c;
    esum += d;
  }
  cin >> q;
  for (int i = 1; i <= q; i++) {
    cin >> qus[i];
  }
  if (n == 2) {
    //just bash
    for (int i = 1; i <= q; i++) {
      if (qus[i] == 2) {
        cout << 0 << endl;
      }
      else {
        cout << min(adj[1][0].second.first,
          adj[1][0].second.second);
      }
    }
    return 0;
  }

  //now we want to root at a non-leaf
  rt = 1;
  for (int i = 2; i <= n; i++) {
    if (adj[i].size() != 1) rt = i;
  }
  dfs(rt);

  go1();
  pii vp = go2();

  //now we are just printing out answer (for now - 1/2)
  for (int i = 1; i <= q; i++) {
    cout << ans[qus[i]] << '\n';
  }
  cout.flush();
}

//calculate the answer for one
//use a dp to calculate the answer for two (root at non-leaf)
//greedily add nodes until we get to each val (if none left - do nothing)

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

designated_cities.cpp: In function 'int main()':
designated_cities.cpp:107:7: warning: variable 'vp' set but not used [-Wunused-but-set-variable]
   pii vp = go2();
       ^~

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