Submission #1225419

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225419		LucaIlie	Longest Trip (IOI23_longesttrip)	C++17	0 / 100	4 ms	404 KiB

longesttrip

#include "longesttrip.h"
#include <queue>
#include <stdio.h>

using namespace std;

const int MAX_N = 256;
int n;
int par[MAX_N], dist[MAX_N];
vector<int> adj[MAX_N];

vector<int> getLongestTrip(int s) {
    for (int u = 0; u < n; u++) {
        dist[u] = n;
        par[u] = -1;
    }

    queue<int> q;
    dist[s] = 0;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (int v: adj[u]) {
            if (dist[u] + 1 < dist[v]) {
                dist[v] = dist[u] + 1;
                par[v] = u;
                q.push(v);
            }
        }
    }

    int d = s;
    for (int v = 0; v < n; v++) {
        // printf("%d %d %d\n", s, v, dist[v]);
        if (dist[v] < n && dist[v] > dist[d])
            d = v;
    }

    vector<int> ans;
    // printf("%d %d\n", s, d);
    while (d != s) {
        ans.push_back(d);
        d = par[d];
    }
    ans.push_back(s);

    return ans;
}

vector<int> longest_trip(int N, int D) {
    n = N;
    for (int u = 0; u < n; u++) 
        adj[u].clear();

    for (int u = 0; u < n; u++) {
        for (int v = u + 1; v < n; v++)  {
            int x = are_connected({u}, {v});
            if (x) {
                adj[u].push_back(v);
                adj[v].push_back(u);
            }
        }
    }

    vector<int> ans;
    for (int s = 0; s < n; s++) {
        vector<int> cand = getLongestTrip(s);
        if (cand.size() > ans.size())
            ans = cand; 
    }

    return ans;
}

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