# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
328511 |
2020-11-16T19:38:46 Z |
BarSa |
Sjekira (COCI20_sjekira) |
C++17 |
|
1000 ms |
9860 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define ii pair<int,int>
#define vii vector<ii>
#define pqi priority_queue<int>
#define all(arr) arr.begin(), arr.end()
#define si stack<int>
#define qi queue<int>
const int INF = 1e18;
vvi g;
vii t;
vi t_orig;
vi visited;
vi removed;
int find_max(int cur){
if(visited[cur] || removed[cur]) return -INF;
visited[cur] = 1;
int r = t_orig[cur];
for(auto nei: g[cur]){
int m = find_max(nei);
if(m > r)
r = m;
}
return r;
}
void solve(){
int n; cin >> n;
visited.resize(n);
removed.resize(n, 0);
for(int i=0; i<n; i++){
int a; cin >> a;
t.push_back({-a, i});
t_orig.push_back(a);
}
sort(all(t));
g.resize(n);
for(int i=0; i<n-1; i++){
int u, v; cin >> u >> v; u--; v--;
g[u].push_back(v);
g[v].push_back(u);
}
int ans = 0;
int idx = 0;
for(int i=0; i<n; i++){
for(int i=0; i<n; i++){
visited[i] = 0;
}
for(auto nei: g[t[i].second]){
if(removed[nei]) continue;
visited[t[i].second] = 1;
ans += find_max(nei);
ans += -t[i].first;
}
removed[t[i].second] = 1;
}
cout << ans << endl;
}
int32_t main(){
ios_base::sync_with_stdio(false);
int t=1;
//cin >> t;
for(int i=0; i<t; i++) solve();
return 0;
}
Compilation message
sjekira.cpp: In function 'void solve()':
sjekira.cpp:53:9: warning: unused variable 'idx' [-Wunused-variable]
53 | int idx = 0;
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
0 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1079 ms |
9860 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
0 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
3 ms |
492 KB |
Output is correct |
7 |
Correct |
3 ms |
364 KB |
Output is correct |
8 |
Correct |
2 ms |
364 KB |
Output is correct |
9 |
Correct |
4 ms |
492 KB |
Output is correct |
10 |
Correct |
5 ms |
640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
0 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Execution timed out |
1079 ms |
9860 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |