Submission #163920

#	Time	Username	Problem	Language	Result	Execution time	Memory
163920		combi1k1	Designated Cities (JOI19_designated_cities)	C++14	100 / 100	510 ms	51560 KiB

designated_cities

#include<bits/stdc++.h>

using namespace std;

#define X   first
#define Y   second
#define pb  emplace_back

#define int long long
#define ii  pair<int,int>
#define ed  tuple<int,int,int>

#define FOR(i,a,b)  for(int i = a ; i < b ; ++i)

const int   N   = 2e5 + 5;

priority_queue<int> pq;

vector<ed>  g[N];

int ans[N];
int Combi = 0;

bool Q;

ii  dfs(int u,int p)    {
    ii  res(0,u);

    for(ed  e : g[u])   if (get<0>(e) != p) {
        int x, y, z;
        tie(x, y, z) = e;
        ii  cur = dfs(x,u); cur.X += y;
        res = max(res,cur);

        if (Q)  Combi += z;
    }
    return  res;
}

int cal(int u,int p)    {
    int M = 0;
    for(ed  e : g[u])   if (get<0>(e) != p) {
        int x, y, z;
        tie(x, y, z) = e;
        ans[1] += z;
        int t = cal(x,u) + y;
        if (t <= M) pq.push(t);
        if (t >  M) pq.push(M), M = t;
    }
    return  M;
}
void sol(int u,int p)   {
    if (ans[1] < Combi)
        ans[1] = Combi;

    for(ed  e : g[u])   if (get<0>(e) != p) {
        int x, y, z;
        tie(x, y, z) = e;
        Combi += y - z; sol(x,u);
        Combi -= y - z;
    }
}

signed main()   {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;  cin >> n;
    int S = 0;

    FOR(i,1,n)  {
        int x, y;   cin >> x >> y;
        int c, d;   cin >> c >> d;
        g[x].pb(y,c,d);
        g[y].pb(x,d,c);
        S += c + d;
    }
    Q = 1;  int L = dfs(1,0).Y; //the optimal result for query e = 2 must have L as one of 2 resort cities
    Q = 0;  int R = dfs(L,0).Y; //now, the optimal result is (L,R)

    pq.push(cal(R,0));


    //we gradually add the furthest node from current skeleton tree
    //if there was only 1 chosen node, the next node is the farthest node in the outward direction
    //if there was at least 2 node chosen, the next node is the second farthest node in the outward direction in some

    FOR(i,2,n + 1)  {
        ans[i] = ans[i - 1] + pq.top();
        pq.pop();
    }

    sol(1,0);

    int q;  cin >> q;

    FOR(i,0,q)  {
        int x;  cin >> x;
        cout << S - ans[x] << "\n";
    }
}
/*
15
14 5 12 7
14 12 6 5
14 10 14 16
9 14 16 12
13 7 4 15
1 3 8 1
6 7 15 13
15 4 4 6
9 1 12 6
13 1 7 6
13 4 5 15
2 6 11 19
8 4 12 7
13 11 14 5
3
3
6
7
*/

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