Submission #1247280

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247280		12baater	Longest Trip (IOI23_longesttrip)	C++20	5 / 100	4 ms	416 KiB

longesttrip

#include "longesttrip.h"
#include <vector>
#include <stack>
#include <iostream>
#include <deque>
#include <queue>

using namespace std;

vector<int> longest_trip(int N, int D)
{
    deque<int> flink;
    deque<int> slink;
    flink.push_back(0);
    queue<int> to_link;
    for (int i = 1; i < N; i++) {
        to_link.push(i);
    }

    for (; !to_link.empty(); to_link.pop()) {
        bool add_next = are_connected({flink.back()}, {to_link.front()});
        if (add_next) {
            flink.push_back(to_link.front());
        } else {
            slink.push_back(to_link.front());
            to_link.pop();
            break;
        }
    }


    for (; !to_link.empty(); to_link.pop()) {
        bool in_flink = are_connected({flink.back()}, {to_link.front()});
        if (in_flink) {
            flink.push_back(to_link.front());
            if (slink.empty()) continue;
            if (are_connected({flink.back()}, {slink.back()})) {
                while (!slink.empty()) {
                    flink.push_back(slink.back());
                    slink.pop_back();
                }
            }
        } else {
            slink.push_back(to_link.front());
        }
    }

    vector<int> fLink;
    for (; !flink.empty(); flink.pop_back()) {
        fLink.push_back(flink.back());
    }
    vector<int> sLink;
    for (; !slink.empty(); slink.pop_back()) {
        sLink.push_back(slink.back());
    }

    if (sLink.size() < 1) {
        return fLink;
    } else if (fLink.size() < 1) {
        return sLink;
    }

    // cout << "///log\n";

    if (fLink.size() < sLink.size()) swap(sLink,fLink);

    // for (int x : fLink) {
    //     cout << x << " ";
    // }
    // cout << endl;
    //
    // for (int x : sLink) {
    //     cout << x << " ";
    // }
    // cout << endl;

    bool same_component = are_connected(fLink, sLink);
    // cout << "///log\n";

    if (!same_component) {
        if (fLink.size() > sLink.size()) {
            return fLink;
        } else {
            return sLink;
        }
    }

    int l = 0, r = fLink.size() - 1;

    // cout << "///log\n";
    while (l < r) {
        int mid = (l+r)/2;
        vector<int> testV;
        for (int i = l; i <= mid; i++) {
            testV.push_back(fLink[i]);
        }
        if (are_connected(testV, sLink)) {
            r = mid;
        } else {
            l = mid+1;
        }
    }
    int connectionPoint = fLink[r];
    int connectionIndex = r;
    // cout << connectionPoint << "\n";

    

    // vector<int> ans;
    // for (int i = 0; i < fLink.size(); i++) {
    //     if (i == connectionIndex) continue;
    //     ans.push_back(fLink[i]);
    // }
    //
    // ans.push_back(connectionPoint);
    // if (are_connected({connectionPoint}, {sLink.front()})) {
    //     for (int i = 0; i < sLink.size(); i++) {
    //         ans.push_back(sLink[i]);
    //     }
    // } else {
    //     for (int i = sLink.size()-1; i >= 0; i--) {
    //         ans.push_back(sLink[i]);
    //     }
    // }



    // cout << "///log\n";
    // for (auto x : ans) {
    //     cout << x << " ";
    // }
    // cout << "\n////logend\n";

    // return ans;

    l = 0, r = sLink.size() - 1;

    while (l < r) {
        int mid = (l+r)/2;
        vector<int> testV;
        for (int i = l; i <= mid; i++) {
            testV.push_back(sLink[i]);
        }
        if (are_connected({connectionPoint}, testV)) {
            r = mid;
        } else {
            l = mid+1;
        }
    }

    int cP2 = sLink[r];

    vector<int> ans;
    for (int i = 0; i < fLink.size(); i++) {
        if (i == connectionIndex) continue;
        ans.push_back(fLink[i]);
    }

    ans.push_back(connectionPoint);
    ans.push_back(cP2);
    for (int i = 0; i < sLink.size(); i++) {
        if (sLink[i] == cP2) continue;
        ans.push_back(sLink[i]);
    }
    return ans;
}

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