Submission #23189

#	Time	Username	Problem	Language	Result	Execution time	Memory
23189		gs14004	Logistical Metropolis (KRIII5_LM)	C++11	7 / 7	1506 ms	46056 KiB

LM

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;

const int MAXN = 100005;
struct disj{
	int pa[MAXN], sz[MAXN];
	void init(int n){
		for(int i=0; i<=n; i++){
			pa[i] = i;
			sz[i] = 1;
		}
	}
	int find(int x){
		return pa[x] = (pa[x] == x ? x : find(pa[x]));
	}
	bool uni(int p, int q){
		p = find(p);
		q = find(q);
		if(p == q) return 0;
		pa[q] = p;
		sz[p] += sz[q];
		return 1;
	}
}disj;

struct edg{
	int s, e, x; 
	bool operator<(const edg &e)const{
		return x < e.x;
	}
}e[300005];

vector<pi> gph[100005];
vector<pi> edg[100005];

int n, m;
int par[17][100005], pae[17][100005], dfn[100005], dout[100005], piv;
int dep[100005];

bool in(int s, int t){
	return dfn[s] <= dfn[t] && dout[t] <= dout[s];
}

void dfs(int x, int p){
	dfn[x] = ++piv;
	for(auto &i : gph[x]){
		if(i.second != p){
			dep[i.second] = dep[x] + 1;
			par[0][i.second] = x;
			pae[0][i.second] = i.first;
			dfs(i.second, x);
		}
	}
	dout[x] = piv;
}

pi lca(int s, int e){
	if(dep[s] < dep[e]) swap(s, e);
	int dx = dep[s] - dep[e];
	int ret = 0;
	for(int i=0; i<17; i++){
		if((dx >> i) & 1){
			ret = max(ret, pae[i][s]);
			s = par[i][s];
		}
	}
	for(int i=16; i>=0; i--){
		if(par[i][s] != par[i][e]){
			ret = max({ret, pae[i][s], pae[i][e]});
			s = par[i][s];
			e = par[i][e];
		}
	}
	if(s != e){
		ret = max({ret, pae[0][s], pae[0][e]});
		s = par[0][s];
		e = par[0][e];
	}
	return pi(s, ret);
}

vector<pi> cnd[100005];
lint dp[100005][2];
int chk[100005];

void dfs2(int x, int p){
	lint up = -1e18;
	for(auto &i : cnd[x]){
		if(i.second == p) continue;
		dfs2(i.second, x);
		dp[i.second][0] = max(dp[i.second][0], dp[i.second][1] + i.first);
		dp[x][0] += dp[i.second][0];
		dp[x][1] += dp[i.second][0];
		up = max(up, dp[i.second][1] - dp[i.second][0]);
	}
	dp[x][1] += up;
	if(chk[x]){
		dp[x][1] = dp[x][0];
		dp[x][0] = -1e18;
	}
}

lint solve(int r){
	if(edg[r].empty()) return 0;
	vector<int> v = {r};
	for(auto &j : edg[r]){
		v.push_back(j.second);
	}
	sort(v.begin(), v.end(), [&](const int &a, const int &b){
		return dfn[a] < dfn[b];
	});
	int l = v.size();
	for(int i=1; i<l; i++) v.push_back(lca(v[i-1], v[i]).first);
	sort(v.begin(), v.end(), [&](const int &a, const int &b){
		return dfn[a] < dfn[b];
	});
	stack<int> stk;
	for(auto &i : v){
		if(!stk.empty() && stk.top() == i) continue;
		while(!stk.empty() && !in(stk.top(), i)) stk.pop();
		if(!stk.empty()){
			int l = lca(stk.top(), i).second;
			cnd[stk.top()].push_back(pi(l, i));
			cnd[i].push_back(pi(l, stk.top()));
		}
		stk.push(i);
	}
	lint ret = 0;
	for(auto &j : edg[r]){
		chk[j.second] = 1;
		ret += j.first;
	}
	dfs2(r, -1);
	ret -= dp[r][0];
	for(auto &i : v){
		cnd[i].clear();
		chk[i] = 0;
		dp[i][0] = dp[i][1] = 0;
	}
	return ret;
}

int main(){
	scanf("%d %d",&n,&m);
	for(int i=0; i<m; i++){
		scanf("%d %d %d",&e[i].s,&e[i].e,&e[i].x);
	}
	sort(e, e+m);
	disj.init(n);
	lint ans = 0;
	for(int i=0; i<m; i++){
		if(disj.uni(e[i].s, e[i].e)){
			gph[e[i].s].push_back(pi(e[i].x, e[i].e));
			gph[e[i].e].push_back(pi(e[i].x, e[i].s));
			ans += e[i].x;
		}
		edg[e[i].s].push_back(pi(e[i].x, e[i].e));
		edg[e[i].e].push_back(pi(e[i].x, e[i].s));
	}
	dfs(1, 0);
	for(int i=1; i<17; i++){
		for(int j=1; j<=n; j++){
			par[i][j] = par[i-1][par[i-1][j]];
			pae[i][j] = max(pae[i-1][j], pae[i-1][par[i-1][j]]);
		}
	}
	for(int i=1; i<=n; i++){
		printf("%lld\n", ans + solve(i));
	}
}

Compilation message (stderr)

LM.cpp: In function 'int main()':
LM.cpp:146:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
                      ^
LM.cpp:148:44: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&e[i].s,&e[i].e,&e[i].x);
                                            ^

• Subtask 1: 2 / 2
• Subtask 2: 5 / 5