Submission #643052

#	Time	Username	Problem	Language	Result	Execution time	Memory
643052		azberjibiou	Road Closures (APIO21_roads)	C++17	0 / 100	2080 ms	1048576 KiB

roads

#include "roads.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pll pair<ll, ll>
using namespace std;
const int mxN=100010;
int N;
vector <pll> v[mxN], ch[mxN];
vector <ll> seg[mxN], d[mxN];
int sub[mxN];
int u[mxN], dd[mxN];
void dfs0(int now, int pre)
{
    sub[now]=1;
    for(auto [nxt, x] : v[now])   if(nxt!=pre)
    {
        dfs0(nxt, now);
        ch[now].emplace_back(nxt, x);
        sub[now]+=sub[nxt];
    }
    if(ch[now].empty())
    {
        u[now]=dd[now]=now;
        return;
    }
    sort(ch[now].begin(), ch[now].end(), [](pll a, pll b){return sub[a.fi]>sub[b.fi];});
    dd[now]=dd[ch[now][0].fi];
    u[dd[now]]=now;
}
void dfs1(int now)
{
    d[now].resize(ch[now].size()+1);
    seg[now].resize(sub[now]+1);
    if(ch[now].empty())
    {
        return;
    }
    for(auto [nxt, x] : ch[now])    dfs1(nxt);
    for(int i=1;i<=sub[now];i++)
    {
        for(auto [nxt, x] : v[now])
        {
            if(sub[nxt]<i)    seg[now][i]+=seg[nxt][sub[nxt]];
            else   seg[now][i]+=seg[nxt][i];
        }
    }
    ll nsum=0;
    for(auto [nxt, x] : ch[now])    nsum+=x;
    for(int i=ch[now].size()+1;i<=sub[now];i++) seg[now][i]+=nsum;
    for(int i=1;i<=ch[now].size();i++)
    {
        vector <ll> pq;
        for(auto [nxt, x] : ch[now])
        {
            if(ch[nxt].size()<i)   pq.push_back(x);
            else if(x-d[nxt][i]>0)   pq.push_back(x-d[nxt][i]);
        }
        sort(pq.begin(), pq.end(), [](ll a, ll b){return a>b;});
        if(i<=ch[now].size() && pq.size()>=i)    d[now][i]=pq[i-1];
        ll sum=0;
        for(int j=0;j<min((int)pq.size(), i);j++)    sum+=pq[j];
        seg[now][i]+=sum;
    }
}
vector<long long> minimum_closure_costs(int n, vector<int> U, vector<int> V, vector<int> W)
{
    N=n;
    for(int i=0;i<N-1;i++)
    {
        U[i]++;
        V[i]++;
        v[U[i]].emplace_back(V[i], W[i]);
        v[V[i]].emplace_back(U[i], W[i]);
    }
    dfs0(1, -1);
    //for(int i=1;i<=N;i++)   printf("u[%d]=%d\n", i, u[i]);
    dfs1(1);
    //for(int i=1;i<=N;i++)   for(int j=1;j<d[i].size();j++)  printf("d[%d][%d]=%lld\n", i, j, d[i][j]);
    vector <ll> ans;
    ans.resize(N);
    ll sum=0;
    for(int ele : W)    sum+=ele;
    ans[0]=sum;
    for(int i=1;i<N;i++)    ans[i]=sum-seg[1][i];
    return ans;
}

Compilation message (stderr)

roads.cpp: In function 'void dfs1(int)':
roads.cpp:52:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for(int i=1;i<=ch[now].size();i++)
      |                 ~^~~~~~~~~~~~~~~~
roads.cpp:57:30: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   57 |             if(ch[nxt].size()<i)   pq.push_back(x);
      |                ~~~~~~~~~~~~~~^~
roads.cpp:61:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         if(i<=ch[now].size() && pq.size()>=i)    d[now][i]=pq[i-1];
      |            ~^~~~~~~~~~~~~~~~
roads.cpp:61:42: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   61 |         if(i<=ch[now].size() && pq.size()>=i)    d[now][i]=pq[i-1];
      |                                 ~~~~~~~~~^~~

• Subtask 1: 0 / 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