| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 14088 |
2015-04-30T08:40:07 Z |
minsu |
Toll (APIO13_toll) |
C++14 |
|
2500 ms |
26004 KB |
#include <iostream>
#include <stack>
#include <algorithm>
#include <cstdio>
#include <utility>
#define F first
#define S second
using namespace std;
typedef pair<int,int> ii;
typedef pair<int, ii> ip;
const int MAXN=1e5+10;
const int MAXM=3e5+10;
const int MAXK=20;
int N,M,K;
vector<ip> path; vector<ii> npath; vector<int> val;
struct mstnode{
int p, c, t; // parent, cost, type=0 default 1 Mr G's
mstnode(int _p=-1, int _c=0, int _t=0) : p(_p), c(_c), t(_t) {}
};
vector<mstnode> mst;
namespace uf{
int par[MAXN];
int ranks[MAXN];
void init(int n){
for(int i=0;i<n;i++){
par[i]=i;
ranks[i]=0;
}
}
int find(int x){
if(par[x]==x)
return x;
else
return par[x]=find(par[x]);
}
void unite(int x,int y){
x=find(x);
y=find(y);
if(x==y) return;
if(ranks[x]<ranks[y])
par[x]=y;
else{
par[y]=x;
if(ranks[x]==ranks[y]) ranks[x]++;
}
}
bool same(int x, int y){
return find(x)==find(y);
}
}
long long ans=0;
// for internal nodes, O(N) : O(2^K*N)
// for leaf nodes, O(N) : O(2^K*N)
// overall time complexity O(2^K*N)
void solve(int k){
if(k==K){
// caclculate revenue function
long long nowans=0;
vector< vector<int> > child(N);
for(int i=1;i<N;i++) child[mst[i].p].push_back(i);
stack<int> st; st.push(0); long long profit=0;
while(!st.empty()){
int now=st.top();
if(child[now].empty()){
if(mst[now].t) profit-=mst[now].c;
st.pop();
}else{
int nxt=child[now].back();
child[now].pop_back(); st.push(nxt);
if(mst[nxt].t) { profit+=mst[nxt].c; }
nowans+=profit*val[nxt];
}
}
// for(int i=1;i<N;i++) cout<<mst[i].p<<"("<<mst[i].c<<")"; cout<<nowans<<"\n";
//cout<<nowans<<"\n";
ans=max(ans, nowans);
return;
}
solve(k+1);
vector<mstnode> mstbackup(mst);
// get cycle : path to LCA
int e1=npath[k].F, e2=npath[k].S; vector<int> ep[2];
for(int i=e1;i!=-1;i=mst[i].p) ep[0].push_back(i);
for(int i=e2;i!=-1;i=mst[i].p) ep[1].push_back(i);
reverse(ep[0].begin(), ep[0].end()); reverse(ep[1].begin(), ep[1].end());
vector<int> upd; int maxi=0, maxp1, maxp2, lca;
for(lca=0;lca<ep[0].size() && lca<ep[1].size() && ep[0][lca]==ep[1][lca];lca++);
for(int k=0;k<2;k++){
for(int i=lca;i<ep[k].size();i++){
int now=ep[k][i];
if(mst[now].t==1) upd.push_back(now);
else if(mst[now].c>maxi){
maxi=mst[now].c;
maxp1=k; maxp2=i;
}
}
}
if(maxi==0) return; // no default nodes in cycle!
for(auto i : upd) mst[i].c=min(mst[i].c, maxi);
for(int i=maxp2;i<(int)ep[maxp1].size()-1;i++){
int now=ep[maxp1][i], nxt=ep[maxp1][i+1];
swap(mst[now], mst[nxt]); mst[now].p=nxt;
} int last=ep[maxp1].back();
mst[last].p=(last==e1)? e2 : e1;
mst[last].c=maxi;
mst[last].t=1;
solve(k+1);
mstbackup.swap(mst);
}
vector< vector<ii> > tempp;
int main() {
scanf("%d%d%d",&N,&M,&K);
val.resize(N); path.resize(M); npath.resize(K); tempp.resize(N); mst.resize(N);
for(int i=0;i<M;i++){
scanf("%d%d%d",&path[i].S.F,&path[i].S.S,&path[i].F);
path[i].S.F--; path[i].S.S--;
}
for(int i=0;i<K;i++){
scanf("%d%d",&npath[i].F,&npath[i].S);
npath[i].F--; npath[i].S--;
}
for(int i=0;i<N;i++) scanf("%d",&val[i]);
sort(path.begin(), path.end()); uf::init(N);
int chosen=0;
for(int i=0;i<M;i++){
int st=path[i].S.F, en=path[i].S.S, cc=path[i].F;
if(!uf::same(st,en)){
uf::unite(st,en);
tempp[st].push_back(ii(en, cc));
tempp[en].push_back(ii(st, cc));
chosen++; if(chosen==N-1) break;
}
}
{
vector<int> bfs, visit(N);
bfs.push_back(0); visit[0]=1;
for(int i=0;i<bfs.size();i++){
for(auto& it : tempp[bfs[i]])
if(visit[it.F]==0){
mst[it.F]=mstnode(bfs[i], it.S, 0);
visit[it.F]=1;
bfs.push_back(it.F);
}
}
} solve(0);
cout<<ans;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2512 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2512 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
106 ms |
2788 KB |
Output is correct |
| 2 |
Correct |
54 ms |
2772 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2500 ms |
26004 KB |
Program timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
