oj.uz

Submission #548491

# Submission time Handle Problem Language Result Execution time Memory
548491 2022-04-13T14:38:53 Z kym Paths (RMI21_paths) C++14
100 / 100
 345 ms 26600 KB 
#include <bits/stdc++.h>
using namespace std;
#define int ll 
#define FOR(i,s,e) for(ll i = s; i <= (ll)e; ++i)
#define DEC(i,s,e) for(ll i = s; i >= (ll)e; --i)
#define IAMSPEED ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
#define db(x) cerr << #x << "=" << x << "\n"
#define db2(x, y) cerr << #x << "=" << x << " , " << #y << "=" << y << "\n"
#define db3(a,b,c) cerr<<#a<<"="<<a<<","<<#b<<"="<<b<<","<<#c<<"="<<c<<"\n"
#define dbv(v) cerr << #v << ":"; for (auto ite : v) cerr << ite << ' '; cerr <<"\n"
#define dbvp(v) cerr << #v << ":"; for (auto ite : v) cerr << "{"  << ite.f << ',' << ite.s << "} "; cerr << "\n"
#define dba(a,ss,ee) cerr << #a << ":"; FOR(ite,ss,ee) cerr << a[ite] << ' '; cerr << "\n"
#define reach cerr << "LINE: " << __LINE__ << "\n";
#else
#define db(x)
#define db2(x,y)
#define db3(a,b,c)
#define dbv(v)
#define dbvp(v)
#define dba(a,ss,ee)
#define reach 
#endif
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define ll long long 
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define f first
#define s second
#define g0(x) get<0>(x)
#define g1(x) get<1>(x)
#define g2(x) get<2>(x)
#define g3(x) get<3>(x)
typedef pair <ll, ll> pi;
typedef tuple<ll,ll,ll> ti3;
typedef tuple<ll,ll,ll,ll> ti4;
ll rand(ll a, ll b) { return a + rng() % (b-a+1); }
const int MOD = 1e9 + 7;
const int inf = (int)1e9 + 500;
const long long oo = (ll)1e18 + 500;
template <typename T> void chmax(T& a, const T b) { a=max(a,b); }
template <typename T> void chmin(T& a, const T b) { a=min(a,b); }
const int MAXN = 100005;
int n,k;
vector<pi> V[MAXN];
set<pi> in; // {num[x],x}
set<pi,greater<pi>> out; // {num[x], x}
int dist[MAXN];
pi down[MAXN];
pi up[MAXN];
int par[MAXN];
int num[MAXN];
int W[MAXN];
int output[MAXN];
int st[MAXN];
int en[MAXN];
int cnt;
vector<int> leaves;

bool ispar(int p, int x) {
	if(st[p] <= st[x] && en[p] >= en[x]) return 1;
	else return 0;
}

pi dfs1(int x, int p) {
	st[x]=cnt++;
	par[x] = p;
	if(V[x].size() == 1 && p != -1) {
		leaves.pb(x);
		down[x]=pi(0, x);
		en[x]=cnt-1;
		return pi(0,x);
	}
	for(auto v:V[x])if(v.f != p){
		dist[v.f] = dist[x] + v.s;
		W[v.f] = v.s;
		pi r=dfs1(v.f,x);
		r.f += v.s;
		chmax(down[x],r);
	}
	en[x]=cnt-1;
	return down[x];
}

void dfs2(int x, int p) {
	vector<pi> vec;
	vec.pb(pi(up[x].f+W[x], up[x].s));
	for(auto v:V[x])if(v.f != p) {
		vec.pb(pi(down[v.f].f+v.s, down[v.f].s));
		sort(all(vec), [](pi a, pi b) {
			return a.f > b.f;
		});
		while((int)vec.size() >= 3)vec.pop_back();
	}
	for(auto v:V[x])if(v.f != p){
		if(ispar(v.f,vec[0].s)) {
			up[v.f]=vec[1];
		} else {
			up[v.f]=vec[0];
		}
	}
	for(auto v:V[x])if(v.f != p) dfs2(v.f,x);
}
int ans;

void update(int x, int nval) {
	if(in.size() && in.find(pi(num[x],x)) != in.end()) {
		auto it=in.find(pi(num[x],x));
		pi into = pi(it->f+nval,it->s);
		in.erase(it);
		in.insert(pi(into.f,into.s));
		num[x]+=nval;
		ans += nval;
	}
	else if(out.size() && out.find(pi(num[x],x)) != out.end()) {
		auto it=out.find(pi(num[x],x));
		pi into = pi(it->f+nval,it->s);
		out.erase(it);
		out.insert(pi(into.f,into.s));
		
		num[x]+=nval;
	} else{
		assert(in.empty() || out.empty());
	}
}

void rebalance() {
	if(in.empty() || out.empty()) return;
	pi inside=*in.begin();
	pi outside=*out.begin();
	while(inside.f < outside.f) {
		ans += outside.f;
		ans -= inside.f;
		in.erase(in.begin());
		out.erase(out.begin());
		in.insert(outside);
		out.insert(inside);
		
		inside=*in.begin();
		outside=*out.begin();
	}
}

