| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 680978 |
2023-01-12T07:34:01 Z |
vjudge1 |
Toll (APIO13_toll) |
C++17 |
|
3 ms |
4948 KB |
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define endl '\n'
#define int long long
#define all(a) a.begin(),a.end()
#define pb push_back
#define mod 1000000007
#define inf 1e18
#define ppb pop_back
#define ff first
#define ss second
/// order_of_key return number of elements less than x -> os.order_of_key(x)
/// cout << "oth element : " << *os.find_by_order(0) << endl; so it returns value of index
int lcm(int x,int y)
{
return (x * 1LL * y) / __gcd(x,y);
}
// Graph on 2D Grid
/*----------------------Graph Moves----------------*/
//const int dx[]={+1,-1,+0,+0};
//const int dy[]={+0,+0,+1,-1};
//const int dx[]={+0,+0,+1,-1,-1,+1,-1,+1}; // Kings Move
//const int dy[]={-1,+1,+0,+0,+1,+1,-1,-1}; // Kings Move
//const int dx[]={-2, -2, -1, -1, 1, 1, 2, 2}; // Knights Move
//const int dy[]={-1, 1, -2, 2, -2, 2, -1, 1}; // Knights Move
/*------------------------------------------------*/
#define debug(x); cerr << #x <<" "; _print(x); cerr << endl;
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(double t) {cerr << t;}
template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
const int N=2e5+4;
int par[N],ar[N],cnt[N];
vector<pair<int,int> >v[N];
int find(int a)
{
if(a==par[a])
{
return a;
}
return par[a]=find(par[a]);
}
void dfs(int a,int p)
{
for(auto b:v[a])
{
if(b.first!=p)
{
dfs(b.first,a);
ar[a]+=ar[b.first];
}
}
}
void dfs1(int a,int p,int val)
{
cnt[a]=val;
for(auto b:v[a])
{
if(b.first!=p)
{
dfs1(b.first,a,max(val,b.second));
}
}
}
void solve()
{
int n,i,m,k,a,b,c,d;
cin>>n>>m>>k;
vector<pair<int,pair<int,int> > >v1;
vector<pair<int,int> >v2;
for(i=0;i<m;i++)
{
cin>>a>>b>>c;
v1.push_back({c,{a,b}});
}
for(i=0;i<k;i++)
{
cin>>a>>b;
v2.push_back({a,b});
}
for(i=1;i<=n;i++)
{
cin>>ar[i];
}
for(i=1;i<=n;i++)
{
par[i]=i;
}
sort(v1.begin(),v1.end());
for(i=0;i<m;i++)
{
a=v1[i].second.first;
b=v1[i].second.second;
c=find(a);
d=find(b);
if(c!=d)
{
par[c]=d;
v[a].push_back({b,v1[i].first});
v[b].push_back({a,v1[i].first});
}
}
dfs(1,-1);
int ans=0;
for(i=0;i<k;i++)
{
a=v2[i].first;
b=v2[i].second;
dfs1(a,-1,0);
ans+=(cnt[b]*min(ar[a],ar[b]));
}
cout<<ans<<endl;
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;
//cin >> t;
while(t--)
{
solve();
}
}
/**
Test Case :
**/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
