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