제출 #1138815

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1138815		TAhmed33	Longest Trip (IOI23_longesttrip)	C++17	0 / 100	0 ms	416 KiB

longesttrip

#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
int cnt;
vector <int> tree[256];
bool vis[256];
vector <int> x;
int p[256];
set <int> unvis;
void dfs (int pos) {
    vis[pos] = 1; x.push_back(pos); unvis.erase(pos);
    while (true) {
        vector <int> t; for (auto i : unvis) t.push_back(i);
        if (!are_connected({pos}, t)) break;
        int l = 0, r = (int)t.size() - 1, ans = -1;
        while (l <= r) {
            int mid = (l + r) / 2;
            vector <int> g;
            for (int i = 0; i <= mid; i++) g.push_back(t[i]);
            cnt++; assert(cnt <= 3000);
            if (are_connected({pos}, g)) {
                r = mid - 1; ans = mid; 
            } else {
                l = mid + 1;
            }
        }
        if (ans == -1) break;
        tree[pos].push_back(t[ans]);
        p[t[ans]] = pos;
        dfs(t[ans]);
    }
}
int get (int x) {
    if (tree[x].empty()) return x;
    return get(tree[x][0]);
}
vector <int> longest_trip (int n, int d) {
    cnt = 0;
    unvis.clear(); for (int i = 0; i < n; i++) unvis.insert(i);
    for (int i = 0; i < n; i++) tree[i].clear();
    memset(p, -1, sizeof(p));
    memset(vis, 0, sizeof(vis));
    x.clear(); dfs(0);
    if (!unvis.empty()) {
        vector <int> ret = x;
        for (int i = 0; i < n; i++) {
            if (!vis[i]) {
                x.clear(); dfs(i);
                if ((int)x.size() > (int)ret.size()) ret = x;
            }
        }
        return ret;
    }
    int pos = -1;
    for (int i = 0; i < n; i++) {
        if ((int)tree[i].size() == 2) {
            pos = i;
        }
    }
    if (pos == -1) return x;
    int u = get(tree[pos][0]), v = get(tree[pos][1]);
    if (p[pos] != -1 && !are_connected({p[pos]}, {u})) {
        swap(u, v); swap(tree[pos][0], tree[pos][1]);
    }
    u = tree[pos][0], v = tree[pos][1];
    while (!x.empty() && x.back() != p[pos]) x.pop_back();
    vector <int> l;
    while (true) {
        l.push_back(u);
        if (tree[u].empty()) break;
        u = tree[u][0];
    }
    reverse(l.begin(), l.end());
    for (auto i : l) x.push_back(i);
    x.push_back(pos);
    while (true) {
        x.push_back(v);
        if (tree[v].empty()) break;
        v = tree[v][0];
    }
    return x;   
}

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