제출 #612532

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
612532		AugustinasJucas	즐거운 행로 (APIO20_fun)	C++14	26 / 100	92 ms	17088 KiB

fun

#include "fun.h"
#include <bits/stdc++.h>
using namespace std;

const int dydis = 1e5 + 10;

vector<int> gr[dydis];
int n;
bool rem[dydis] = {};
int dst[dydis] = {};
void dfs(int v, int came) {
    if(rem[v]) return;

    for(auto x : gr[v]) {
        if(x == came) continue;
        dst[x] = dst[v] + 1;
        //cout << "dst[" << v << "] = " << dst[v] << ", tai dst[" << x << "] = " << dst[x] << endl;
        dfs(x, v);
    }
}
int furthest (int a) {
   // cout << "ieskau atstumu nuo " << a << endl;
    dst[a] = 0;
    dfs(a, -1);
    int mx = 0; int sk = a;
    for(int i = 0; i < n; i++) {
        if(rem[i]) continue;
   //     cout << "dst[" << i << "] = " << dst[i] << endl;
        if(dst[i] > mx) {
            mx = dst[i];
            sk = i;
        }
    }
    return sk;
}
vector<int> createFunTour(int N, int Q) {
    n = N;

    for(int i = 0; i < n; i++) {
        for(int j = i+1; j < n; j++) {
            if(hoursRequired(i, j) == 1) {
                gr[i].push_back(j);
                gr[j].push_back(i);
            }
        }
    }

    vector<int> ret;
    int v = furthest(0);
    for(int i = 0; i < n; i++) {
       // cout << "i = " << i << ", v = " << v << endl;
        ret.push_back(v);
        int was = v;
        v = furthest(v);
        rem[was] = 1;
     //   cout << endl;
    }

    return ret;
}

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