Submission #1218014

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218014		qwusha	Longest Trip (IOI23_longesttrip)	C++20	5 / 100	329 ms	688 KiB

longesttrip

#include <bits/stdc++.h>
#include "longesttrip.h"
using namespace std;
#define fi first
#define se second
typedef long long ll;
typedef long double ld;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
ll inf = 1e18;


vector<int> s;
vector<int> used;
int n;
int endik = -1;
vector<vector<int>> adj;

/*
bool are_connected(vector<int> a, vector<int> b) {
    cout << a[0] << ' ' << b[0] << endl;
    int x;
    cin >> x;
    return (x == 1);
}
 */

void dfs(int v) {
    s.push_back(v);
    used[v] = 1;
    bool ok = 0;
    for (int i = 0; i < n; i++) {
        if (used[i]) {
            continue;
        }
        if (adj[v][i] == 1) {
            dfs(i);
            ok = 1;
            break;
        }
    }
    if (!ok) {
        endik = v;
    }
}

vector<int> dist, par;

void dfs_dist(int v, int d = 1, int p = -1) {
    dist[v] = d;
    par[v] = p;
    used[v] = 1;
    for (int i = 0; i < n; i++) {
        if (used[i]) {
            continue;
        }
        if (adj[v][i] == 1) {
            dfs_dist(i, d + 1, v);
        }
    }
    
}


vector<int> longest_trip(int N, int d) {
    n = N;
    adj.assign(n, vector<int>(n, -1));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (adj[i][j] == -1) {
                if (are_connected({i}, {j})) {
                    adj[i][j] = 1;
                    adj[j][i] = 1;
                } else {
                    adj[i][j] = 0;
                    adj[j][i] = 0;
                }
            }
        }
    }
    for (int i = 0; i < n; i++) {
        vector<int> notcon;
        for (int j = 0; j < n; j++) {
            if (adj[i][j] == 0) {
                notcon.push_back(j);
            }
        }
        if (notcon.size() >= n / 2) {
            return notcon;
        }
    }
    used.assign(n, 0);
    dfs(0);
    s.clear();
    used.assign(n, 0);
    dist.assign(n, inf);
    par.assign(n, -1);
    dfs_dist(endik);
    int maxi = -1, mind = -1;
    for (int i = 0; i < n; i++) {
        if (dist[i] > maxi) {
            maxi = dist[i];
            mind = i;
        }
    }
    while (mind != -1) {
        s.push_back(mind);
        mind = par[mind];
    }
    return s;
}

/*
signed main() {
    int N, D;
    cin >> N >> D;
    auto res = longest_trip(N, D);
    for (auto el : res) {
        cout << el << ' ';
    }
    cout << endl;
}
*/

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