Submission #1132423

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132423		omsincoconut	Longest Trip (IOI23_longesttrip)	C++20	5 / 100	329 ms	784 KiB

longesttrip

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

using namespace std;

const int MAXN = 256;

vector<int> edge[MAXN];
int dp[MAXN];
void dfs(vector<int> &ccomp, int u) {
    ccomp.push_back(u);
    for (int v : edge[u]) {
        if (dp[v] == -1) {
            dp[v] = dp[u] + 1;
            dfs(ccomp, v);
        }
    }
}

vector<int> longest_trip(int N, int D) {
    for (int i = 0; i < N; i++) {
        edge[i].clear();
        dp[i] = -1;
    }

    bool edge_bool[N][N];

    for (int i = 0; i < N; i++) {
        for (int j = i+1; j < N; j++) {
            if (are_connected({i}, {j})) {
                edge[i].push_back(j);
                edge[j].push_back(i);
                edge_bool[i][j] = edge_bool[j][i] = true;
            } else edge_bool[i][j] = edge_bool[j][i] = false;
        }
    }

    for (int i = 0; i < N; i++) sort(edge[i].begin(), edge[i].end());

    vector<vector<int>> comp;
    for (int i = 0; i < N; i++) {
        if (dp[i] != -1) continue;
        dp[i] = 0;
        vector<int> ccomp;
        dfs(ccomp, i);
        comp.push_back(ccomp);
    }

    if (comp.size() > 1) {
        if (comp[0].size() < comp[1].size()) swap(comp[0], comp[1]);
        return comp[0];
    }

    int lastfail = -1;
    for (int i = 0; i < N-1; i++) {
        if (!edge_bool[comp[0][i]][comp[0][i+1]]) {
            lastfail = i;
            break;
        }
    }

    if (lastfail == -1) return comp[0];
    while (comp[0].size() > lastfail+1) comp[0].pop_back();
    return comp[0];
}

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