Submission #14088

#	Time	Username	Problem	Language	Result	Execution time	Memory
14088		minsu	Toll (APIO13_toll)	C++14	56 / 100	2500 ms	26004 KiB

toll

#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; 
}

• Subtask 1: 16 / 16
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 0 / 22
• Subtask 5: 0 / 22