Submission #1101198

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101198		PieArmy	Road Closures (APIO21_roads)	C++17	100 / 100	312 ms	76508 KiB

roads

typedef long long ll;
ll pie(ll army){return (1ll<<army);}
#include "roads.h"
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define endl '\n'
#define mid ((left+right)>>1)
const ll inf=200000000000000005;
const int sonsuz=2000000005;
using namespace std;
ll fpow(ll x,ll y,ll m=0){if(y<0){cout<<"powError";return -1;}if(m)x%=m;ll res=1;while(y>0){if(y&1)res*=x;x*=x;if(m){x%=m;res%=m;}y>>=1;}return res;}

struct Seg{
	int n;
	vector<ll>sum,arr;
	vector<int>cnt;
	void build(int node=1,int left=0,int right=-1){
		if(right==-1)right=n-1;
		if(left==right){
			sum[node]=arr[left];
			cnt[node]=!!arr[left];
			return;
		}
		build(node*2,left,mid);build(node*2+1,mid+1,right);
		sum[node]=sum[node*2]+sum[node*2+1];
		cnt[node]=cnt[node*2]+cnt[node*2+1];
	}
	void launch(){
		n=arr.size();
		sum.resize(n<<2);
		cnt.resize(n<<2);
		build();
	}
	int l,r;
	void up(int node=1,int left=0,int right=-1){
		if(right==-1)right=n-1;
		if(left==right){
			sum[node]=r;
			cnt[node]=!!r;
			return;
		}
		if(l>mid)up(node*2+1,mid+1,right);
		else up(node*2,left,mid);
		sum[node]=sum[node*2]+sum[node*2+1];
		cnt[node]=cnt[node*2]+cnt[node*2+1];
	}
	void update(int tar,int x){
		l=tar;r=x;
		up();
	}
	ll qu(int node=1,int left=0,int right=-1){
		if(right==-1)right=n-1;
		if(l==0)return 0;
		if(left==right){
			return sum[node];
		}
		if(cnt[node*2]>l)return qu(node*2,left,mid);
		l-=cnt[node*2];
		return sum[node*2]+qu(node*2+1,mid+1,right);
	}
	ll query(int x){
		l=x;
		if(l>cnt[1])return inf;
		return qu();
	}
};

int n;
int vis[100000];
ll dp[100000][2];
Seg seg[100000];
vector<pair<int,int>>adj[100000],act[100000];
map<int,int>ord[100000];
vector<int>deg[100000],awake;
vector<ll>ans;

void dfs(int pos,int par,int k){
	vis[pos]=k;
	ll sum=0;
	vector<ll>v;
	ll parcos=inf;
	for(pair<int,int>x:act[pos]){
		if(x.fr==par){
			parcos=x.sc;
			continue;
		}
		dfs(x.fr,pos,k);
		sum+=dp[x.fr][0];
		v.pb(dp[x.fr][1]-dp[x.fr][0]);
	}
	sort(v.begin(),v.end());
	dp[pos][1]=inf;
	dp[pos][0]=inf;
	dp[pos][1]=min(dp[pos][1],sum+seg[pos].query(max(0,int(adj[pos].size())-k-1))+parcos);
	dp[pos][0]=min(min(dp[pos][0],dp[pos][1]),sum+seg[pos].query(max(0,int(adj[pos].size())-k)));
	for(int i=0;i<v.size();i++){
		sum+=v[i];
		dp[pos][1]=min(dp[pos][1],sum+seg[pos].query(max(0,int(adj[pos].size())-i-k-2))+parcos);
		dp[pos][0]=min(min(dp[pos][0],dp[pos][1]),sum+seg[pos].query(max(0,int(adj[pos].size())-i-k-1)));
	}
}

void wake(int tar){
	awake.pb(tar);
	for(pair<int,int>x:adj[tar]){
		act[x.fr].pb({tar,x.sc});
		seg[x.fr].update(ord[x.fr][tar],0);
	}
}

vector<ll> minimum_closure_costs(int N,vector<int>U,vector<int>V,vector<int>W){
	n=N;
	ans.resize(n,0);
	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++){
		vis[i]=n;
		deg[adj[i].size()-1].pb(i);
		sort(adj[i].begin(),adj[i].end(),[&](const pair<int,int>&x,const pair<int,int>&y){return x.sc<y.sc;});
		for(int j=0;j<adj[i].size();j++){
			ord[i][adj[i][j].fr]=j;
			seg[i].arr.pb(adj[i][j].sc);
		}
		seg[i].launch();
	}
	for(int i=n-1;i>=0;i--){
		for(int x:deg[i]){
			wake(x);
		}
		for(int j:awake){
			if(vis[j]==i)continue;
			dfs(j,-1,i);
			ans[i]+=dp[j][0];
		}
	}
	return ans;
}

Compilation message (stderr)

roads.cpp: In function 'void dfs(int, int, int)':
roads.cpp:98:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |  for(int i=0;i<v.size();i++){
      |              ~^~~~~~~~~
roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:124:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |   for(int j=0;j<adj[i].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