Submission #1223087

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223087		nikd	Longest Trip (IOI23_longesttrip)	C++20	15 / 100	328 ms	432 KiB

longesttrip

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

std::vector<int> longest_trip(int n, int D)
{
    vector<vector<bool>> adj(n, vector<bool>(n));
    for(int i = 0; i<n; i++){
        for(int j = i+1; j<n; j++){
            if(are_connected({i}, {j})){
                adj[i][j] = 1;
                adj[j][i] = 1;
            }
        }
    }
    // longest path ???
    // D=2
    vector<int> vis(n, 0);
    vector<int> sol(n-1);
    int nd = 0;
    for(int i = 0; i<n-1; i++){
        vis[nd] = 1;
        sol[i] = nd;
        if(i == n-2) break;
        for(int u = 0; u<n; u++){
            if(adj[nd][u]){
                if(!vis[u]){
                    nd = u; break;
                }
            }
        }
    }
    int manc = -1;
    for(int i= 0; i<n; i++) if(!vis[i]){
        manc = i; break;
    }
    assert(adj[nd][manc] || adj[0][manc]);
    if(adj[nd][manc]) sol.push_back(manc);
    else sol.insert(sol.begin(), manc);
    assert(sol.size() == n);
    return sol;
}

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