oj.uz

Submission #786415

# Submission time Handle Problem Language Result Execution time Memory
786415 2023-07-18T07:33:52 Z 박상훈(#10027) Paths (RMI21_paths) C++17
12 / 100
 81 ms 17332 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
constexpr int INF1 = 1e9 + 100;
constexpr ll INF2 = 4e18;

struct Node{
	int x, p;
	ll d;
	Node(){}
	Node(int _x, int _p, ll _d): x(_x), p(_p), d(_d) {}

	bool operator < (const Node &N) const{
		if (d==N.d) return p < N.p;
		return d < N.d;
	}
};

int n, k;
vector<pair<int, ll>> adj[100100];
ll dp1[100100], dp2[100100], D[100100], dist[100100];
int dp1_idx[100100], par[100100], T[100100];

int valP[100100], col[100100], on[100100], onS[100100];
ll ret1, ret2, onD[100100];
ll ans[100100];

void dfs1(int s, int pa = 0, ll paW = 0, int paT = 0){
	dist[s] = paW;
	dp1[s] = 0;
	dp1_idx[s] = s;

	par[s] = pa;
	T[s] = paT;

	for (auto &[v, w]:adj[s]) if (v!=pa){
		dfs1(v, s, paW + w, (paT?paT:v));

		if (dp1[s] < dp1[v] + w){
			dp1[s] = dp1[v] + w;
			dp1_idx[s] = dp1_idx[v];
		}
	}
}

void dfs2(int s, int pa = 0){
	vector<pair<ll, int>> C;
	D[s] = max(dp1[s], dp2[s]);
	
	if (pa) C.emplace_back(dp2[s], s);
	for (auto &[v, w]:adj[s]) if (v!=pa){
		C.emplace_back(dp1[v] + w, v);
	}

	if (!C.empty()) swap(C[0], *max_element(C.begin(), C.end()));
	if (C.size() > 1) swap(C[1], *max_element(C.begin()+1, C.end()));
	for (auto &[v, w]:adj[s]) if (v!=pa){
		if (C[0].second!=v) dp2[v] = C[0].first + w;
		else if (C.size()==1) dp2[v] = w;
		else dp2[v] = C[1].first + w;

		dfs2(v, s);
	}
}

void run(int root, vector<int> P){ // should call dfs1(root) first
	ret1 = 0;
	ret2 = 0;

	fill(valP+1, valP+n+1, 0);
	fill(col+1, col+n+1, 0);
	fill(on+1, on+n+1, 0);
	for (int i=0;i<(int)P.size();i++) valP[P[i]] = (int)P.size() - i;
	
	priority_queue<Node> pq;
	pq.emplace(dp1_idx[root], valP[dp1_idx[root]], dist[dp1_idx[root]]);

	for (int z=1;z<=k;z++) if (!pq.empty()){
		auto [x, _, d] = pq.top(); pq.pop();
		on[x] = 1;
		if (z <= (int)P.size()) assert(_ == (int)P.size() - z + 1);

		ret1 += d;
		while(true){
			for (auto &[y, w]:adj[x]) if (y!=par[x] && !col[y]){
				int z = dp1_idx[y];
				pq.emplace(z, valP[z], dist[z] - dist[x]);
			}

			if (par[x] && !col[x]){
				col[x] = 1;
				x = par[x];
			}

			else break;
		}
	}

	if (!pq.empty()) ret2 = pq.top().d;
}

void dfs3(int s, int pa = 0){
	onS[s] = on[s];
	if (on[s]) onD[s] = 0;
	else onD[s] = INF2;

	for (auto &[v, w]:adj[s]) if (v!=pa){
		dfs3(v, s);
		onS[s] += onS[v];
		onD[s] = min(onD[s], onD[v] + w);
	}
}

void get_optimal(int root){
	dfs1(root);

	vector<pair<ll, int>> C;
	for (auto &[v, w]:adj[root]) C.emplace_back(dp1[v]+w, v);
	assert(C.size() > 1);

	swap(C[0], *max_element(C.begin(), C.end()));
	swap(C[1], *max_element(C.begin()+1, C.end()));

	vector<int> V(2);
	for (int i=1;i<=n;i++) if (i!=root){
		if (dist[i]==C[0].first && T[i]==C[0].second) V[0] = i;
		if (dist[i]==C[1].first && T[i]==C[1].second) V[1] = i;
	}

	assert(V[0] && V[1]);
	run(root, V);
	dfs3(root);
}

void dfs4(int s, ll val, int pa = 0, int flag = 0){
	ans[s] = val;

	for (auto &[v, w]:adj[s]) if (v!=pa){
		if (!col[v] || flag){
			dfs4(v, val+w, s, flag);
		}

		else if (onS[v]==1 && val-onD[v]+ret2 > val){
			dfs4(v, val-onD[v]+ret2, s, 1);
		}

		else{
			dfs4(v, val, s, 0);
		}
	}
}

int main(){
	scanf("%d %d", &n, &k);

	for (int i=1;i<=n-1;i++){
		int x, y, z;
		scanf("%d %d %d", &x, &y, &z);
		adj[x].emplace_back(y, z);
		adj[y].emplace_back(x, z);
	}

	dfs1(1);
	dfs2(1);

	if (k==1){
		for (int i=1;i<=n;i++){
			printf("%lld\n", D[i]);
		}
		return 0;
	}

	if (n==2){
		for (int i=1;i<=n;i++) printf("%lld\n", adj[1][0].second);
		return 0;
	}

	int root = -1;
	ll valD = INF2;

	for (int i=1;i<=n;i++) if (D[i] < valD && adj[i].size() > 1){
		valD = D[i];
		root = i;
	}

	assert(root!=-1);
	get_optimal(root);
	dfs4(root, ret1);

	for (int i=1;i<=n;i++){
		printf("%lld\n", ans[i]);
	}
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:155:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  155 |  scanf("%d %d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:159:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  159 |   scanf("%d %d %d", &x, &y, &z);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 13180 KB Output is correct
2 Correct 67 ms 17332 KB Output is correct
3 Correct 66 ms 13032 KB Output is correct
4 Correct 63 ms 13160 KB Output is correct
5 Correct 81 ms 14848 KB Output is correct
6 Correct 62 ms 13120 KB Output is correct

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -