oj.uz

답안 #969492

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
969492 2024-04-25T08:34:20 Z LucaIlie Designated Cities (JOI19_designated_cities) C++17
7 / 100
 338 ms 38632 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 = 2; 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Incorrect 2 ms 12636 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 338 ms 28172 KB Output is correct
3 Correct 307 ms 37972 KB Output is correct
4 Correct 240 ms 27448 KB Output is correct
5 Correct 266 ms 27532 KB Output is correct
6 Correct 265 ms 29376 KB Output is correct
7 Correct 266 ms 27936 KB Output is correct
8 Correct 290 ms 38632 KB Output is correct
9 Correct 264 ms 29880 KB Output is correct

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Incorrect 290 ms 27592 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Incorrect 2 ms 12636 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 338 ms 28172 KB Output is correct
3 Correct 307 ms 37972 KB Output is correct
4 Correct 240 ms 27448 KB Output is correct
5 Correct 266 ms 27532 KB Output is correct
6 Correct 265 ms 29376 KB Output is correct
7 Correct 266 ms 27936 KB Output is correct
8 Correct 290 ms 38632 KB Output is correct
9 Correct 264 ms 29880 KB Output is correct
10 Correct 2 ms 12636 KB Output is correct
11 Incorrect 290 ms 27592 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Incorrect 2 ms 12636 KB Output isn't correct
3 Halted 0 ms 0 KB -