読者です 読者をやめる 読者になる 読者になる

SRM627 Medium

Class:getMinimumInversions
問題概要:n(<=1000)頂点の無向木に辺を一本足したもの(多重辺,self loopなし)が与えられる.それぞれの頂点には整数V[i](1<=V[i]<=1000)が定まっている.K個の異なる点からなる木上の経路Cをうまく選んで、V[C_1],V[C_2],...V[C_K]の転倒数の最小を求めよ.Cが取れない場合は-1を返せ.
解答:
dfs適当にやって良い,InversionはBITでできる(Vの値の方で持つ)のだが、dfsの引数にvectorint bitとかを持って中でbit2を宣言してコピーして再帰とかするとコピーコストが大量にかかって死にます(死にました)
呼び出し時にvisited[i]=true,return時にvisited[i]=falseとすれば再帰がうまくいくことを知っているなら、同様にbitに足した分を減らして返せば良い(Marathonとかだと当たり前の工夫)

コード:

#include <iostream>
#include <vector>
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
using namespace std;
vector<int> G[1000],V,bit(1001);
bool visited[1000];
class GraphInversions{
	public:
	int mn=1e8;
	void add(int i,int x){
		while(i<=1000){
			bit[i]+=x;
			i+=(i&-i);
		}
	}
	int sum(int i){
		int s=0;
		while(i>0){
			s+=bit[i];
			i-=(i&-i);
		}
		return s;
	}
	void dfs(int x,int cnt,int ret){
		visited[x]=true;
		ret-=sum(V[x]);
		add(V[x],1);
//		cout << x << " " << cnt << " " << ret << endl;
//		rep(i,5) cout << visited[i] << " ";
//		cout << endl;
		if(cnt==1){
//			cout << ret << endl;
			mn=min(mn,ret);
			visited[x]=false;
			add(V[x],-1);
			return;
		}
		rep(i,G[x].size()){
			if(visited[G[x][i]]) continue;
			dfs(G[x][i],cnt-1,ret);
		}
		visited[x]=false;
		add(V[x],-1);
	}
	int getMinimumInversions(vector <int> A, vector <int> B, vector <int> Vc, int K){
		V=Vc;
		int n=A.size();
		rep(i,n){
			G[A[i]].pb(B[i]);
			G[B[i]].pb(A[i]);
		}
		rep(i,n) dfs(i,K,K*(K-1)/2);
		if(mn==1e8) mn=-1;
		return mn;
	}
};