Submission #880049

#	Time	Username	Problem	Language	Result	Execution time	Memory
880049		RaresFelix	Longest Trip (IOI23_longesttrip)	C++17	70 / 100	23 ms	956 KiB

longesttrip

#include "longesttrip.h"

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

int gaseste_leg(int u, vi comp) {
    int l = 0;
    auto ok = [&](int len) {
        vi A;
        for(int i = 0; i < len; ++i)
            A.push_back(comp[i]);
        return are_connected(A, {u});
    };
    for(int i = 10; i >= 0; --i) {
        if(l + (1 << i) <= comp.size()) {
            if(!ok(l + (1 << i))) l += (1 << i);
        }
    }
    return comp[l];
}

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})) {
                int it = gaseste_leg(i, comp);
                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();
            }
        } 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;
        }
    }
    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]);
            int it = gaseste_leg(R[i], comp);
            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 'int gaseste_leg(int, vi)':
longesttrip.cpp:18:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |         if(l + (1 << i) <= comp.size()) {
      |            ~~~~~~~~~~~~~^~~~~~~~~~~~~~
longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:101:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     for(int i = 0; i < R.size(); ++i) {
      |                    ~~^~~~~~~~~~
longesttrip.cpp:104:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |             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