Submission #461319

#	Time	Username	Problem	Language	Result	Execution time	Memory
461319		PedroBigMan	Roller Coaster Railroad (IOI16_railroad)	C++14	34 / 100	662 ms	524292 KiB

railroad

#include "railroad.h"
/*
Author of all code: Pedro BIGMAN Dias
Last edit: 15/02/2021
*/
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 50000000000000000LL
#define EPS 0.00000001
#define pi 3.14159
ll mod=1000000007LL;

template<class A=ll> 
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}

template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}} 

vector<ll> s,t; ll N;

class WDiGraph
{
    public:
    ll N;
    vector<vector<pl> > adj; 
	vector<vector<pl> > dpH; //for Hamiltonian BF first part is - -3 if not decided, -2 if not possible, -1 if single node (v==1<<x), else last visited node, second part is minimum weight of such path
    
    WDiGraph(vector<vector<pl> > ad)
    {
        adj=ad; N=adj.size();
    }
	
	ll Hamiltonian() //least-cost Hamiltonian Path
    {
        ll vv = (1LL<<N)-1LL; 
		vector<pl> xx; REP(i,0,N) {xx.pb({-3LL,INF});} REP(i,0,vv+1LL) {dpH.pb(xx);}
		ll E=-1; ll minval=INF;
        REP(i,0,N) 
        {
            if(f(vv,i).ff>=-1LL && f(vv,i).ss<minval) {E=i; minval=f(vv,i).ss;}
        }
		return minval;
    }
	
	pl f(ll v, ll x)
	{
		if(dpH[v][x].ff!=-3LL) {return dpH[v][x];}
        if(v==(1LL<<x)) {dpH[v][x]={-1LL,0LL}; return dpH[v][x];}
		v-=(1LL<<x); ll node; ll minval = INF;
		REP(i,0,adj[x].size())
		{
			node=adj[x][i].ff;
			if((v & (1LL<<node))==0LL) {continue;}
			if(f(v,node).ff>=-1LL && f(v,node).ss + adj[x][i].ss <minval) 
			{
				minval=f(v,node).ss + adj[x][i].ss;
				dpH[v+(1LL<<x)][x]={node,f(v,node).ss+adj[x][i].ss};
			}
		}
		if(minval<INF) {return dpH[v+(1LL<<x)][x];}
        dpH[v][x]={-2LL,INF}; return dpH[v][x];
	}
};

ll plan_roller_coaster(vector<int> sss, vector<int> ttt) 
{
	N=sss.size(); REP(i,0,N) {s.pb((ll) sss[i]); t.pb((ll) ttt[i]);}
	vector<pl> xx; vector<vector<pl> > adj; REP(i,0,N) {adj.pb(xx);}
	REP(i,0,N)
	{
		REP(j,0,N)
		{
			if(i==j) {continue;}
			adj[i].pb({j,max(0LL,t[i]-s[j])});
		}		
	}
	WDiGraph G(adj);
	return G.Hamiltonian();
}

Compilation message (stderr)

railroad.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("O3")
      | 
railroad.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("unroll-loops")
      | 
railroad.cpp: In member function 'll WDiGraph::Hamiltonian()':
railroad.cpp:66:6: warning: variable 'E' set but not used [-Wunused-but-set-variable]
   66 |   ll E=-1; ll minval=INF;
      |      ^

• Subtask 1: 11 / 11
• Subtask 2: 23 / 23
• Subtask 3: 0 / 30
• Subtask 4: 0 / 36