Submission #1170250

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170250		antonn	Longest Trip (IOI23_longesttrip)	C++20	5 / 100	332 ms	660 KiB

longesttrip

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

#define F first
#define S second
 
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
 
template<class T> bool ckmin(T& a, T b) { return b < a ? a = b, true : false; }
template<class T> bool ckmax(T& a, T b) { return a < b ? a = b, true : false; }

const int NMAX = 3e2 + 7;

vector<int> g[NMAX];
bool vis[NMAX];

void dfs(int u) {
    vis[u] = 1;
    for (auto v : g[u]) if (!vis[v]) dfs(v);
}

vector<int> longest_trip(int n, int d) {
    for (int i = 0; i < n; ++i) vis[i] = 0, g[i].clear();
    vector<vector<bool>> edge(n, vector<bool>(n, 0));
    vector<int> deg(n);
    ll sumdeg = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (are_connected({i}, {j}) == 1) {
                edge[i][j] = 1;
                edge[j][i] = 1;
                ++deg[i];
                ++deg[j];
                sumdeg += 2;
                g[i].push_back(j);
                g[j].push_back(i);
            }
        }
    }
    dfs(0);
    vector<int> a, b;
    for (int i = 0; i < n; ++i) {
        if (vis[i]) a.push_back(i);
        if (!vis[i]) b.push_back(i);
    }
    if (!a.empty() && !b.empty()) {
        if (a.size() > b.size()) {
            return a;
        } else {
            return b;
        }
    }
    if (sumdeg == n * (n - 1)) {
        vector<int> sol;
        for (int i = 0; i < n; ++i) sol.push_back(i);
        return sol;
    }
    for (int a = 0; a < n; ++a) {
        ll s = sumdeg;
        s -= 2 * deg[a];
        if (s == (n - 1) * (n - 2)) {
            int who = -1;
            for (auto x : g[a]) {
                who = x;
            }
            vector<int> sol;
            for (int i = 0; i < n; ++i) if (i != who && i != a) sol.push_back(i);
            sol.push_back(who);
            sol.push_back(a);
            return sol;
        }
    }
    for (int a = 0; a < n; ++a) {
        for (int b = a + 1; b < n; ++b) {
            if (!edge[a][b]) continue;
            ll s = sumdeg;
            s -= 2 * deg[a];
            s -= 2 * deg[b];
            s += 2;
            if (s == (n - 2) * (n - 3)) {
                int who = -1;
                for (auto x : g[a]) {
                    if (x != b) {
                        who = x;
                    }
                }
                for (auto x : g[b]) {
                    if (x != a) {
                        who = x;
                    }
                }
                vector<int> sol;
                for (int i = 0; i < n; ++i) if (i != who && i != a && i != b) sol.push_back(i);
                sol.push_back(who);
                if (edge[who][a]) sol.push_back(a), sol.push_back(b);
                else sol.push_back(b), sol.push_back(a);
                return sol;
            }
        }
    }
    return {};
}

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