Submission #903940

#	Time	Username	Problem	Language	Result	Execution time	Memory
903940		LaviniaTornaghi	Longest Trip (IOI23_longesttrip)	C++17	25 / 100	13 ms	1464 KiB

longesttrip

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

struct XorList {
    struct Node {
        int val;
        Node *x, *y;

        Node(int val) : val(val), x(NULL), y(NULL) { }
    } *start, *end;

    void merge(XorList *o) {
        if (end->x == NULL) {
            end->x = o->start;
        } else {
            end->y = o->start;
        }

        if (o->start->x == NULL) {
            o->start->x = end;
        } else {
            o->start->y = end;
        }

        end = o->end;
        o->start = o->end = NULL;
    }

    vector<int> vectorize() {
        vector<int> ans;
        
        Node* curr = start, *old = NULL;
        while (curr != NULL) {
            ans.push_back(curr->val);

            if (old == curr->x) {
                old = curr;
                curr = old->y;
            } else {
                old = curr;
                curr = old->x;
            }
        }
        return ans;
    }

    int last() { return end->val; }
    void reverse() { swap(start, end); }
    XorList(int val) { start = end = new Node(val); }
};

vector<int> longest_trip(int N, int D) {
    XorList *a = new XorList(0);
    XorList *b = new XorList(1);
    
    for (int i = 2; i < N; i++) {
        int last_a = a->last();
        int last_b = b->last();
        XorList *m = new XorList(i);

        if (are_connected({last_a}, {last_b})) {
            b->reverse();
            a->merge(b);

            b = m;
        } else if (are_connected({last_a}, {i})) {
            a->merge(m);
        } else {
            b->merge(m);
        }
    }

    vector<int> chain_a = a->vectorize();
    vector<int> chain_b = b->vectorize();

    if (chain_a.size() > chain_b.size()) {
        return chain_a;
    } else {
        return chain_b;
    }
}

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