oj.uz

Submission #461319

# Submission time Handle Problem Language Result Execution time Memory
461319 2021-08-09T17:54:19 Z PedroBigMan Roller Coaster Railroad (IOI16_railroad) C++14
34 / 100
 662 ms 524292 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB n = 2
2 Correct 0 ms 204 KB n = 2
3 Correct 0 ms 204 KB n = 2
4 Correct 0 ms 204 KB n = 2
5 Correct 1 ms 204 KB n = 2
6 Correct 1 ms 204 KB n = 2
7 Correct 0 ms 288 KB n = 3
8 Correct 0 ms 204 KB n = 3
9 Correct 0 ms 204 KB n = 3
10 Correct 1 ms 332 KB n = 8
11 Correct 1 ms 332 KB n = 8
12 Correct 1 ms 332 KB n = 8
13 Correct 1 ms 332 KB n = 8
14 Correct 1 ms 332 KB n = 8
15 Correct 1 ms 332 KB n = 8
16 Correct 1 ms 332 KB n = 8
17 Correct 1 ms 332 KB n = 8
18 Correct 1 ms 332 KB n = 8
19 Correct 1 ms 204 KB n = 3
20 Correct 1 ms 204 KB n = 7
21 Correct 1 ms 332 KB n = 8
22 Correct 1 ms 332 KB n = 8
23 Correct 1 ms 332 KB n = 8
24 Correct 1 ms 332 KB n = 8
25 Correct 1 ms 332 KB n = 8

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB n = 2
2 Correct 0 ms 204 KB n = 2
3 Correct 0 ms 204 KB n = 2
4 Correct 0 ms 204 KB n = 2
5 Correct 1 ms 204 KB n = 2
6 Correct 1 ms 204 KB n = 2
7 Correct 0 ms 288 KB n = 3
8 Correct 0 ms 204 KB n = 3
9 Correct 0 ms 204 KB n = 3
10 Correct 1 ms 332 KB n = 8
11 Correct 1 ms 332 KB n = 8
12 Correct 1 ms 332 KB n = 8
13 Correct 1 ms 332 KB n = 8
14 Correct 1 ms 332 KB n = 8
15 Correct 1 ms 332 KB n = 8
16 Correct 1 ms 332 KB n = 8
17 Correct 1 ms 332 KB n = 8
18 Correct 1 ms 332 KB n = 8
19 Correct 1 ms 204 KB n = 3
20 Correct 1 ms 204 KB n = 7
21 Correct 1 ms 332 KB n = 8
22 Correct 1 ms 332 KB n = 8
23 Correct 1 ms 332 KB n = 8
24 Correct 1 ms 332 KB n = 8
25 Correct 1 ms 332 KB n = 8
26 Correct 1 ms 332 KB n = 8
27 Correct 1 ms 332 KB n = 8
28 Correct 1 ms 296 KB n = 8
29 Correct 109 ms 19284 KB n = 16
30 Correct 130 ms 19320 KB n = 16
31 Correct 107 ms 19208 KB n = 16
32 Correct 115 ms 19284 KB n = 16
33 Correct 123 ms 19200 KB n = 16
34 Correct 118 ms 19200 KB n = 16
35 Correct 121 ms 19300 KB n = 16
36 Correct 56 ms 9220 KB n = 15
37 Correct 1 ms 332 KB n = 8
38 Correct 138 ms 19304 KB n = 16
39 Correct 132 ms 19200 KB n = 16
40 Correct 1 ms 332 KB n = 9
41 Correct 107 ms 19200 KB n = 16
42 Correct 116 ms 19284 KB n = 16
43 Correct 111 ms 19200 KB n = 16
44 Correct 1 ms 332 KB n = 9
45 Correct 55 ms 9280 KB n = 15
46 Correct 123 ms 19284 KB n = 16
47 Correct 130 ms 19316 KB n = 16
48 Correct 125 ms 19200 KB n = 16

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 662 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB n = 2
2 Correct 0 ms 204 KB n = 2
3 Correct 0 ms 204 KB n = 2
4 Correct 0 ms 204 KB n = 2
5 Correct 1 ms 204 KB n = 2
6 Correct 1 ms 204 KB n = 2
7 Correct 0 ms 288 KB n = 3
8 Correct 0 ms 204 KB n = 3
9 Correct 0 ms 204 KB n = 3
10 Correct 1 ms 332 KB n = 8
11 Correct 1 ms 332 KB n = 8
12 Correct 1 ms 332 KB n = 8
13 Correct 1 ms 332 KB n = 8
14 Correct 1 ms 332 KB n = 8
15 Correct 1 ms 332 KB n = 8
16 Correct 1 ms 332 KB n = 8
17 Correct 1 ms 332 KB n = 8
18 Correct 1 ms 332 KB n = 8
19 Correct 1 ms 204 KB n = 3
20 Correct 1 ms 204 KB n = 7
21 Correct 1 ms 332 KB n = 8
22 Correct 1 ms 332 KB n = 8
23 Correct 1 ms 332 KB n = 8
24 Correct 1 ms 332 KB n = 8
25 Correct 1 ms 332 KB n = 8
26 Correct 1 ms 332 KB n = 8
27 Correct 1 ms 332 KB n = 8
28 Correct 1 ms 296 KB n = 8
29 Correct 109 ms 19284 KB n = 16
30 Correct 130 ms 19320 KB n = 16
31 Correct 107 ms 19208 KB n = 16
32 Correct 115 ms 19284 KB n = 16
33 Correct 123 ms 19200 KB n = 16
34 Correct 118 ms 19200 KB n = 16
35 Correct 121 ms 19300 KB n = 16
36 Correct 56 ms 9220 KB n = 15
37 Correct 1 ms 332 KB n = 8
38 Correct 138 ms 19304 KB n = 16
39 Correct 132 ms 19200 KB n = 16
40 Correct 1 ms 332 KB n = 9
41 Correct 107 ms 19200 KB n = 16
42 Correct 116 ms 19284 KB n = 16
43 Correct 111 ms 19200 KB n = 16
44 Correct 1 ms 332 KB n = 9
45 Correct 55 ms 9280 KB n = 15
46 Correct 123 ms 19284 KB n = 16
47 Correct 130 ms 19316 KB n = 16
48 Correct 125 ms 19200 KB n = 16
49 Runtime error 662 ms 524292 KB Execution killed with signal 9
50 Halted 0 ms 0 KB -