제출 #1242239

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1242239		minhpk	Designated Cities (JOI19_designated_cities)	C++20	100 / 100	188 ms	76704 KiB

designated_cities

#include <bits/stdc++.h>
#define int long long
using namespace std;
struct node{
     int x,w1,w2;
};
vector <node> z[1000005];
int child[1000005];
array<int,3> dp2[1000005];
array<int,2> dp1[1000005];
int high[1000005];
void dfs(int i,int par){
    for (auto p:z[i]){
         if (p.x==par){
            continue;
         }
         high[p.x]=high[i]+p.w1;
         dfs(p.x,i);
         child[i]+=child[p.x];
         child[i]+=p.w2;
    }
    dp1[i]={child[i],i};
    dp2[i]={0,i,i};
    for (auto p:z[i]){
         if (p.x==par){
             continue;
         }
         int w1=p.w1;
         int w2=p.w2;
         dp2[i]=max(dp2[i],{dp2[p.x][0]+w1+child[i]-child[p.x]-w2,dp2[p.x][1],dp2[p.x][2]});
         dp2[i]=max(dp2[i],{dp1[p.x][0]+dp1[i][0]+w1-child[p.x],dp1[i][1],dp1[p.x][1]});
         dp2[i]=max(dp2[i],{dp1[p.x][0]+w1+child[i]-child[p.x],i,dp1[p.x][1]});



         dp1[i]=max(dp1[i],{dp1[p.x][0]+w1+child[i]-child[p.x],dp1[p.x][1]});

    }
   // cerr << i << "\n";
}
int sum=0;
int res[1000005];
void dfs1(int i,int par,int cur){
    res[1]=max(res[1],cur);
    for (auto [p,w1,w2]:z[i]){
         if (p==par){
             continue;
         }
         dfs1(p,i,cur+w1-w2);
    }
   // cerr << i << "\n";
}
priority_queue<int> q;
int inf=1e16;
int dfs2(int i,int par){
   // cerr << i << " " << par << "\n";
    if (i==dp2[1][2]){
       // cerr  << "ok" << "\n";
        return inf;
    }
    vector <int> cand;
  //  cerr << "ok" << "\n";
    for (auto [p,w1,w2]:z[i]){
         if (p==par){
            continue;
         }
         cand.push_back(dfs2(p,i)+w1);
         //cerr << p << " " << i << "\n";
    }
    if (cand.size()){
        sort(cand.begin(),cand.end());
        for (int  t=0;t<cand.size();t++){
          if (t==cand.size()-1){
              q.push(0LL);
          }else{
              q.push(cand[t]);
          }
        }
    }
  //  cerr << i << "\n";
    if (cand.empty()){
        return 0LL;
    }
    return cand[cand.size()-1];
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int a;
    cin >> a;
    for (int i=1;i<a;i++){
          int x,y,w1,w2;
          cin >> x >> y >> w1 >> w2;
          z[x].push_back({y,w1,w2});
          z[y].push_back({x,w2,w1});
          sum+=w1+w2;
    }
    dfs(1,1);
    dfs1(1,1,child[1]);
   // cerr << dp2[1][1] << " " << dp2[1][2]  << "\n";
    dfs2(dp2[1][1],0);
    res[1]=sum-res[1];
    res[2]=sum-dp2[1][0];
    for (int i=3;i<=a;i++){
         res[i]=res[i-1]-q.top();
         q.pop();
    }
    int c;
    cin >> c;
    while (c--){
         int x;
         cin >> x;
         cout << res[x] << "\n";
    }
    return 0;
}

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