oj.uz

Submission #969479

# Submission time Handle Problem Language Result Execution time Memory
969479 2024-04-25T08:28:59 Z LucaIlie Designated Cities (JOI19_designated_cities) C++17
0 / 100
 2000 ms 33944 KB 
#include <bits/stdc++.h>
#define int long long
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;
    }
}

signed 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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 12632 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 3 ms 12636 KB Output is correct
6 Incorrect 2 ms 12636 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12644 KB Output is correct
2 Execution timed out 2062 ms 33944 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12640 KB Output is correct
2 Execution timed out 2045 ms 33928 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 12632 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 3 ms 12636 KB Output is correct
6 Incorrect 2 ms 12636 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12644 KB Output is correct
2 Execution timed out 2062 ms 33944 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 12632 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 3 ms 12636 KB Output is correct
6 Incorrect 2 ms 12636 KB Output isn't correct
7 Halted 0 ms 0 KB -