Submission #1007378

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007378		AdamGS	Designated Cities (JOI19_designated_cities)	C++17	100 / 100	263 ms	68904 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];
pair<ll,ll>sred={-1, -1};
ll wynik[LIM], sum, dp[LIM], dp_up[LIM], oc[LIM], ile[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);
  sred=max(sred, {sum+max(dp[x], dp_up[x]), 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;
}
void DFS5(int x, int o) {
  ile[x]=1;
  for(auto i : V[x]) if(i.st!=o) {
    DFS5(i.st, x);
    ile[x]+=ile[i.st];
  }
  rep(i, V[x].size()) if(V[x][0].st==o || (V[x][i].st!=o && ile[V[x][i].st]>ile[V[x][0].st])) swap(V[x][0], V[x][i]);
}
void DFS6(int x, int o, multiset<ll>&S) {
  if(V[x][0].st==o) {
    S.insert(0);
    return;
  }
  DFS6(V[x][0].st, x, S);
  auto it=S.end(); --it;
  auto a=*it;
  S.erase(it);
  S.insert(a+V[x][0].nd);
  for(int i=1; i<V[x].size(); ++i) if(V[x][i].st!=o) {
    multiset<ll>tmp;
    DFS6(V[x][i].st, x, tmp);
    it=tmp.end(); --it;
    a=*it;
    tmp.erase(it);
    tmp.insert(a+V[x][i].nd);
    for(auto j : tmp) S.insert(j);
    tmp.clear();
  }
}
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);
  oc[sred.nd]=0;
  sum=0;
  DFS(sred.nd, sred.nd);
  DFS5(sred.nd, sred.nd);
  multiset<ll>A;
  DFS6(sred.nd, sred.nd, A);
  rep(i, n) {
    if(A.size()==0) break;
    auto it=A.end(); --it;
    auto a=*it;
    A.erase(it);
    sum+=a;
    wynik[i+2]=sum;
  }
  rep(i, n) wynik[i+1]=max(wynik[i+1], wynik[i]);
  rep(i, n+1) wynik[i]=summ-wynik[i];
  int q;
  cin >> q;
  while(q--) {
    int x;
    cin >> x;
    cout << wynik[x] << '\n';
  }
}

Compilation message (stderr)

designated_cities.cpp: In function 'void DFS5(int, int)':
designated_cities.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
designated_cities.cpp:58:3: note: in expansion of macro 'rep'
   58 |   rep(i, V[x].size()) if(V[x][0].st==o || (V[x][i].st!=o && ile[V[x][i].st]>ile[V[x][0].st])) swap(V[x][0], V[x][i]);
      |   ^~~
designated_cities.cpp: In function 'void DFS6(int, int, std::multiset<long long int>&)':
designated_cities.cpp:70:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |   for(int i=1; i<V[x].size(); ++i) if(V[x][i].st!=o) {
      |                ~^~~~~~~~~~~~

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