Submission #1235886

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235886		madamadam3	가장 긴 여행 (IOI23_longesttrip)	C++20	5 / 100	4 ms	408 KiB

longesttrip

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

using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;

void get_distances(int u, int n, vvi &adj, vi &dist, vi &par) {
    dist.assign(n, 0);
    par.assign(n, -1);

    queue<int> q;
    vector<bool> seen(n, false);
    seen[u] = true;

    q.push(u);
    while (!q.empty()) {
        int cur = q.front();
        q.pop();

        for (auto v : adj[cur]) {
            if (seen[v]) continue;
            seen[v] = true;
            dist[v] = 1 + dist[cur];
            par[v] = cur;
            q.push(v);
        }
    }
}

vi longest_trip(int N, int D) {
    int n = N, d = D;

    if (d >= 2) {
        vi ans(n); iota(ans.begin(), ans.end(), 0);
        return ans; 
    }

    vvi adj(n, vi());
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            bool edge = are_connected(vi({i}), vi({j}));
            if (!edge) continue;
            adj[i].push_back(j);
            adj[j].push_back(i);
        }
    }

    int bd = -1; vi best;
    for (int i = 0; i < n; i++) {
        vi dist, par;
        get_distances(i, n, adj, dist, par);

        int furthest = 0; for (int j = 1; j < n; j++) if (dist[j] > dist[furthest]) furthest = j;
        int length = dist[furthest];
        if (length <= bd) continue;

        vi ans;
        while (furthest != -1) {
            ans.push_back(furthest);
            furthest = par[furthest];
        }

        bd = length;
        best = ans;
    }

    return best;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 25
• Subtask 4: 0 / 60