Submission #735468

#	Time	Username	Problem	Language	Result	Execution time	Memory
735468		Nahian9696	Fun Tour (APIO20_fun)	C++17	10 / 100	2064 ms	1236 KiB

fun

#include "fun.h"

#include <iostream>
#include <iomanip>
#include <chrono>

#include <cmath>
#include <cstring>
#include <algorithm>


#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <utility>
#include <string>
#include <vector>
#include <bitset>



using std::min;
using std::max;
using std::sort;
using std::swap;
using std::fixed;
using std::to_string;
using std::make_pair;
using std::upper_bound;
using std::lower_bound;
using std::setprecision;

using std::cin;
using std::cout;

using std::set;
using std::map;
using std::list;
using std::pair;
using std::less;
using std::tuple;
using std::stack;
using std::queue;
using std::deque;
using std::string;
using std::vector;
using std::bitset;
using std::greater;
using std::priority_queue;





typedef long double                         ld;
typedef unsigned                            ui;
typedef long long                           lli;
typedef unsigned long long                  ulli;
typedef vector<int32_t>                     vi;
typedef vector<ld>                          vld;
typedef vector<ui>                          vui;
typedef vector<lli>                         vlli;
typedef vector<ulli>                        vulli;
typedef list<int32_t>                       lsi;
typedef list<ld>                            lsld;
typedef list<ui>                            lsui;
typedef list<lli>                           lslli;
typedef list<ulli>                          lsulli;
typedef set<int32_t>                        si;
typedef set<ld>                             sld;
typedef set<ui>                             sui;
typedef set<lli>                            slli;
typedef set<ulli>                           sulli;

typedef pair<int32_t, int32_t>              pii;
typedef pair<lli, lli>                      pll;



// #define int                                 int64_t

#define endl                                "\n"
#define inp(n)                              int n; cin >> n
#define Inp(n)                              lli n; cin >> n
#define inpstr(s)                           string s; cin >> s
#define inp2(a,b)                           int a,b; cin >> a >> b
#define Inp2(a,b)                           lli a,b; cin >> a >> b
#define inparr(arr,n)                       int arr[n]; f0(t_ind, n) cin >> arr[t_ind]
#define Inparr(arr,n)                       lli arr[n]; f0(t_ind, n) cin >> arr[t_ind]

#define f0(i,n)                             for(int32_t i = 0; i <  (n); i++)
#define f1(i,n)                             for(int32_t i = 1; i <= (n); i++)
#define rep0(i,l,r)                         for(int32_t i=(l); i <  (r); i++)
#define rep1(i,l,r)                         for(int32_t i=(l); i <= (r); i++)

#define testIn                              cin >> test
#define tests                               for(int32_t testNo=1; testNo <= (test); testNo++)

#define all(x)                              (x).begin(), (x).end()
#define rall(x)                             (x).rbegin(), (x).rend()
#define asrt(v)                             sort(all(v))
#define dsrt(v)                             sort(rall(v))
#define revStr(str)                         string(rall(str))
#define len(a)                              ((int64_t)(a).size())
#define front_zero(n)                       __builtin_clzll(n)
#define back_zero(n)                        __builtin_ctzll(n)
#define total_one(n)                        __builtin_popcountll(n)
#define lcm(a, b)                           (((a)*(b))/gcd(a,b))
#define mem(a, b)                           memset(a, b, sizeof(a))

#define pb                                  push_back
#define pf                                  push_front
#define mp                                  make_pair
#define ff                                  first
#define ss                                  second

#define yes                                 cout << "yes" << endl
#define no                                  cout << "no" << endl
#define Yes                                 cout << "Yes" << endl
#define No                                  cout << "No" << endl
#define YES                                 cout << "YES" << endl
#define NO                                  cout << "NO" << endl
#define finish                              return 0
#define clean                               fflush(stdout)

#define Inf                                 (int32_t)(1e9)
#define INF                                 (lli)(1e18)
#define Eps                                 (ld)(1e-9)
#define EPS                                 (ld)(1e-18)
#define PI                                  (ld)(3.141592653589793238462643383279502884197169L)
#define MOD                                 (int32_t)(1e9+7)
#define MXN                                 (int32_t)(1e5+7)


// vector<pii> grph[505];
int mat[505][505];
vi path;
bool vis[505] = {0};
int len = 0, n;

bool bfs(int u) {
    if(len == 1) {
        f0(i, n) {
            if(!vis[i]) {
                vis[i] = true;
                path.pb(i);
                len++;
                bool ans = bfs(i);
                if(ans) return true;
                len--;
                path.pop_back();
                vis[i] = false;
            }
        }
        return false;
    } else if (len == n) {
        return true;
    } else {
        int prevdis = mat[path[len-1]][path[len-2]];
        f0(i, n) {
            if(!vis[i]) {
                if(mat[path[len-1]][i] <= prevdis) {
                    vis[i] = true;
                    path.pb(i);
                    len++;
                    bool ans = bfs(i);
                    if(ans) return true;
                    len--;
                    path.pop_back();
                    vis[i] = false;
                }
            }
        }
        return false;
    }
}



std::vector<int> createFunTour(int N, int Q) {
    n = N;
    f0(i, N) {
        for(int j = i+1; j < N; j++) {
            int H = hoursRequired(i, j);
            mat[i][j] = H, mat[j][i] = H;
            // grph[i].pb({j, H});
            // grph[j].pb({i, H});
        }
    }

    f0(cur, n) {
        vis[cur] = true;
        path.pb(cur);
        len++;
        bool ya = bfs(cur);
        if(ya) return path;
        len--;
        path.pop_back();
        vis[cur] = false;
    }
    




    int H = hoursRequired(0, N - 1);
    int A = attractionsBehind(0, N - 1);
    return std::vector<int>(N);
}

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:209:9: warning: unused variable 'H' [-Wunused-variable]
  209 |     int H = hoursRequired(0, N - 1);
      |         ^
fun.cpp:210:9: warning: unused variable 'A' [-Wunused-variable]
  210 |     int A = attractionsBehind(0, N - 1);
      |         ^

• Subtask 1: 10 / 10
• Subtask 2: 0 / 16
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 34