Submission #880041

#	Time	Username	Problem	Language	Result	Execution time	Memory
880041		RaresFelix	Longest Trip (IOI23_longesttrip)	C++17	70 / 100	25 ms	1112 KiB

longesttrip

#include "longesttrip.h"

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

std::vector<int> longest_trip(int N, int D) {
    if(D >= 2) {
        deque<int> Re;
        Re.push_back(0);
        vi Took(N, 0);
        Took[0] = 1;
        if(are_connected({0}, {1})) {
            Re.push_back(1);
            Took[1] = 1;
        } else {
            Took[2] = 1;
            Re.push_back(2);
        }
        for(int i = 0; i < N; ++i) {
            if(!Took[i]) {
                if(are_connected({i}, {Re.front()})) {
                    Re.push_front(i);
                } else Re.push_back(i);
                Took[i] = 1;
            }
        }
        vi R;
        for(auto it : Re) R.push_back(it);
        return R;
    }
    int nod_curent = 0;
    vi comp, R;
    for(int i = 1; i < N; ++i) {
        if(are_connected({nod_curent}, {i})) {
            R.push_back(nod_curent);
            nod_curent = i;
            if(!comp.empty() && are_connected(comp, {i})) {
                for(auto it : comp) {
                    if(are_connected({it}, {i})) {
                        R.push_back(i);
                        vi E;
                        E.push_back(it);
                        for(auto it2 : comp) if(it2 != it) E.push_back(it2);
                        nod_curent = E.back();
                        E.pop_back();
                        for(auto it : E) R.push_back(it);
                        comp.clear();
                        break;
                    }
                }
            }
        } else {
            comp.push_back(i);
        }
    }
    if(comp.empty()) {
        R.push_back(nod_curent);
        return R;
    }
    if(R.empty()) {
        ///nod singur si componenta
        return comp;
    }
    //am ramas cu (R, nod_curent) si o componenta conexa
    for(auto it : comp) {
        if(are_connected({it}, {R[0]})) {
            vi Re;
            for(auto it2:comp)
                if(it2 != it) Re.push_back(it2);
            Re.push_back(it);
            for(auto it : R) Re.push_back(it);
            Re.push_back(nod_curent);
            return Re;
        }
        if(are_connected({it}, {nod_curent})) {
            vi Re;
            for(auto it : R) Re.push_back(it);
            Re.push_back(nod_curent);
            Re.push_back(it);
            for(auto it2 : R)
                if(it2 != it) Re.push_back(it2);
            return Re;
        }
    }
    assert(are_connected({R[0]}, {nod_curent}));
    vi Re;
    for(int i = 0; i < R.size(); ++i) {
        if(are_connected({R[i]}, comp)) {
            vi Re;
            for(int j = i + 1; j < R.size(); ++j)
                Re.push_back(R[j]);
            Re.push_back(nod_curent);
            for(int j = 0; j <= i; ++j)
                Re.push_back(R[j]);
            for(auto it : comp){
                if(are_connected({R[i]}, {it})) {
                    Re.push_back(it);
                    for(auto it2 : comp)
                        if(it2 != it) Re.push_back(it2);
                    return Re;
                }
            }
        }
    }
    if(comp.size() >= 1 + R.size()) {
        return comp;
    }
    R.push_back(nod_curent);
    return R;
}

Compilation message (stderr)

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:90:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     for(int i = 0; i < R.size(); ++i) {
      |                    ~~^~~~~~~~~~
longesttrip.cpp:93:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |             for(int j = i + 1; j < R.size(); ++j)
      |                                ~~^~~~~~~~~~

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