oj.uz

Submission #1031961

# Submission time Handle Problem Language Result Execution time Memory
1031961 2024-07-23T09:07:44 Z abczz Longest Trip (IOI23_longesttrip) C++17
15 / 100
 1000 ms 348 KB 
#include "longesttrip.h"
#include <iostream>
#include <vector>
#include <random>
#include <queue>
#include <algorithm>
#define ll int

using namespace std;

std::vector<int> longest_trip(int N, int D)
{
    random_device rd;
    mt19937_64 mt(rd());
    vector <int> V, U, F, X[257], perm;
    bool res;
    bool B[257];
    ll x, y;
    for (int i=0; i<N; ++i) {
        X[i].clear();
        B[i] = 0;
        perm.push_back(i);
    }
    if (D == 3) {
        for (int i=0; i<N; ++i) V.push_back(i);
        return V;
    }
    else if (D == 2) {
        for (int i=1; i<N; ++i) {
            res = are_connected({0}, {i});
            if (res) {
                B[0] = B[i] = 1;
                U.push_back(0);
                V.push_back(i);
                break;
            }
        }
        for (int i=1; i<N; ++i) {
            if (B[i]) continue;
            res = are_connected({U.back()}, {i});
            if (res) U.push_back(i);
            else V.push_back(i);
        }
        for (int i=U.size()-1; i>=0; --i) F.push_back(U[i]);
        for (auto u : V) F.push_back(u);
        return F;
    }
    else {
        F.push_back(perm[0]);
        for (int i=1; i<N; ++i) {
            U.push_back(perm[i]);
            X[perm[i]].push_back(perm[i]);
        }
        while (F.size() < N) {
            V.clear();
            while (!U.empty()) {
                auto u = U.back();
                U.pop_back();
                res = are_connected({F.back()}, {X[u].back()});
                if (res) {
                    while (!X[u].empty()) {
                        auto v = X[u].back();
                        X[u].pop_back();
                        F.push_back(v);
                    }
                    break;
                }
                else {
                    V.push_back(u);
                }
            }
            if (res) {
                if (V.size() > 1) swap(V[0], V[1]);
                for (int i=1; i<V.size(); ++i) {
                    X[V[0]].push_back(V[i]);
                }
                if (!V.empty()) {
                    if (!U.empty()) {
                        auto v = U.back();
                        U.pop_back();
                        U.push_back(V[0]);
                        U.push_back(v);
                    }
                    else U.push_back(V[0]);
                }
            }
            else break;
        }
        if (F.size() == N) return F;
        if (V.size() > 1) swap(V[0], V[1]);
        for (int i=1; i<V.size(); ++i) {
            X[V[0]].push_back(V[i]);
        }
        if (X[V[0]].size() > 1) {
            res = are_connected({F.back()}, {X[V[0]][0]});
            if (res) {
                for (auto v : X[V[0]]) F.push_back(v);
                return F;
            }
        }
        if (F.size() > 1) {
            res = are_connected({F[0]}, {X[V[0]].back()});
            if (res) {
                reverse(F.begin(), F.end());
                while (!X[V[0]].empty()) {
                    auto v = X[V[0]].back();
                    X[V[0]].pop_back();
                    F.push_back(v);
                }
                return F;
            }
            res = are_connected({F[0]}, {X[V[0]][0]});
            if (res) {
                reverse(F.begin(), F.end());
                for (auto v : X[V[0]]) F.push_back(v);
                return F;
            }
        }
        res = are_connected(F, X[V[0]]);
        if (!res) {
            if (F.size() > X[V[0]].size()) return F;
            else return X[V[0]];
        }
        ll l = 0, r = X[V[0]].size()-1, mid;
        vector <ll> tmp;
        while (l < r) {
            tmp.clear();
            mid = (l+r)/2;
            for (int i=l; i<=mid; ++i) tmp.push_back(X[V[0]][i]);
            res = are_connected(F, tmp);
            if (res) r = mid;
            else l = mid + 1;
        }
        y = l;
        l = 0, r = F.size()-1;
        while (l < r) {
            tmp.clear();
            mid = (l+r)/2;
            for (int i=l; i<=mid; ++i) tmp.push_back(F[i]);
            res = are_connected(tmp, {X[V[0]][y]});
            if (res) r = mid;
            else l = mid + 1;
        }
        x = l;
        U.clear();
        for (int i=x+1; i<F.size(); ++i) U.push_back(F[i]);
        for (int i=0; i<=x; ++i) U.push_back(F[i]);
        for (int i=y; i<X[V[0]].size(); ++i) U.push_back(X[V[0]][i]);
        for (int i=0; i<y; ++i) U.push_back(X[V[0]][i]);
        return U;
    }
}

Compilation message

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:54:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   54 |         while (F.size() < N) {
      |                ~~~~~~~~~^~~
longesttrip.cpp:74:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |                 for (int i=1; i<V.size(); ++i) {
      |                               ~^~~~~~~~~
longesttrip.cpp:89:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   89 |         if (F.size() == N) return F;
      |             ~~~~~~~~~^~~~
longesttrip.cpp:91:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         for (int i=1; i<V.size(); ++i) {
      |                       ~^~~~~~~~~
longesttrip.cpp:146:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |         for (int i=x+1; i<F.size(); ++i) U.push_back(F[i]);
      |                         ~^~~~~~~~~
longesttrip.cpp:148:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |         for (int i=y; i<X[V[0]].size(); ++i) U.push_back(X[V[0]][i]);
      |                       ~^~~~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

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

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 6 ms 344 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 4 ms 344 KB Output is correct
5 Correct 5 ms 344 KB Output is correct
6 Correct 6 ms 344 KB Output is correct
7 Correct 8 ms 344 KB Output is correct
8 Correct 5 ms 344 KB Output is correct
9 Correct 7 ms 344 KB Output is correct
10 Correct 7 ms 344 KB Output is correct
11 Correct 5 ms 344 KB Output is correct
12 Correct 6 ms 348 KB Output is correct
13 Correct 5 ms 344 KB Output is correct
14 Correct 11 ms 344 KB Output is correct
15 Correct 9 ms 344 KB Output is correct
16 Execution timed out 3046 ms 344 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 344 KB Output is correct
2 Correct 6 ms 344 KB Output is correct
3 Correct 6 ms 344 KB Output is correct
4 Correct 4 ms 344 KB Output is correct
5 Correct 7 ms 344 KB Output is correct
6 Correct 8 ms 344 KB Output is correct
7 Correct 6 ms 344 KB Output is correct
8 Correct 7 ms 344 KB Output is correct
9 Correct 5 ms 344 KB Output is correct
10 Correct 7 ms 344 KB Output is correct
11 Correct 5 ms 344 KB Output is correct
12 Correct 5 ms 344 KB Output is correct
13 Correct 5 ms 344 KB Output is correct
14 Correct 14 ms 344 KB Output is correct
15 Correct 9 ms 344 KB Output is correct
16 Execution timed out 3067 ms 344 KB Time limit exceeded
17 Halted 0 ms 0 KB -