Submission #1081159

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081159		Macker	Longest Trip (IOI23_longesttrip)	C++17	60 / 100	915 ms	728 KiB

longesttrip

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

using namespace std;
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;

#define all(v) v.begin(), v.end()
#define FOR(i, n) for (int i = 0; i < n; i++)
#define inf LLONG_MAX/2
#define ff first
#define ss second
#define ckmin(a, b) a = min(a, b)
#define ckmax(a, b) a = max(a, b)
#define last(s) (*--s.end())
#define first(s) (*s.begin())


vector<int> longest_trip(int n, int D)
{
    bool adj[256][256];
    FOR(i, n) FOR(j, n) adj[i][j] = 0;
    FOR(i, n) FOR(j, i) {
        if(are_connected({i}, {j})){
            adj[i][j] = 1;
            adj[j][i] = 1;
        }
    }

    { // 2 components
        vector<int> vis(n);
        vector<vector<int>> comp;
        function<void(int)> dfs = [&](int a){
            comp.back().push_back(a);
            vis[a] = 1;
            FOR(b, n) if(adj[a][b] && !vis[b]) dfs(b);    
        };

        FOR(i, n){
            if(!vis[i]) {
                comp.push_back({});
                dfs(i);
            }
        }

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

    { // full graph
        bool full = 1;
        FOR(i, n) if(accumulate(adj[i], adj[i] + n, 0) != n - 1) full = 0;
        if(full) {
            vector<int> r;
            FOR(i, n) r.push_back(i);
            return r;
        }
    }

    bool vis[256];
    FOR(i, 256) vis[i] = 0;
    FOR(st, n){
        int a = -1, b;
        FOR(j, n) FOR(k, j){
            if(adj[st][j] && adj[st][k] && !adj[j][k]) a = j, b = k;
        }
        if(a == -1) continue;
        deque<int> res;
        res.push_back(st);
        res.push_back(a);
        res.push_front(b);
        vis[st] = 1; vis[a] = 1; vis[b] = 1;

        FOR(_, n){
            bool f = 0;
            FOR(j, n){
                if(vis[j]) continue;
                if(adj[a][j] && !adj[b][j]){
                    f = 1;
                    a = j;
                    res.push_back(a);
                    vis[a] = 1;
                }
                else if(adj[b][j] && !adj[a][j]){
                    f = 1;
                    b = j;
                    res.push_front(b);
                    vis[b] = 1;
                }
            }
            if(!f){
                f = 0;
                FOR(x, n){
                    if(vis[x]) continue;
                    FOR(y, x){
                        if(vis[y]) continue;
                        if(adj[a][x] && adj[b][y] && !adj[x][y]){
                            f = 1;
                            a = x;
                            b = y;
                            res.push_back(a);
                            vis[a] = 1;
                            res.push_front(b);
                            vis[b] = 1;
                        }
                    }
                }
                if(!f){
                    FOR(x, n) if(!vis[x]) res.push_back(x);
                    return vector<int>(all(res));
                }
            }
        }
        return vector<int>(all(res));
    }
    return {0};
}

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