oj.uz

Submission #880038

# Submission time Handle Problem Language Result Execution time Memory
880038 2023-11-28T16:01:47 Z RaresFelix Longest Trip (IOI23_longesttrip) C++17
15 / 100
 11 ms 608 KB 
#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({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({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

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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 608 KB Output is correct

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 344 KB Output is correct
2 Correct 5 ms 344 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 4 ms 344 KB Output is correct
5 Correct 5 ms 344 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 344 KB Output is correct
2 Correct 5 ms 344 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 4 ms 344 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Correct 5 ms 344 KB Output is correct
7 Correct 5 ms 344 KB Output is correct
8 Correct 5 ms 344 KB Output is correct
9 Correct 5 ms 344 KB Output is correct
10 Correct 5 ms 608 KB Output is correct
11 Correct 5 ms 344 KB Output is correct
12 Correct 5 ms 600 KB Output is correct
13 Correct 4 ms 608 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 344 KB Output is correct
2 Correct 6 ms 600 KB Output is correct
3 Correct 5 ms 344 KB Output is correct
4 Correct 5 ms 600 KB Output is correct
5 Correct 4 ms 544 KB Output is correct
6 Correct 6 ms 344 KB Output is correct
7 Correct 7 ms 344 KB Output is correct
8 Correct 5 ms 344 KB Output is correct
9 Correct 4 ms 344 KB Output is correct
10 Correct 4 ms 600 KB Output is correct
11 Correct 5 ms 596 KB Output is correct
12 Correct 5 ms 344 KB Output is correct
13 Correct 6 ms 600 KB Output is correct
14 Correct 11 ms 344 KB Output is correct
15 Incorrect 0 ms 344 KB non-disjoint arrays
16 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 5 ms 600 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 5 ms 600 KB Output is correct
5 Correct 4 ms 600 KB Output is correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 10 ms 344 KB Output is correct
8 Correct 5 ms 344 KB Output is correct
9 Correct 6 ms 344 KB Output is correct
10 Correct 4 ms 344 KB Output is correct
11 Correct 5 ms 344 KB Output is correct
12 Correct 5 ms 432 KB Output is correct
13 Correct 4 ms 608 KB Output is correct
14 Correct 9 ms 596 KB Output is correct
15 Incorrect 0 ms 344 KB non-disjoint arrays
16 Halted 0 ms 0 KB -