4254 | 2023. 03. 19 19:02:47 | horvathabel | Útadó | cpp17 | Hibás válasz 0/50 | 800ms | 8500 KiB |
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
vector<ll> g[50001];
vector<ll>c;
vector<pair<ll,int>> db ;
ll dfs(int x){
if (c[x]==0){
db[x]={1,x};
return db[x].first;
}
else{
for (int edge:g[x]){
db[x].first+=dfs(edge);
db[x].second=x;
}
}
return (db[x].first);
}
int main() {
int n;
cin>>n;
c.assign(n+1, 0);
vector<int> p;
p.resize(n+1);
for (int i=1;i<n;i++)
{
ll x,y;
cin>>x>>y;
db.assign(n+1, {1,0});
c[x]++;
p[y]=x;
g[x].push_back(y);
}
vector<ll> arak;
for (int i=1; i<n;i++){
ll x;
cin>>x;
arak.push_back(x);
}
dfs(1);
for (int i=1; i<=n;i++) db[i].first=db[i].first*(n-db[i].first);
sort(db.begin(), db.end());
sort(arak.begin(), arak.end());
ll ans=0;
vector<pair<pair<ll, ll>,ll>> cnt;
for (int i=2; i<=n;i++){
ans+=db[i].first*arak[i-2]*2;
ans=ans%32609;
cnt.push_back({{db[i].second, p[db[i].second]},arak[i-2]});
}
cout<<ans;
for (auto x: cnt) cout<<x.first.first<<" "<<x.first.second<<" "<<x.second<<endl;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 0/50 | ||||||
1 | Hibás válasz | 0/0 | 4ms | 4284 KiB | |||
2 | Hibás válasz | 0/0 | 493ms | 8500 KiB | |||
3 | Hibás válasz | 0/2 | 4ms | 4584 KiB | |||
4 | Hibás válasz | 0/2 | 4ms | 4800 KiB | |||
5 | Hibás válasz | 0/2 | 4ms | 5064 KiB | |||
6 | Hibás válasz | 0/2 | 4ms | 5260 KiB | |||
7 | Hibás válasz | 0/2 | 4ms | 5496 KiB | |||
8 | Időlimit túllépés | 0/8 | 763ms | 5432 KiB | |||
9 | Hibás válasz | 0/2 | 8ms | 5920 KiB | |||
10 | Hibás válasz | 0/2 | 7ms | 6168 KiB | |||
11 | Hibás válasz | 0/2 | 8ms | 6220 KiB | |||
12 | Hibás válasz | 0/2 | 8ms | 6224 KiB | |||
13 | Hibás válasz | 0/2 | 7ms | 6320 KiB | |||
14 | Időlimit túllépés | 0/2 | 800ms | 6060 KiB | |||
15 | Időlimit túllépés | 0/2 | 768ms | 6268 KiB | |||
16 | Időlimit túllépés | 0/2 | 726ms | 6292 KiB | |||
17 | Időlimit túllépés | 0/2 | 754ms | 6568 KiB | |||
18 | Időlimit túllépés | 0/2 | 765ms | 6444 KiB | |||
19 | Időlimit túllépés | 0/2 | 737ms | 6772 KiB | |||
20 | Időlimit túllépés | 0/2 | 763ms | 6836 KiB | |||
21 | Időlimit túllépés | 0/2 | 745ms | 6968 KiB | |||
22 | Időlimit túllépés | 0/2 | 774ms | 6920 KiB | |||
23 | Időlimit túllépés | 0/2 | 750ms | 7028 KiB | |||
24 | Időlimit túllépés | 0/2 | 763ms | 7056 KiB |