Submission #1007376

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007376		AdamGS	Designated Cities (JOI19_designated_cities)	C++17	16 / 100	300 ms	42836 KiB

designated_cities

#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e5+7;
vector<pair<ll,ll>>V[LIM];
ll wynik[LIM], sum, dp[LIM], dp_up[LIM], oc[LIM];
void DFS(int x, int o) {
  for(auto i : V[x]) if(i.st==o) oc[x]=i.nd; else DFS(i.st, x);
  sum+=oc[x];
}
void DFS2(int x, int o) {
  for(auto i : V[x]) if(i.st!=o) {
    DFS2(i.st, x);
    dp[x]=max(dp[x], dp[i.st]+i.nd);
  }
}
void DFS3(int x, int o) {
  pair<ll,ll>ma={-1, -1};
  for(auto i : V[x]) if(i.st!=o) {
    ma=max(ma, {dp[i.st]+i.nd, i.st});
  }
  for(auto i : V[x]) if(i.st!=o) {
    dp_up[i.st]=max(dp_up[i.st], dp_up[x]+oc[i.st]);
    if(i.st!=ma.nd) {
      dp_up[i.st]=max(dp_up[i.st], ma.st+oc[i.st]);
    } else {
      for(auto j : V[x]) if(j.st!=o && j.st!=ma.nd) {
        dp_up[i.st]=max(dp_up[i.st], dp[j.st]+j.nd+oc[i.st]);
      }
    }
  }
  for(auto i : V[x]) if(i.st!=o) DFS3(i.st, x);
}
void DFS4(int x, int o) {
  for(auto i : V[x]) if(i.st==o) sum-=i.nd;
  wynik[1]=max(wynik[1], sum);
  wynik[2]=max(wynik[2], sum+max(dp[x], dp_up[x]));
  for(auto i : V[x]) if(i.st!=o) {
    sum+=i.nd;
    DFS4(i.st, x);
    sum-=i.nd;
  }
  for(auto i : V[x]) if(i.st==o) sum+=i.nd;
}
int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  int n;
  cin >> n;
  ll summ=0;
  rep(i, n-1) {
    ll a, b, c, d;
    cin >> a >> b >> c >> d; --a; --b;
    V[a].pb({b, c});
    V[b].pb({a, d});
    summ+=c+d;
  }
  DFS(0, 0);
  DFS2(0, 0);
  DFS3(0, 0);
  DFS4(0, 0);
  rep(i, n+1) wynik[i]=summ-wynik[i];
  int q;
  cin >> q;
  while(q--) {
    int x;
    cin >> x;
    cout << wynik[x] << '\n';
  }
}

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