oj.uz

Submission #786361

# Submission time Handle Problem Language Result Execution time Memory
786361 2023-07-18T07:01:23 Z 박상훈(#10027) Paths (RMI21_paths) C++17
12 / 100
 73 ms 14892 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int n, k;
vector<pair<int, ll>> adj[100100];
ll dp1[100100], dp2[100100], D[100100];

void dfs1(int s, int pa = 0){
	dp1[s] = 0;
	for (auto &[v, w]:adj[s]) if (v!=pa){
		dfs1(v, s);
		dp1[s] = max(dp1[s], dp1[v] + w);
	}
}

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);
	}
}

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;
	}


}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |  scanf("%d %d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |   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 57 ms 11160 KB Output is correct
2 Correct 60 ms 14892 KB Output is correct
3 Correct 52 ms 11100 KB Output is correct
4 Correct 56 ms 11156 KB Output is correct
5 Correct 73 ms 12716 KB Output is correct
6 Correct 53 ms 11168 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 -