void solve(int x, int p) {
	output[x] = ans;
	db(x);
	for(auto v:V[x])if(v.f!=p) {
		
		pi r1 = down[v.f];
		pi r2 = up[v.f];
		
		update(r1.s, -W[v.f]);
		update(r2.s, W[v.f]);
		
		rebalance();
		
		solve(v.f, x);

		update(r1.s, W[v.f]);
		update(r2.s, -W[v.f]);
		rebalance();
		db(x);
		dbvp(in);
		dbvp(out);
	
	}
}

int32_t main() 
{
	IAMSPEED
	cin >> n >> k;
	FOR(i,1,n-1) {
		int a,b,c; cin >> a >> b >> c;
		V[a].pb(pi(b,c));
		V[b].pb(pi(a,c));
	}
	dfs1(1,-1);
	reach
	up[1] = pi(0,1);
	dfs2(1,-1);
	FOR(i,2,n) {
		db3(i,down[i].s,down[i].f);
		db3(i,up[i].s,up[i].f);
		num[down[i].s]+=W[i];
	}
	
	for(auto i:leaves) {
		out.insert(pi(num[i],i));
	}
	if(V[1].size() == 1)out.insert(pi(0,1));
	dbv(leaves);
	while(out.size() && (int)in.size() < k) {
		in.insert(*out.begin());
		ans += out.begin()->f;
		out.erase(out.begin());
	}
	if((int)in.size() < k) { //just take every single edge. 
		FOR(i,1,n) {
			cout << ans << '\n';
		}
		exit(0);
	}
	reach
	solve(1,-1);
	FOR(i,1,n) cout << output[i] << '\n';
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2684 KB Output is correct
2 Correct 2 ms 2684 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2684 KB Output is correct
2 Correct 2 ms 2684 KB Output is correct
3 Correct 2 ms 2680 KB Output is correct
4 Correct 2 ms 2684 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2684 KB Output is correct
2 Correct 2 ms 2684 KB Output is correct
3 Correct 2 ms 2680 KB Output is correct
4 Correct 2 ms 2684 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 4 ms 2900 KB Output is correct
9 Correct 3 ms 2900 KB Output is correct
10 Correct 4 ms 2856 KB Output is correct
11 Correct 3 ms 2824 KB Output is correct
12 Correct 2 ms 2900 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2684 KB Output is correct
2 Correct 2 ms 2684 KB Output is correct
3 Correct 2 ms 2680 KB Output is correct
4 Correct 2 ms 2684 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 4 ms 2900 KB Output is correct
9 Correct 3 ms 2900 KB Output is correct
10 Correct 4 ms 2856 KB Output is correct
11 Correct 3 ms 2824 KB Output is correct
12 Correct 2 ms 2900 KB Output is correct
13 Correct 5 ms 3156 KB Output is correct
14 Correct 4 ms 3208 KB Output is correct
15 Correct 4 ms 3084 KB Output is correct
16 Correct 5 ms 3156 KB Output is correct
17 Correct 5 ms 3032 KB Output is correct
18 Correct 4 ms 3000 KB Output is correct
19 Correct 5 ms 3020 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 21456 KB Output is correct
2 Correct 269 ms 24272 KB Output is correct
3 Correct 180 ms 20120 KB Output is correct
4 Correct 271 ms 23164 KB Output is correct
5 Correct 282 ms 24392 KB Output is correct
6 Correct 265 ms 23332 KB Output is correct

Subtask #6
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2684 KB Output is correct
2 Correct 2 ms 2684 KB Output is correct
3 Correct 2 ms 2680 KB Output is correct
4 Correct 2 ms 2684 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 4 ms 2900 KB Output is correct
9 Correct 3 ms 2900 KB Output is correct
10 Correct 4 ms 2856 KB Output is correct
11 Correct 3 ms 2824 KB Output is correct
12 Correct 2 ms 2900 KB Output is correct
13 Correct 5 ms 3156 KB Output is correct
14 Correct 4 ms 3208 KB Output is correct
15 Correct 4 ms 3084 KB Output is correct
16 Correct 5 ms 3156 KB Output is correct
17 Correct 5 ms 3032 KB Output is correct
18 Correct 4 ms 3000 KB Output is correct
19 Correct 5 ms 3020 KB Output is correct
20 Correct 275 ms 21456 KB Output is correct
21 Correct 269 ms 24272 KB Output is correct
22 Correct 180 ms 20120 KB Output is correct
23 Correct 271 ms 23164 KB Output is correct
24 Correct 282 ms 24392 KB Output is correct
25 Correct 265 ms 23332 KB Output is correct
26 Correct 316 ms 23604 KB Output is correct
27 Correct 281 ms 25912 KB Output is correct
28 Correct 345 ms 26600 KB Output is correct
29 Correct 178 ms 20332 KB Output is correct
30 Correct 325 ms 23532 KB Output is correct
31 Correct 250 ms 21572 KB Output is correct
32 Correct 292 ms 24704 KB Output is correct
33 Correct 313 ms 23548 KB Output is correct
34 Correct 157 ms 19976 KB Output is correct
35 Correct 282 ms 23668 KB Output is correct
36 Correct 239 ms 26456 KB Output is correct