Submission #941951

#TimeUsernameProblemLanguageResultExecution timeMemory
941951LalicRoller Coaster Railroad (IOI16_railroad)C++17
Compilation error
0 ms0 KiB
#include "railroad.h" #include <bits/stdc++.h> using namespace std; #define pb push_back #define fi first #define se second #define all(x) x.begin(), x.end() #define allr(x) x.rbegin(), x.rend() #define mp make_pair typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXN = 1e5+10; const int INF = 0x3f3f3f3f; const ll LINF = 0x3f3f3f3f3f3f3f3f; const int MOD = 1e9+7; long long solve(vector<int> s, vector<int> t){ int n=(int)s.size(); for(int i=0;i<n;i++) for(int j=0;j<(1<<n);j++) dp[i][j]=LINF; dp[0][0]=0; for(int i=1;i<(1<<n);i++){ for(int j=0;j<n;j++){ if(!(i&(1<<j))) continue; int curr=(i^(1<<j)); if(curr==0) dp[j][i]=0; else{ for(int k=0;k<n;k++){ if(!(curr&(1<<k))) continue; dp[j][i]=min(dp[j][i], dp[k][curr]+max((ll)t[k]-(ll)s[j], 0ll)); } } } } ll ans=LINF; for(int i=0;i<n;i++) ans=min(ans, dp[i][(1<<n)-1]); return ans; } long long plan_roller_coaster(vector<int> s, vector<int> t) { if((int)s.size()<=16) return solve(s, t); vector<int> arr; for(auto u : s) arr.pb(u); for(auto u : t) arr.pb(u); sort(all(arr)); arr.erase(unique(all(arr)), arr.end()); int n=(int)arr.size(); map<int, int> mp; vector<int> g(n, 0); for(int i=0;i<n;i++) mp[arr[i]]=i; vector<vector<int>> adj(n); adj[n-1].pb(0); g[n-1]++; g[0]--; for(int i=0;i<(int)s.size();i++){ g[mp[s[i]]]++; g[mp[t[i]]]--; adj[mp[s[i]]].pb(mp[t[i]]); } for(int i=0;i<n-1;i++){ if(g[i]>0) return 1; if(g[i]<0) adj[i].pb(i+1), g[i+1]+=g[i], g[i]=0; } if(g[n-1]!=0) return 1; vector<int> cmp(n, 0); cmp[0]=1; queue<int> q; q.push(0); while(!q.empty()){ int curr=q.front(); q.pop(); for(auto u : adj[curr]){ if(!cmp[u]){ cmp[u]=1; q.push(u); } } } for(int i=0;i<n;i++) if(!cmp[i]) return 1; return 0; }

Compilation message (stderr)

railroad.cpp: In function 'long long int solve(std::vector<int>, std::vector<int>)':
railroad.cpp:26:4: error: 'dp' was not declared in this scope; did you mean 'mp'?
   26 |    dp[i][j]=LINF;
      |    ^~
      |    mp
railroad.cpp:28:2: error: 'dp' was not declared in this scope; did you mean 'mp'?
   28 |  dp[0][0]=0;
      |  ^~
      |  mp