oj.uz

Submission #1067870

# Submission time Handle Problem Language Result Execution time Memory
1067870 2024-08-21T04:55:57 Z 김은성(#11126) Paths (RMI21_paths) C++17
19 / 100
 600 ms 13396 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100010;
typedef long long ll;
vector<pair<int, ll> > graph[MAXN];
vector<int> child[MAXN];
bool ch[MAXN];
int par[MAXN];
ll cost[MAXN];
void settree(int v){
	for(auto [u, c]: graph[v]){
		if(par[v] == u)
			continue;
		par[u] = v;
		settree(u);
		cost[u] = c;
	}
}
ll maxcost(int v){
	if(ch[v])
		return 0;
	return cost[v] + maxcost(par[v]);
}
void check(int v){
	if(ch[v])
		return;
	ch[v] = 1;
	check(par[v]);
}
int main(){
	int n, k, i, j, a, b;
	ll c;
	scanf("%d %d", &n, &k);
	for(i=1; i<n; i++){
		scanf("%d %d %lld", &a, &b, &c);
		graph[a].push_back(make_pair(b, c));
		graph[b].push_back(make_pair(a, c));
	}
	for(int r=1; r<=n; r++){
		memset(ch, 0, sizeof(ch));
		ch[0] = 1;
		cost[r] = 0;
		par[r] = 0;
		settree(r);
		ll ans = 0;
		for(i=1; i<=k; i++){
			int opt = -1;
			ll mx = -1;
			for(j=1; j<=n; j++){
				ll temp = maxcost(j);
				//printf("j=%d temp=%lld\n", j, temp);
				if(temp > mx){
					mx = temp;
					opt = j;
				}
			}
			ans += mx;
			check(opt);
		}
		printf("%lld\n", ans);
	}
	return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |  scanf("%d %d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:35:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |   scanf("%d %d %lld", &a, &b, &c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6236 KB Output is correct
2 Correct 2 ms 5980 KB Output is correct
3 Correct 5 ms 6228 KB Output is correct
4 Correct 6 ms 6232 KB Output is correct
5 Correct 4 ms 6236 KB Output is correct
6 Correct 7 ms 6248 KB Output is correct
7 Correct 7 ms 6248 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6236 KB Output is correct
2 Correct 2 ms 5980 KB Output is correct
3 Correct 5 ms 6228 KB Output is correct
4 Correct 6 ms 6232 KB Output is correct
5 Correct 4 ms 6236 KB Output is correct
6 Correct 7 ms 6248 KB Output is correct
7 Correct 7 ms 6248 KB Output is correct
8 Correct 365 ms 6244 KB Output is correct
9 Execution timed out 601 ms 6340 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6236 KB Output is correct
2 Correct 2 ms 5980 KB Output is correct
3 Correct 5 ms 6228 KB Output is correct
4 Correct 6 ms 6232 KB Output is correct
5 Correct 4 ms 6236 KB Output is correct
6 Correct 7 ms 6248 KB Output is correct
7 Correct 7 ms 6248 KB Output is correct
8 Correct 365 ms 6244 KB Output is correct
9 Execution timed out 601 ms 6340 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1055 ms 13396 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6236 KB Output is correct
2 Correct 2 ms 5980 KB Output is correct
3 Correct 5 ms 6228 KB Output is correct
4 Correct 6 ms 6232 KB Output is correct
5 Correct 4 ms 6236 KB Output is correct
6 Correct 7 ms 6248 KB Output is correct
7 Correct 7 ms 6248 KB Output is correct
8 Correct 365 ms 6244 KB Output is correct
9 Execution timed out 601 ms 6340 KB Time limit exceeded
10 Halted 0 ms 0 KB -