# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
854457 |
2023-09-27T16:53:09 Z |
vjudge1 |
Sjekira (COCI20_sjekira) |
C++17 |
|
1000 ms |
30456 KB |
//author: Ahmet Alp Orakci
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
#define ONLINE_JUDGE
void solve() {
int n;
cin >> n;
vector <int> vec(n +1);
for(int i = 1; i <= n; i++)
cin >> vec[i];
set <int> adj[n +1];
for(int i = 1; i <= n -1; i++) {
int u, v;
cin >> u >> v;
adj[u].emplace(v);
adj[v].emplace(u);
}
function <int(int, int)> dfsMax = [&](int node, int par) -> int {
int ind = node;
for(const int &child : adj[node]) {
if(child != par) {
int g = dfsMax(child, node);
//cerr << child << " " << node << " :: " << g << "\n";
if(vec[g] >= vec[ind]) {
ind = g;
}
}
}
return ind;
};
int res = 0;
function <void(int)> dfsAns = [&](int node) -> void {
//cerr << "# " << node << "\n";
int cev = 0;
vector <int> vvec;
for(const int &child : adj[node]) {
cev += vec[node];
int g = dfsMax(child, node);
cerr << child << " " << node << " :: " << g << "\n";
cev += vec[g];
adj[child].erase(node);
vvec.emplace_back(child);
}
adj[node].clear();
for(int &i : vvec) {
dfsAns(dfsMax(i, node));
}
//cerr << node << " " << cev << "\n";
res += cev;
};
dfsAns(dfsMax(1, 0));
cout << res;
return;
}
signed main() {
#ifndef ONLINE_JUDGE
freopen(".in", "r", stdin);
freopen(".out", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int t = 1; //cin >> t;
for(int i = 1; i <= t; i++) {
solve();
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
624 ms |
24820 KB |
Output is correct |
2 |
Correct |
479 ms |
18896 KB |
Output is correct |
3 |
Correct |
457 ms |
18148 KB |
Output is correct |
4 |
Correct |
534 ms |
20436 KB |
Output is correct |
5 |
Correct |
793 ms |
30456 KB |
Output is correct |
6 |
Execution timed out |
1066 ms |
28380 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
9 ms |
600 KB |
Output is correct |
7 |
Correct |
8 ms |
648 KB |
Output is correct |
8 |
Correct |
7 ms |
604 KB |
Output is correct |
9 |
Correct |
13 ms |
860 KB |
Output is correct |
10 |
Correct |
18 ms |
756 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
624 ms |
24820 KB |
Output is correct |
7 |
Correct |
479 ms |
18896 KB |
Output is correct |
8 |
Correct |
457 ms |
18148 KB |
Output is correct |
9 |
Correct |
534 ms |
20436 KB |
Output is correct |
10 |
Correct |
793 ms |
30456 KB |
Output is correct |
11 |
Execution timed out |
1066 ms |
28380 KB |
Time limit exceeded |
12 |
Halted |
0 ms |
0 KB |
- |