| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 872933 |
2023-11-14T05:29:31 Z |
gggkik |
Toll (APIO13_toll) |
C++14 |
|
4 ms |
12380 KB |
#include <bits/stdc++.h>
using namespace std;
const int MXN = 1e5+5;
using pii = pair<int,int>;
using ll = long long;
struct dsu{
vector<int> par;
void init(int x){
par.resize(x+1);
iota(par.begin(),par.end(),0);
}
int find(int x){
return par[x]-x?par[x]=find(par[x]):x;
}
void u(int a,int b){
a = find(a), b = find(b);
if(a!=b) par[a] = b;
}
};
vector<vector<int>> build_mst(int n, vector<vector<int>> edges){
dsu uf; uf.init(n);
sort(edges.begin(),edges.end(),[&](vector<int> &i, vector<int> &j){
return i[2]<j[2];
});
vector<vector<int>> ret;
for(auto &i : edges){
int a = uf.find(i[0]), b = uf.find(i[1]);
if(a!=b) {
uf.u(a,b);
ret.push_back(i);
}
}
return ret;
}
vector<pii> E[MXN];
void build(int n,vector<vector<int>> &v){
for(int i = 1;i<=n;i++) E[i].clear();
for(auto &j : v){
E[j[0]].push_back({j[1],j[2]});
E[j[1]].push_back({j[0],j[2]});
}
}
ll A[MXN], P[MXN];
int h[MXN], par[MXN];
void dfs(int x,int p){
par[x] = p;
h[x] = h[p]+1;
for(auto i : E[x]) if(i.first!=p){
P[i.first] = i.second;
dfs(i.first,x);
}
}
int lca(int a,int b){
int mxp = 0;
while(a!=b){
if(h[a]<h[b]) swap(a,b);
if(P[mxp]<P[a]) mxp = a;
a = par[a];
}
return mxp;
}
int L[MXN], ck[MXN], rt[MXN], rpar[MXN], vis[MXN];
set<pii> G[MXN];
ll sz[MXN];
void f(int x,int r,int p){
rt[x] = r;
sz[r] += A[x];
for(auto &i : E[x]) if(i.first!=p){
if(ck[i.first]) {
rpar[i.first] = r;
G[r].insert(i);
//cout << r << "->" << i.first << endl;
f(i.first,i.first,x);
}
else {
f(i.first,r,x);
}
}
}
pair<ll,ll> get(int x){
pair<ll,ll> ret = {0,sz[x]};
for(auto &i : G[x]) {
pair<ll,ll> res = get(i.first);
ret.second += res.second;
ret.first += res.first;
if(vis[i.first]) ret.first += res.second*i.second;
}
//cout << "!!" << x << ' ' << ret.first << ' ' << ret.second << endl;
return ret;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int n, m, k; cin >> n >> m >> k;
vector<vector<int>> edges;
for(int i = 0;i<m;i++){
int a,b,c; cin >> a >> b >> c;
edges.push_back({a,b,c});
}
vector<vector<int>> myedge;
for(int i = 0;i<k;i++){
int a,b; cin >> a >> b;
myedge.push_back({a,b,0});
}
for(int i = 1;i<=n;i++) {
cin >> A[i];
}
edges = build_mst(n, edges);
build(n, edges); dfs(1,0);
for(int i = 0;i<k;i++){
L[i] = lca(myedge[i][0],myedge[i][1]);
ck[L[i]] = 1;
//cout << L[i] << "~\n";
}
f(1,1,0);
//for(int i = 1;i<=n;i++) cout << sz[i] << ' '; cout << '\n';
ll ans = 0;
for(int i = 0;i<1<<k;i++){
vector<int> v;
for(int j = 0;j<k;j++) if(i>>j&1)
v.push_back(L[j]);
int no = 0;
for(int j : v){
if(vis[j]) no = 1;
vis[j] = 1;
}
if(no) {
for(int j : v) vis[j] = 0;
continue;
}
for(int j = 0;j<k;j++) if(i>>j&1){
int u = myedge[j][0], v = myedge[j][1];
if(h[u]>h[v]) swap(u,v);
int a = L[j];
G[rpar[a]].erase({a,P[a]});
G[rt[u]].insert({rt[v],P[a]});
}
ll cost = get(1).first;
for(int j = 0;j<k;j++) if(i>>j&1){
int u = myedge[j][0], v = myedge[j][1];
if(h[u]>h[v]) swap(u,v);
int a = L[j];
G[rpar[a]].insert({a,P[a]});
G[rt[u]].erase({rt[v],P[a]});
}
//cout << i << " :: ";
//cout << cost << endl;
ans = max(cost,ans);
for(int j : v) vis[j] = 0;
}
cout << ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
12380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
12380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
12380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
12380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
12380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
