Submission #447235

#	Time	Username	Problem	Language	Result	Execution time	Memory
447235		blue	도로 폐쇄 (APIO21_roads)	C++17	14 / 100	31 ms	6300 KiB

roads

#include "roads.h"
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

const int maxN = 200;

int N;
vector<int> edge[maxN];
vector<long long> wt[maxN];

vector<int> P(maxN, -1);
vector<long long> P_wt(maxN, 0);

void dfs(int u)
{
    for(int e = 0; e < edge[u].size(); e++)
    {
        int v = edge[u][e];
        long long w = wt[u][e];

        if(P[u] == v) continue;

        P[v] = u;
        P_wt[v] = w;
        dfs(v);
    }
}


int K;
long long dp1[maxN];
long long dp2[maxN];

void dfs2(int u)
{
    // cerr << "\n";
    // cerr << "dfs2 " << u << '\n';
    dp1[u] = 0;
    dp2[u] = 0;

    vector<long long> adj;

    if(edge[u].size() == 1 && u != 0)
    {
        dp1[u] = dp2[u] = 0;
        return;
    }

    for(int v: edge[u])
    {
        if(P[u] == v) continue;

        dfs2(v);

        dp1[u] += dp2[v];
        dp2[u] += dp2[v];

        adj.push_back(P_wt[v] + dp1[v] - dp2[v]);
    }

    sort(adj.begin(), adj.end());

    // cerr << "u = " << u << '\n';
    // cerr << "adj = ";
    // for(long long a: adj) cerr << a << ' ';
    // cerr << '\n';

    int x1 = max(int(adj.size() - K), 0);

    // cerr << "dp1 " << u << " = " << dp1[u] << ", dp2 " << u << " = " << dp2[u] << '\n';


    for(int i = 0; i < x1; i++)
        dp1[u] += adj[i];
    for(int i = x1; i < adj.size(); i++)
        dp1[u] += min(0LL, adj[i]);



    int x2 = max(int(adj.size() - (K-1)), 0);

    for(int i = 0; i < x2; i++)
        dp2[u] += adj[i];
    for(int i = x2; i < adj.size(); i++)
        dp2[u] += min(0LL, adj[i]);

    // cerr << "dp1 " << u << " = " << dp1[u] << ", dp2 " << u << " = " << dp2[u] << '\n';
}

vector<long long> minimum_closure_costs(int n1, vector<int> u1, vector<int> v1, vector<int> c1)
{
    long long total_weight = 0;
    N = n1;
    for(int j = 0; j < N-1; j++)
    {
        edge[ u1[j] ].push_back( v1[j] );
        wt[ u1[j] ].push_back( c1[j] );

        edge[ v1[j] ].push_back( u1[j] );
        wt[ v1[j] ].push_back( c1[j] );

        total_weight += c1[j];
    }

    dfs(0);

    vector<long long> res(N);

    res[0] = total_weight;

    for(K = 1; K <= N-1; K++)
    {
        // cerr << "\n\n\n\n";
        // cerr << "K = " << K << '\n';
        dfs2(0);
        res[K] = min(dp1[0], dp2[0]);
    }

    return res;
}

Compilation message (stderr)

roads.cpp: In function 'void dfs(int)':
roads.cpp:18:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for(int e = 0; e < edge[u].size(); e++)
      |                    ~~^~~~~~~~~~~~~~~~
roads.cpp: In function 'void dfs2(int)':
roads.cpp:77:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for(int i = x1; i < adj.size(); i++)
      |                     ~~^~~~~~~~~~~~
roads.cpp:86:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for(int i = x2; i < adj.size(); i++)
      |                     ~~^~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 14 / 14
• Subtask 4: 0 / 10
• Subtask 5: 0 / 17
• Subtask 6: 0 / 25
• Subtask 7: 0 / 22