# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
793078 | 2023-07-25T13:35:30 Z | 1075508020060209tc | Sjekira (COCI20_sjekira) | C++14 | 82 ms | 20328 KB |
#include <bits/stdc++.h> using namespace std; #define int long long int n; int ar[500005]; vector<int>e[500005]; int uf[500005]; int umx[500005]; int fin(int x){ if(uf[x]==x){return x;} uf[x]=fin(uf[x]); return uf[x]; } void mrg(int a,int b){ int pa=fin(a);int pb=fin(b); if(pa==pb){return;} uf[pa]=pb; umx[pb]=max(umx[pa],umx[pb]); } signed main() { cin>>n; for(int i=1;i<=n;i++){ cin>>ar[i]; uf[i]=i; umx[i]=ar[i]; } for(int i=1;i<=n-1;i++){ int a;int b; cin>>a>>b; e[a].push_back(b); e[b].push_back(a); } int ans=0; vector<pair<int,int>>seq; for(int i=1;i<=n;i++){ seq.push_back({ar[i],i}); } //cout<<"hihi"; sort(seq.begin(),seq.end()); for(int i=0;i<seq.size();i++){ int nw=seq[i].second; for(int j=0;j<e[nw].size();j++){ int v=e[nw][j]; if(fin(v)==fin(nw)){continue;} ans+=umx[fin(v)]+umx[fin(nw)]; mrg(v,nw); } } cout<<ans<<endl; return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 6 ms | 11988 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 82 ms | 20328 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 6 ms | 11988 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 6 ms | 11988 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |