Submission #804608

#TimeUsernameProblemLanguageResultExecution timeMemory
804608I_Love_EliskaM_Roller Coaster Railroad (IOI16_railroad)C++14
64 / 100
489 ms50952 KiB
#include "railroad.h" #include <bits/stdc++.h> using namespace std; #define forn(i,n) for(int i=0;i<n;++i) #define pb push_back #define all(x) x.begin(), x.end() using ll = long long; #define pi pair<int,int> #define f first #define s second struct DSU { vector<int> p,sz; DSU(int n) { forn(i,n) p.pb(i), sz.pb(1); } int get(int u) { return p[u]==u?u:get(p[u]); } void uni(int u, int v) { u=get(u),v=get(v); if (u==v) return; if (sz[u]<sz[v]) swap(u,v); sz[u]+=sz[v]; p[v]=u; } }; ll dp[1<<16][20]; bool foo(int a, int b) { return __builtin_popcount(a) < __builtin_popcount(b); } ll scuza(vector<int> s, vector<int> t) { int n=s.size(); s.pb(-1); t.pb(0); vector<int> b; forn(i,1<<n) b.pb(i); sort(all(b),foo); forn(i,n+1) forn(j,1<<n) dp[j][i]=1e18; dp[0][n]=0; for(auto&m:b) { forn(i,n+1) { if (m) if (!(m&(1<<i))) continue; forn(j,n) { if (m&(1<<j)) continue; dp[m|(1<<j)][j]=min(dp[m|(1<<j)][j],dp[m][i] + max(t[i]-s[j],0)); } } } ll ans=1e18; forn(i,n) ans=min(ans,dp[(1<<n)-1][i]); return ans; } ll plan_roller_coaster(vector<int> s, vector<int> t) { int n=s.size(); if (n<=16) return scuza(s,t); s.pb(1e9+7); t.pb(-1); ++n; int m=0; set<int> st; forn(i,n) st.insert(s[i]), st.insert(t[i]); map<int,int> c; for(auto&x:st) c[x]=m++; vector<int> pr(m); forn(i,n) s[i]=c[s[i]], t[i]=c[t[i]]; DSU dsu(m); forn(i,n) { pr[t[i]]++; pr[s[i]]--; dsu.uni(s[i],t[i]); } for(int i=1; i<m; ++i) pr[i]+=pr[i-1]; forn(i,m) { if (pr[i]<0) return 1; if (pr[i]>0) dsu.uni(i,i+1); } int ans=1; forn(i,n) ans&=dsu.get(i)==dsu.get(0); return !ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...