Submission #979281

#	Time	Username	Problem	Language	Result	Execution time	Memory
979281		8pete8	Road Closures (APIO21_roads)	C++17	5 / 100	42 ms	8244 KiB

roads

#include "roads.h"
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include <cassert>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric> //gcd(a,b)
#include<bitset>
#include <cstdlib> 
#include <cstdint>
using namespace std;
#define ll long long
#define f first
//#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
//#define int long long
#define double long double
/*
*****
check if function has a return value?
*****
*/
const int mxn=1e5,inf=1e9,minf=-1e9,Mxn=1e7;
ll dp[mxn+10][2];
vector<pii>adj[mxn+10];
int k;
void solve(int cur,int p){
  ll sum=0;
  vector<ll>v;
  for(auto i:adj[cur]){
    if(i.f==p)continue;
    solve(i.f,cur);
    sum+=dp[i.f][1]+i.s;
    v.pb(dp[i.f][0]-dp[i.f][1]-i.s);//del all
  }
  dp[cur][0]=sum;
  sort(all(v));//free sum
  int cc=0;
  while(cc<v.size()&&cc<k-1&&v[cc]<0)dp[cur][0]+=v[cc],cc++;
  dp[cur][1]=dp[cur][0];
  if(k&&cc<v.size()&&v[cc]<0)dp[cur][1]+=v[cc];
  //cout<<cur<<" "<<dp[cur][0]<<" "<<dp[cur][1]<<"LL\n";
}
int pa[mxn+10];
int find(int u){return (pa[u]==u)?u:pa[u]=find(pa[u]);}
vector<ll> minimum_closure_costs(int N,vector<int>U,vector<int>V,vector<int>W) {
  bool sub1=1,sub2=1;
  vector<ll>ans;
  for(auto i:U)sub1&=(i==0);
  for(int i=0;i<N-1;i++)sub2&=(U[i]==i&&V[i]==i+1),pa[i]=i;
  if(sub1){
    ll sum=0;
    sort(all(W));
    for(auto i:W)sum+=i;
    ans.pb(sum);
    for(int i=0;i<N-1;i++)sum-=W.back(),W.pop_back(),ans.pb(sum);
    return ans;
  }
  else if(sub2){
    for(int i=0;i<min(N,2);i++)k=i,solve(0,-1),ans.pb(dp[0][1]);
    while(ans.size()<N)ans.pb(0);
    return ans;
  }
  else if(N<2000){
    for(int i=0;i<N-1;i++){
      adj[U[i]].pb({V[i],W[i]});
      adj[V[i]].pb({U[i],W[i]});
    }
    for(int i=0;i<N;i++){
      k=i,solve(0,-1);
      ans.pb(dp[0][1]);
    }
    return ans;
  }//sub5 dsu??
  return ans;
}/*
int32_t main(){
  int n;cin>>n;
  vector<int>u(n-1),v(n-1),w(n-1);
  for(int i=0;i<n-1;i++)cin>>u[i]>>v[i]>>w[i];
  vector<ll>ans=minimum_closure_costs(n,u,v,w);
  for(auto i:ans)cout<<i<<" ";
  cout<<'\n';
}*/
/*
n^2 solution = do dp
dp[0],dp[1]; 0= didnt take par road,1= take par road
we can have atmost k dp[0];
we can sort dp[1]+road-dp[0] cost of all children
then greedy take
*/

Compilation message (stderr)

roads.cpp: In function 'void solve(int, int)':
roads.cpp:61:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |   while(cc<v.size()&&cc<k-1&&v[cc]<0)dp[cur][0]+=v[cc],cc++;
      |         ~~^~~~~~~~~
roads.cpp:63:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   if(k&&cc<v.size()&&v[cc]<0)dp[cur][1]+=v[cc];
      |         ~~^~~~~~~~~
roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:83:21: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   83 |     while(ans.size()<N)ans.pb(0);
      |           ~~~~~~~~~~^~

• 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