Submission #969474

#	Time	Username	Problem	Language	Result	Execution time	Memory
969474		LucaIlie	Designated Cities (JOI19_designated_cities)	C++17	0 / 100	2078 ms	26904 KiB

designated_cities

#include <bits/stdc++.h>

using namespace std;

struct edge {
    int u, v, a, b;

    int other( int w ) {
        return u ^ v ^ w;
    }

    int cost( int w ) {
        return (w == v ? a : b);
    }
};

const int MAX_N = 2e5;
int parent[MAX_N + 1], parentEdge[MAX_N + 1], countLeafs[MAX_N + 1];
long long ans[MAX_N + 1];
edge edges[MAX_N];
vector<int> adj[MAX_N + 1];
vector<int> leafs;

long long sumR = 0, difR[MAX_N + 1];
void dfs( int u, int p ) {
    parent[u] = p;
    for ( int e: adj[u] ) {
        int v = edges[e].other( u );
        int up = edges[e].cost( u ), down = edges[e].cost( v );
        if ( v == p )
            continue;
        sumR += down;
        difR[v] = difR[u] + up - down;
        parentEdge[v] = e;
        dfs( v, u );
        countLeafs[u] += countLeafs[v];
    }
    if ( adj[u].size() == 1 ) {
        leafs.push_back( u );
        countLeafs[u] = 1;
    }
}

int main() {
    int n;
    long long sumTot = 0;

    cin >> n;
    for ( int i = 1; i <= n - 1; i++ ) {
        cin >> edges[i].u >> edges[i].v >> edges[i].a >> edges[i].b;
        adj[edges[i].u].push_back( i );
        adj[edges[i].v].push_back( i );
        sumTot += edges[i].a + edges[i].b;
    }
    
    int r = 1;
    if ( n != 2 ) {
        while ( adj[r].size() == 1 )
            r++;
    }

    dfs( r, 0 );

    ans[1] = sumR;
    for ( int v = 1; v <= n; v++ )
        ans[1] = min( ans[1], sumR + difR[v] );

    for ( int pas = leafs.size() - 1; pas >= 2; pas-- ) {
        int d = 0;
        long long minCost = 1e15;
        for ( int v: leafs ) {
            if ( countLeafs[v] == 0 )
                continue;

            int u = v;
            long long cost = 0;
            while ( countLeafs[u] == 1 ) {
                cost += edges[parentEdge[u]].cost( u );
                u = parent[u];
            }
            if ( cost < minCost ) {
                minCost = cost;
                d = v;
            }
        }
        ans[pas] = ans[pas + 1] + minCost;
        int u = d;
        while ( u != 0 ) {
            countLeafs[u]--;
            u = parent[u];
        }
    }

    int q;
    cin >> q;
    while ( q-- ) {
        int k;
        cin >> k;
        cout << ans[k] << "\n";
    }

    return 0;
}

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