제출 #1161647

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1161647		Aviansh	즐거운 행로 (APIO20_fun)	C++20	26 / 100	54 ms	15548 KiB

fun

#include "fun.h"

#include <bits/stdc++.h>

using namespace std;
int f;
void dfs(int st, vector<int>(&g)[], int p, int dep, int d[], bool rem[]){
    d[st]=dep;
    if(d[f]<dep){
        f=st;
    }
    for(int i : g[st]){
        if(i==p||rem[i])
            continue;
        dfs(i,g,st,dep+1,d,rem);
    }
}

int findFarthest(int x, vector<int>(&g)[], bool rem[], int n){
    f=x;
    int d[n];
    fill(d,d+n,0);
    dfs(x,g,-1,0,d,rem);
    return f;
}

vector<int> createFunTour(int n, int q) {
  //  int H = hoursRequired(0, N - 1);
    //int A = attractionsBehind(0, N - 1);
    vector<int>g[n];
    vector<int>ans;
    for(int i = 0;i<n;i++){
        for(int j = i+1;j<n;j++){
            if(hoursRequired(i,j)==1){
                g[i].push_back(j);
                g[j].push_back(i);
            }
        }
    }
    //graph acquired
    bool rem[n];
    fill(rem,rem+n,0);
    int x = findFarthest(0,g,rem, n);
    for(int i = 0;i<n;i++){
        //i just for counting
        ans.push_back(x);
        rem[x]=1;
        x=findFarthest(x,g,rem, n);
    }
    return ans;
}

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