Submission #1311681

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311681		thelegendary08	Road Closures (APIO21_roads)	C++20	31 / 100	2098 ms	65584 KiB

roads

#include "roads.h"
#include<bits/stdc++.h>
#define int long long
#define mp make_pair
#define eb emplace_back
#define pb push_back
#define f0r(i,n) for(int i = 0; i < n; i++)
#define FOR(i,k,n) for(int i = k; i < n; i++)
#define vi vector<int>
#define vvi vector<vi>
#define dout(x) cout<<x<<' '<<#x<<endl;
#define dout2(x,y) cout<<x<<' '<<#x<<' '<<y<<' '<<#y<<endl;
#define vout(v) for(auto u : v)cout<<u<<' '; cout<<endl;
using namespace std;
const int mxn = 1e5 + 5; 
struct Edge{
	int u,v,w;
};
set<pair<int,int>>adj[mxn]; vector<pair<int,int>>G[mxn]; 
int n, k; int dp[mxn][2]; multiset<int, greater<int>>dif[mxn]; bool vis[mxn]; set<int>imp; 
void dfs(int node, int from){
	vis[node]=1; int sum = 0;
	for(auto [u,w] : adj[node])if(u!=from)dfs(u,node), sum+=max(dp[u][0],dp[u][1]), dif[node].insert(dp[u][0]+w-max(dp[u][0],dp[u][1])); 
	dp[node][1]=sum; int cnt = 0; for(auto u : dif[node]){
		if(cnt==k)break; dp[node][1]+=u; cnt++; 
	}
	
	dp[node][0]=sum; cnt = 0; for(auto u : dif[node]){
		if(cnt>=k-1)break; if(u<0)break; dp[node][0]+=u; cnt++; 
	}
	for(auto [u,w] : adj[node])if(u!=from)dif[node].erase(dif[node].find(dp[u][0]+w-max(dp[u][0],dp[u][1]))); 
}
std::vector<long long> minimum_closure_costs(signed N, std::vector<signed> U,
                                             std::vector<signed> V,
                                             std::vector<signed> W) {
	n=N; vi ans; int S = 0; vi deg(n); vector<Edge>edges;
	f0r(i,n-1)edges.pb({U[i],V[i],W[i]}),adj[U[i]].insert(mp(V[i],W[i])),adj[V[i]].insert(mp(U[i],W[i])),G[U[i]].eb(V[i],W[i]),G[V[i]].eb(U[i],W[i]),S+=W[i],deg[U[i]]++,deg[V[i]]++; 
	vvi w(n); f0r(i,n)w[deg[i]].pb(i); f0r(i,n)imp.insert(i); int per = 0; vi plus(n); vector<vector<Edge>>minus(n); for(auto [u,v,w] : edges){
		plus[max(deg[u],deg[v])]+=w; minus[min(deg[u],deg[v])].pb({u,v,w});
	} 
	f0r(K,n){
		k=K; per+=plus[k]; vi tmp; for(auto u : w[k]){
			imp.erase(u); //tmp.pb(u);  
		}
		for(auto [u,v,w] : minus[k]){
			if(deg[u] < deg[v])dif[v].insert(w); if(deg[v] < deg[u])dif[u].insert(w);
			adj[u].erase(mp(v,w)), adj[v].erase(mp(u,w));
		}
		// vector<pair<pair<int,int>,int>>er; 
		// for(auto u : tmp){
			// for(auto [x,w] : adj[u]){dif[x].insert(w);}
		// }
		// for(auto idk : er){
			// int u = idk.first.first, v = idk.first.second, w = idk.second; adj[u].erase(mp(v,w)); adj[v].erase(mp(u,w));
		// } //vout(imp);
		for(auto i : imp)f0r(j,2)dp[i][j]=0, vis[i]=0; int cur = S-per; //dout(per);
		for(auto i : imp)if(!vis[i])dfs(i,-1), cur -= max(dp[i][0],dp[i][1]); ans.pb(cur);
		
	} return ans;
}

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