| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 586812 |
2022-06-30T17:36:49 Z |
1ne |
Toll (APIO13_toll) |
C++14 |
|
1 ms |
212 KB |
#include<bits/stdc++.h>
using namespace std;
struct node{
long long x,y,cost;
};
struct DSU{
vector<long long>parent,sz;
//vector<pair<long long,long long>>ops;
set<pair<long long,long long>>new_edge;
vector<vector<pair<long long,long long>>>adj;
vector<vector<long long>>comp;
vector<long long>maxxy;
vector<vector<node>>pos;
void build(long long n){
parent.resize(n);
sz.resize(n);
adj.resize(n);
comp.resize(n);
maxxy.resize(n);
for (long long i = 0;i<n;++i){
parent[i] = i;
sz[i] = 1;
maxxy[i] = 0;
comp[i].push_back(i);
}
}
void add_edge(long long u,long long v){
new_edge.insert({max(u,v),min(u,v)});
}
long long findsets(long long v){
if (v == parent[v])return v;
parent[v] = findsets(parent[v]);
return parent[v];
}
bool unionset(long long a,long long b,long long cost){
long long u = findsets(a);
long long v = findsets(b);
if (u == v)return false;
if (sz[u] < sz[v])swap(u,v);
int counts = 0;
for (auto x:comp[u]){
for (auto y:comp[v]){
if (new_edge.find({max(x,y),min(x,y)})!=new_edge.end()){
if (counts == 0){
pos.emplace_back();
}
pos.back().push_back({x,y,max({cost,maxxy[v],maxxy[u]})});
counts++;
new_edge.erase({max(x,y),min(x,y)});
}
}
}
if (counts==0){
adj[a].push_back({b,0});
adj[b].push_back({a,0});
}
//ops.push_back({v,parent[v]});
parent[v] = u;
//ops.push_back({~u,sz[u]});
sz[u]+=sz[v];
maxxy[u] = max({cost,maxxy[u],maxxy[v]});
comp[u].insert(comp[u].end(),comp[v].begin(),comp[v].end());
comp[v].clear();
return true;
}
/*void roll_back(long long v){
while((long long)ops.size() > v){
long long i = ops.back().first;
long long j = ops.back().second;
ops.pop_back();
if (i >= 0){
parent[i] = j;
}
else{
sz[~i] = j;
}
}
}
*/
};
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
long long n,m,k;cin>>n>>m>>k;
vector<node>edge(m);
for (long long i = 0;i<m;++i){
long long x,y,cost;
cin>>x>>y>>cost;
--x;
--y;
edge.push_back({x,y,cost});
}
sort(edge.begin(),edge.end(),[&](auto x,auto y){
return x.cost < y.cost;
});
DSU st;
st.build(n);
for (long long i = 0;i<k;++i){
long long x,y;cin>>x>>y;
--x;
--y;
st.add_edge(x,y);
}
vector<long long>p(n);
for (long long i = 0;i<n;++i)cin>>p[i];
for (auto x:edge){
st.unionset(x.x,x.y,x.cost);
}
const int mxn = 1e9;
auto getmaxx =[&](){
vector<long long>dist(n,mxn);
dist[0] = 0;
queue<int>q;
q.push(0);
while(!q.empty()){
auto u = q.front();
q.pop();
for (auto x:st.adj[u]){
if (dist[x.first] > dist[u] + x.second){
dist[x.first] = dist[u] + x.second;
q.push(x.first);
}
}
}
long long ans = 0;
for (int i = 0;i<n;++i){
ans+=dist[i] * p[i];
}
return ans;
};
long long ans = 0;
function<void(int)>solve = [&](int u){
if (u == -1){
ans = max(ans,getmaxx());
return;
}
for (auto x:st.pos[u]){
st.adj[x.x].push_back({x.y,x.cost});
st.adj[x.y].push_back({x.x,x.cost});
solve(u - 1);
st.adj[x.x].pop_back();
st.adj[x.y].pop_back();
}
};
solve((int)st.pos.size() - 1);
cout<<ans<<'\n';
return 0;
}
/*
5 5 1
3 5 2
1 2 3
2 3 5
2 4 4
4 3 6
5 4
10 20 30 40 50
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
