Submission #676557

#	Time	Username	Problem	Language	Result	Execution time	Memory
676557		fatemetmhr	Fun Tour (APIO20_fun)	C++17	26 / 100	93 ms	21760 KiB

fun

// ~~ Be name khoda ~~

#include "fun.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define all(x) x.begin(), x.end()
#define pb     push_back
#define fi     first
#define se     second

const int maxn5 = 3e5 + 10;
const int lg    = 21;

int h[maxn5];
bool rem[maxn5];
vector <int> adj[maxn5], out;

void dfs(int v, int par){
    for(auto u : adj[v]) if(u != par && !rem[u]){
        h[u] = h[v] + 1;
        dfs(u, v);
    }
}

std::vector<int> createFunTour(int n, int Q) {
    for(int i = 0; i < n; i++) for(int j = i + 1; j < n; j++)
        if(hoursRequired(i, j) == 1){
            adj[i].pb(j);
            adj[j].pb(i);
        }
    h[0] = 0;
    dfs(0, -1);
    int v = 0;
    for(int i = 0; i < n; i++) if(h[v] < h[i])
        v = i;
    out.pb(v);
    for(int tt = 0; tt < n - 1; tt++){
        h[v] = 0;
        dfs(v, -1);
        rem[v] = true;
        for(int i = 0; i < n; i++) if(!rem[i] && h[i] > h[v])
            v = i;
        out.pb(v);
        //cout << h[v] << ' ';
    }
    //cout << endl;
    return out;
}

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