Submission #1310366

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310366		AliMark71	Longest Trip (IOI23_longesttrip)	C++20	15 / 100	4 ms	440 KiB

longesttrip

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

template<typename T>
using vec = std::vector<T>;
using namespace std;

struct xlist {
    struct node {
        int storage;
        uintptr_t npx;
    };
    
    node *head = nullptr, *tail = nullptr;
    int size = 0;
    
    xlist(initializer_list<int> list) {
        if (list.size() == 0) return;
        size = 1;
        head = tail = new node{ .storage = *list.begin() };
        for (auto it = next(list.begin()); it != list.end(); ++it)
            append(*it);
    }
    
    void append(int a) {
        if (size == 0) {
            *this = xlist{a};
            return;
        }
        
        node *t = new node{ .storage = a };
        t->npx = (uintptr_t)tail;
        tail->npx ^= (uintptr_t)t;
        tail = t;
        size++;
    }
    
    void concat(xlist &l) {
        if (size == 0) {
            *this = l;
            return;
        }
        if (l.size == 0)
            return;
        
        tail->npx ^= (uintptr_t)l.head;
        l.head->npx ^= (uintptr_t)tail;
        tail = l.head;
        size += l.size;
        
        l.size = 0;
        l.head = l.tail = nullptr;
    }
    
    int back() {
        return tail->storage;
    }
    
    void reverse() {
        swap(head, tail);
    }
    
    vec<int> collect() {
        vec<int> res;
        
        uintptr_t prev = 0;
        node* curr = head;
        while (curr != nullptr) {
            res.push_back(curr->storage);
            
            uintptr_t next = curr->npx ^ prev;
            prev = (uintptr_t) curr;
            curr = (node*)next;
        }
        return res;
    }
};

std::vector<int> longest_trip(int N, int D)
{
    vec<int> nodes(N); for (int i = 0; i < N; i++) nodes[i] = i;
    if (D == 3)
        return nodes;
    if (D == 2) {
        deque<int> path{0, are_connected({0}, {1}) ? 1 : 2};
        nodes.erase(find(nodes.begin(), nodes.end(), path.front()));
        nodes.erase(find(nodes.begin(), nodes.end(), path.back()));
        
        while (!nodes.empty()) {
            auto u = nodes.back(); nodes.pop_back();
            if (are_connected({path.front()}, {u}))
                path.push_front(u);
            else
                path.push_back(u);
        }
        
        return vec<int>(path.begin(), path.end());
    }
    
    xlist path[2] = {{0}, {1}};
    nodes.erase(find(nodes.begin(), nodes.end(), path[0].back()));
    nodes.erase(find(nodes.begin(), nodes.end(), path[1].back()));
    while (!nodes.empty()) {
        auto u = nodes.back(); nodes.pop_back();
        if (are_connected({path[0].back()}, {u}))
            path[0].append(u);
        else if (are_connected({path[1].back()}, {u}))
            path[1].append(u);
        else {
            path[1].reverse();
            path[0].concat(path[1]);
            path[1].append(u);
        }
    }
    
    return (path[0].size > path[1].size ? path[0] : path[1]).collect();
}

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