Submission #279999

#TimeUsernameProblemLanguageResultExecution timeMemory
279999eohomegrownappsRoller Coaster Railroad (IOI16_railroad)C++14
0 / 100
317 ms59836 KiB
#include "railroad.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; ll INF = 1e18; vector<vector<ll>> adjlist; vector<ll> comind; vector<bool> visited; void dfs(ll ind, ll com){ //cout<<ind<<' '<<com<<'\n'; visited[ind]=true; comind[ind]=com; for (ll i : adjlist[ind]){ if (!visited[i]){ dfs(i,com); } } } struct UFDS{ vector<ll> parent; ll n; UFDS(ll _n){ n=_n; parent.resize(n); for (ll i = 0; i<n; i++){ parent[i]=i; } } ll root(ll x){ if (x==parent[x]){return x;} return parent[x]=root(parent[x]); } void connect(ll a, ll b){ ll ra = root(a); ll rb = root(b); if (ra!=rb){ parent[ra]=rb; } } bool connected(ll a, ll b){ return root(a)==root(b); } }; long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) { vector<ll> ind2coord; for (ll i : s){ ind2coord.push_back(i); } for (ll i : t){ ind2coord.push_back(i); } ind2coord.push_back(INF); ind2coord.push_back(1); sort(ind2coord.begin(),ind2coord.end()); ind2coord.erase(unique(ind2coord.begin(),ind2coord.end()),ind2coord.end()); s.push_back(INF); t.push_back(1); ll n = ind2coord.size(); for (ll i = 0; i<s.size(); i++){ s[i]=lower_bound(ind2coord.begin(),ind2coord.end(),s[i])-ind2coord.begin(); t[i]=lower_bound(ind2coord.begin(),ind2coord.end(),t[i])-ind2coord.begin(); } //start at 1, end at 1 ll ans = 0; vector<ll> edgedelta(n); for (ll i = 0; i<s.size(); i++){ edgedelta[s[i]]++; edgedelta[t[i]]--; } ll curdelta = 0; for (ll i = 0; i<n-1; i++){ curdelta+=edgedelta[i]; if (curdelta<0){ //need to go ltr / speed up (fine) s.push_back(i); t.push_back(i+1); } if (curdelta>0){ //need to go rtl / slow down (not fine) ans+=curdelta*(ind2coord[i+1]-ind2coord[i]); s.push_back(i+1); t.push_back(i); } } //make connected components adjlist.resize(n); visited.resize(n); comind.resize(n); for (ll i = 0; i<s.size(); i++){ adjlist[s[i]].push_back(t[i]); } ll cptr = 0; for (ll i = 0; i<n; i++){ if (!visited[i]){ dfs(i,cptr); cptr++; } } vector<pair<ll,pair<ll,ll>>> edges; for (ll i = 0; i<n-1; i++){ if (comind[i]!=comind[i+1]){ edges.push_back({ind2coord[i+1]-ind2coord[i],{comind[i],comind[i+1]}}); } } sort(edges.begin(), edges.end()); UFDS u(n); for (auto e : edges){ // are these connected? if (u.connected(e.second.first, e.second.second)){ continue; } ans+=e.first; u.connect(e.second.first, e.second.second); } return ans; }

Compilation message (stderr)

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:68:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for (ll i = 0; i<s.size(); i++){
      |                    ~^~~~~~~~~
railroad.cpp:77:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for (ll i = 0; i<s.size(); i++){
      |                    ~^~~~~~~~~
railroad.cpp:101:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     for (ll i = 0; i<s.size(); i++){
      |                    ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...