Submission #718704

#	Time	Username	Problem	Language	Result	Execution time	Memory
718704		lam	Road Closures (APIO21_roads)	C++14	5 / 100	90 ms	9152 KiB

roads

#include "roads.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e5 + 10;
typedef pair<int,int> ii;
#define ff first
#define ss second
int n,k;
ll dp[2][maxn];
vector <ii> adj[maxn];
priority_queue<ll,vector<ll>,greater<ll>> pq;

void dfs(int x, int p)
{
    ll sum = 0LL;
    vector <ll> tmp;
    for (ii i:adj[x])
        if (i.ff!=p)
    {
        dfs(i.ff,x);
        sum += dp[0][i.ff];
        tmp.push_back(dp[1][i.ff]+i.ss-dp[0][i.ff]);
    }
    sort(tmp.begin(),tmp.end(),greater<ll>());
    vector <ll> tmp2 = tmp;
    dp[0][x] = sum;
    while (!tmp.empty()&&(tmp.size()>k||(tmp.back() < 0)))
    {
        dp[0][x] += tmp.back();
        tmp.pop_back();
    }
    dp[1][x] = sum;
    while (!tmp2.empty()&&(tmp2.size()>k+1||(tmp2.back()<0)))
    {
        dp[1][x] += tmp2.back();
        tmp2.pop_back();
    }
}

vector <ll> minimum_closure_costs(int N, vector <int>U, vector<int>V, vector<int>W)
{
    n=N;
    for (int i=0; i<n; i++) adj[i].clear();
    for (int i=0; i<n-1; i++)
    {
        int u=U[i]; int v=V[i];
        int w=W[i];
        pq.push(w);
    }
    vector <ll> ans;
    ll num = 0LL;
    for (int k=n-1; k>=0; k--)
    {
        while (pq.size() > k)
        {
            num+=pq.top(); pq.pop();
        }
            ans.push_back(num);
    }
    reverse(ans.begin(),ans.end());
    return ans;

}

Compilation message (stderr)

roads.cpp: In function 'void dfs(int, int)':
roads.cpp:28:37: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   28 |     while (!tmp.empty()&&(tmp.size()>k||(tmp.back() < 0)))
      |                           ~~~~~~~~~~^~
roads.cpp:34:39: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |     while (!tmp2.empty()&&(tmp2.size()>k+1||(tmp2.back()<0)))
      |                            ~~~~~~~~~~~^~~~
roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:47:13: warning: unused variable 'u' [-Wunused-variable]
   47 |         int u=U[i]; int v=V[i];
      |             ^
roads.cpp:47:25: warning: unused variable 'v' [-Wunused-variable]
   47 |         int u=U[i]; int v=V[i];
      |                         ^
roads.cpp:55:26: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   55 |         while (pq.size() > k)
      |                ~~~~~~~~~~^~~

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