Submission #1033192

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033192		TAhmed33	가장 긴 여행 (IOI23_longesttrip)	C++17	100 / 100	13 ms	600 KiB

longesttrip

#include "longesttrip.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
bool check (int x, int y) {
    assert(x != y);
    return are_connected({x}, {y});
}
vector <int> longest_trip (int n, int d) {
    vector <int> x, y;  
    x.push_back(0);  
    y.push_back(1);
    for (int i = 2; i + 1 < n; i += 2) {
        int u = i, v = i + 1;
        if (check(u, v)) {
            if (check(u, x.back())) {
                x.push_back(u); x.push_back(v);
            } else if (check(u, y.back())) {
                y.push_back(u); y.push_back(v);
            } else {
                reverse(y.begin(), y.end());
                for (auto j : y) {
                    x.push_back(j);
                }
                y.clear();
                y.push_back(u); y.push_back(v);
            }
        } else { //preferably make a flowchart for this part
            if (check(u, x.back())) {
                x.push_back(u);
                if (check(v, y.back())) {
                    y.push_back(v);
                } else {
                    reverse(y.begin(), y.end());
                    for (auto j : y) {
                        x.push_back(j);
                    }
                    y.clear();
                    y.push_back(v);
                }
            } else {
                x.push_back(v);
                if (check(u, y.back())) {
                    y.push_back(u);
                } else {
                    reverse(y.begin(), y.end());
                    for (auto j : y) {
                        x.push_back(j);
                    }
                    y.clear();
                    y.push_back(u);
                }
            }
        }
    }
    if (n & 1) {
        int i = n - 1;
        bool f = check(x.back(), i);
        bool g = check(y.back(), i);
        if (!f && !g) {
            reverse(y.begin(), y.end());
            for (auto j : y) {
                x.push_back(j);
            }
            y.clear();
            y.push_back(i);
        } else if (f) {
            x.push_back(i);
        } else {
            y.push_back(i);
        }
    }
    if (!are_connected(x, y)) {
        if (x.size() < y.size()) {
            swap(x, y);
        }
        return x;
    }
    vector <int> gg = {x.front()}, hh = {y.front()};
    if (x.size() != 1) gg.push_back(x.back());
    if (y.size() != 1) hh.push_back(y.back());
    for (auto i : gg) {
        for (auto j : hh) {
            if (are_connected({i}, {j})) {
                if (i == x.front()) {
                    reverse(x.begin(), x.end());
                }
                if (j == y.back()) {
                    reverse(y.begin(), y.end());
                }
                for (auto g : y) {
                    x.push_back(g);
                }
                return x;
            }
        }
    } 
    int L1 = 0, R1 = int(x.size()) - 1, ANS1 = -1;
    while (L1 <= R1) {
        int mid = (L1 + R1) / 2;
        vector <int> dd;
        for (int i = 0; i <= mid; i++) {
            dd.push_back(x[i]);
        }
        if (are_connected(dd, y)) {
            R1 = mid - 1; ANS1 = mid;
        } else {
            L1 = mid + 1;
        }
    }
    for (int i = ANS1; i <= ANS1; i++) {
        int l = 0, r = int(y.size()) - 1, ans = -1;
        while (l <= r) {
            int mid = (l + r) / 2;
            vector <int> dd;
            for (int j = 0; j <= mid; j++) {
                dd.push_back(y[j]);
            }
            if (are_connected({x[i]}, dd)) {
                r = mid - 1; ans = mid;
            } else {
                l = mid + 1;
            }
        }
        if (ans == -1) continue;
        vector <int> ret;
        for (int j = i - 1; j >= 0; j--) {
            ret.push_back(x[j]);
        }
        for (int j = int(x.size()) - 1; j > i; j--) {
            ret.push_back(x[j]);
        }
        ret.push_back(x[i]);
        ret.push_back(y[ans]);
        for (int j = ans + 1; j < int(y.size()); j++) {
            ret.push_back(y[j]);
        }
        for (int j = 0; j < ans; j++) {
            ret.push_back(y[j]);
        }
        return ret;
    }
}

Compilation message (stderr)

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:10:18: warning: control reaches end of non-void function [-Wreturn-type]
   10 |     vector <int> x, y;
      |                  ^

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