제출 #223606

#제출 시각아이디문제언어결과실행 시간메모리
223606DavidDamianRoller Coaster Railroad (IOI16_railroad)C++11
64 / 100
137 ms15336 KiB
//#include "railroad.h" #include<bits/stdc++.h> using namespace std; typedef long long ll; ///Subtask 3 ///Disjoint Sets ///Sweep Line ///Just check if every time the sum is <=0 and all the special sections are connected ll cost[17][17]; ll memo[100005][17]; int link[200005]; int setSize[200005]; int Find(int u) { if(link[u]==u) return u; else return link[u]=Find(link[u]); } bool same(int u,int v) { return Find(u)==Find(v); } void unite(int u,int v) { u=Find(u); v=Find(v); if(u==v) return; if(setSize[v]>setSize[u]) swap(u,v); setSize[u]+=setSize[v]; link[v]=u; } void initDSU(int n) { for(int i=1;i<=n;i++){ setSize[i]=1; link[i]=i; } } struct event { int T; int op; int id; //Which special section bool operator<(const event& a) { if(T<a.T) return true; else{ if(T==a.T){ if(op<a.op) return true; else return false; } else return false; } } }; vector<event> timeline; long long plan_roller_coaster(vector<int> s, vector<int> t) { int n=s.size(); if(n<=16){ for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(j==i) continue; cost[i][j]=max(0,t[i]-s[j]); } } for(ll m=3;m<=(1<<n)-1;m++){ for(int i=0;i<n;i++){ if(m & (1<<i)){ if(m == (1<<i)){ memo[m][i]=0; continue; } memo[m][i]=LLONG_MAX; ll before_m=m-(1<<i); for(int j=0;j<n;j++){ if(j==i) continue; if(before_m & (1<<j)) memo[m][i]=min(memo[m][i],memo[before_m][j]+cost[j][i]); } } } } ll minimum=LLONG_MAX; for(int i=0;i<n;i++){ minimum=min(minimum,memo[(1<<n)-1][i]); } return minimum; } initDSU(n); for(int i=0;i<n;i++){ event e={s[i],+1,i+1}; timeline.push_back(e); e={t[i],-1,i+1}; timeline.push_back(e); } sort(timeline.begin(),timeline.end()); //Lines to the right are +1 //Lines to the left are -1 int balance=-1; //Because there is a line that goes from inf to 1 for(int i=0;i<2*n-1;i++){ balance+=timeline[i].op; if(balance<0){ unite(timeline[i].id,timeline[i+1].id); } else if(balance>0){ return 1; //Not possible with 0, we need to add tracks to slow down } } int root=Find(1); for(int i=1;i<=n;i++){ if(Find(i)!=root) return 1; //Not possible with 0, the sections are not fully connected } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...