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

SRM629

SRM 629: o-- +0/-0 +217.48 (140th)

Med
全然間に合わんかった…実装がむずい
でもよく考えるとn<=1000なのにO(n)で書いちゃったけどもうちょっとサボってO(n^2)で書くと楽だったのかなあ(そんなに変わらない気もするけど)

#include <iostream>
#include <vector>
#include <algorithm>
#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
#define show(x) cout << #x << " " << x << endl
#define miz(x,y) x=min(x,y)
using namespace std;
struct edge{int to,id,one,two;};
vector<edge> G[1000];
int dp[1001][2],inf=1e8;
bool visited[1000];
vector<int> seq;
void dfs(int v,int p){
	if(visited[v]) return;
	visited[v]=true;
	seq.pb(v);
	int nx;
	rep(i,2) if(G[v][i].to!=p) {nx=G[v][i].to; break;}
	dfs(nx,v);
}
void dpp(int m){
	rep(j,m-1){
		int v=seq[j+1],nxt=seq[(j+2)%m];
		//show(v);
		//show(nxt);
		edge e;
		rep(kk,2) if(G[v][kk].to==nxt) e=G[v][kk];
		rep(kk,2) dp[j+1][kk]=inf;
		if(v==e.id) miz(dp[j+1][0],dp[j][0]+e.one);
		miz(dp[j+1][1],dp[j][0]+e.two);
		miz(dp[j+1][0],dp[j][1]);
		if(nxt==e.id) miz(dp[j+1][1],dp[j][1]+e.one);
		miz(dp[j+1][1],dp[j][1]+e.two);
		//show(dp[j+1][0]);
		//show(dp[j+1][1]);
	}
}
class CandyCollection{
	public:
	int solve(vector <int> t1, vector <int> n1, vector <int> t2, vector <int> n2){
		int n=t1.size(),ans=0;
		rep(i,n){
			int one=min(n1[i],n2[i])+1,two=max(n1[i],n2[i])+1,id=(n1[i]>n2[i] ? t1[i] : t2[i]);
			G[t1[i]].pb({t2[i],id,one,two});
			G[t2[i]].pb({t1[i],id,one,two});
		}
		rep(i,n){
			if(visited[i]) continue;
			seq.clear();
			dfs(i,-1);
			int m=seq.size();
/*			cout << "seq  ";
			rep(i,m) cout << seq[i] << " ";
			cout << endl;*/
			int mn=inf;
			dp[0][1]=0;
			dpp(m);
			//show(min(dp[m-1][0],dp[m-1][1])+G[i][0].two);
			miz(mn,min(dp[m-1][0],dp[m-1][1])+G[i][0].two);
			if(G[i][0].id==i){
				dp[0][1]=inf;
				dpp(m);
				//show(min(dp[m-1][0],dp[m-1][1])+G[i][0].one);
				miz(mn,min(dp[m-1][0],dp[m-1][1])+G[i][0].one);
			}
			reverse(seq.begin()+1,seq.end());
/*			cout << "seq  ";
			rep(i,m) cout << seq[i] << " ";
			cout << endl;*/
			dp[0][1]=0;
			dpp(m);
			//show(min(dp[m-1][0],dp[m-1][1])+G[i][1].two);
			miz(mn,min(dp[m-1][0],dp[m-1][1])+G[i][1].two);
			if(G[i][1].id==i){
				dp[0][1]=inf;
				dpp(m);
				//show(min(dp[m-1][0],dp[m-1][1])+G[i][1].one);
				miz(mn,min(dp[m-1][0],dp[m-1][1])+G[i][1].one);
			}
			ans+=mn;
		}
		return ans;
	}
};