Submission #980949

#	Time	Username	Problem	Language	Result	Execution time	Memory
980949		8pete8	Road Closures (APIO21_roads)	C++17	100 / 100	263 ms	59076 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=1e18,minf=-1e18,Mxn=1e7,lg=20;
int dp[mxn+10][2];
vector<pii>adj[mxn+10];
int k;
int del[mxn+10],vis[mxn+10],cost[mxn+10],p[mxn+10],inval[mxn+10];
struct fen{
  vector<pii>fwk;
  vector<pii>neighbor;
  vector<int>on;
  void init(int x){
    for(auto i:adj[x])neighbor.pb({-i.s,i.f});
    neighbor.pb({minf,minf});
    sort(all(neighbor));
    fwk.assign(neighbor.size(),{0,0});
    on.assign(neighbor.size(),0);
  }
  void update(int pos){
    if(pos==0)assert(0);
    pii val={neighbor[pos].f,1};
    for(int i=pos;i<fwk.size();i+=(i&-i))fwk[i].f+=val.f,fwk[i].s+=val.s;
  }
  pii qry(int pos){
    pii sum={0,0};
    for(int i=pos;i>0;i-=(i&-i))sum.f+=fwk[i].f,sum.s+=fwk[i].s;
    return sum; 
  }
  void put(pii a){
    auto it=lb(all(neighbor),a);
    if(it==neighbor.end())assert(0);
    on[it-neighbor.begin()]=1;
    update(it-neighbor.begin());
  }
  pii get(int x,int mx){
    //get all val<x and the cnt<mx
    if(mx<0)return {0,0};
    //version 2.0 TT
    /*
    int l=1,r=neighbor.size()-1;
    
    while(l<=r){
      int mid=l+(r-l)/2;
      if(neighbor[mid].f>x)r=mid-1;
      else{
        pii a=qry(mid);
        if(a.s<=mx)ans=min(ans,a),l=mid+1;
        else r=mid-1;
      }
    }
    return ans;*/
    
    int pos=0,cnt=0,sum=0;
    for(int i=log2(neighbor.size())+1;i>=0;i--){
      if((pos+(1LL<<i))<neighbor.size()&&neighbor[pos+(1LL<<i)].f<x&&cnt+fwk[(pos+(1LL<<i))].s<=mx){
        pos+=(1LL<<i);
        cnt+=fwk[pos].s;
        sum+=fwk[pos].f;
      }
    }
    return {sum,cnt};
  }
}t[mxn+10];
int pref[mxn+10];
void solve(int cur,int p){
  if(del[cur])return;
  vis[cur]=1;
  int sum=inval[cur];//initial value (for the del children)
  vector<int>v;
  for(auto i:adj[cur]){
    if(i.f==p)continue;
    solve(i.f,cur);
    sum+=dp[i.f][1]+i.s;
    if(dp[i.f][0]-dp[i.f][1]-i.s<0)v.pb(dp[i.f][0]-dp[i.f][1]-i.s);//del all
  }
  dp[cur][0]=dp[cur][1]=sum;
  sort(all(v));//free sum
  v.pb(inf);
  for(int i=0;i<v.size();i++){
    pref[i]=v[i];
    if(i)pref[i]+=pref[i-1];
  }
  //bru idc anymore log factor going crazyyyyy
  int a=t[cur].get(inf,k-1).f,b=t[cur].get(inf,k).f;
  for(int i=0;i<v.size()-1;i++){
    if(i+1<=k-1)a=min(a,pref[i]+t[cur].get(v[i+1],k-1-i-1).f);
    if(i+1<=k)b=min(b,pref[i]+t[cur].get(v[i+1],k-i-1).f);//cout<<"L\n";
  }
  dp[cur][0]+=a;
  dp[cur][1]+=b;
  /*
  int l=0,r=v.size()-2,val=0;
  while(l<=r){
    int mid=l+(r-l)/2;
    pii a=t[cur].get(v[mid+1],(k-1)-mid-1);
    if(mid+1+a.s<=k-1)l=mid+1,val=min(val,a.f+pref[mid]);
    else r=mid-1;
  }
  dp[cur][0]+=min(val,t[cur].get(inf,k-1).f);
  l=0,r=v.size()-2,val=0;
  while(l<=r){
    int mid=l+(r-l)/2;
    pii a=t[cur].get(v[mid+1],(k)-mid-1);
    if(mid+1+a.s<=k)l=mid+1,val=min(val,a.f+pref[mid]);
    else r=mid-1;
  }
  dp[cur][1]+=min(val,t[cur].get(inf,k).f);*/
}
/*
we have to somehow get the sum of k min val
for the edge of node ->alive can be handle normally but edge from node ->del
need to be handle seperately
*/
bool cmp(pii a,pii b){
  if(adj[a.f].size()!=adj[b.f].size())return adj[a.f].size()>adj[b.f].size();
  return a.f>b.f;
}
vector<int> minimum_closure_costs(int32_t N,vector<int32_t>U,vector<int32_t>V,vector<int32_t>W) {
  vector<int>ans;
  for(int i=0;i<N-1;i++){
    adj[U[i]].pb({V[i],W[i]});
    adj[V[i]].pb({U[i],W[i]});
  }
  vector<pii>node;
  for(int i=0;i<N;i++)node.pb({adj[i].size(),i}),sort(all(adj[i]),cmp),t[i].init(i);
  sort(all(node));
  int cur=0;
  for(int i=0;i<N;i++){
    k=i;
    while(cur<node.size()&&node[cur].f<=i){
      int x=node[cur].s;
      for(auto j:adj[x]){
        if(adj[j.f].empty())assert(0);
        if(adj[j.f].back().f!=x)assert(0);
        adj[j.f].pop_back();
        inval[j.f]+=j.s;
        t[j.f].put({-j.s,x});
      }
      del[x]=1;
      cur++;
    }
    int sum=0;
    for(int j=cur;j<node.size();j++){
      if(!vis[node[j].s]){
        solve(node[j].s,-1);
        sum+=dp[node[j].s][1];
      }
      vis[node[j].s]=0;
    }
    ans.pb(sum);
  }
  return ans;
}
#undef int
/*
int32_t main(){
  fastio
  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];//u[i]--,v[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

the sum of cnt of node with deg>=x = sum of deg ('O')
so we can actually do dp on these node and skip the node with deg<=x as we dont actually need to do anything to them
we can actually delete the unnecessary node and deal with each component independently?
*/

Compilation message (stderr)

roads.cpp: In member function 'void fen::update(long long int)':
roads.cpp:64:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for(int i=pos;i<fwk.size();i+=(i&-i))fwk[i].f+=val.f,fwk[i].s+=val.s;
      |                   ~^~~~~~~~~~~
roads.cpp: In member function 'std::pair<long long int, long long int> fen::get(long long int, long long int)':
roads.cpp:97:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |       if((pos+(1LL<<i))<neighbor.size()&&neighbor[pos+(1LL<<i)].f<x&&cnt+fwk[(pos+(1LL<<i))].s<=mx){
      |          ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
roads.cpp: In function 'void solve(long long int, long long int)':
roads.cpp:121:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |   for(int i=0;i<v.size();i++){
      |               ~^~~~~~~~~
roads.cpp:127:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |   for(int i=0;i<v.size()-1;i++){
      |               ~^~~~~~~~~~~
roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int32_t, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:172:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  172 |     while(cur<node.size()&&node[cur].f<=i){
      |           ~~~^~~~~~~~~~~~
roads.cpp:185:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  185 |     for(int j=cur;j<node.size();j++){
      |                   ~^~~~~~~~~~~~

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