oj.uz

Submission #843015

# Submission time Handle Problem Language Result Execution time Memory
843015 2023-09-03T14:37:49 Z pit4h Longest Trip (IOI23_longesttrip) C++17
15 / 100
 1000 ms 2097152 KB 
#include<bits/stdc++.h>
#include "longesttrip.h"

using namespace std;

pair<int, int> find_connection(vector<int> vec1, vector<int> vec2) {
    if (!are_connected(vec1, vec2)) {
        return make_pair(-1, -1);
    }
    if (vec1.size() == 1 && vec2.size() == 1) {
        return make_pair(vec1[0], vec2[0]);
    } 
    if (vec1.size() == 1) {
        return find_connection(vec2, vec1);
    }

    vector<int> half;
    for (int i = 0; i < (int)vec1.size() / 2; i++) {
        half.push_back(vec1[i]);
    }
    pair<int, int> res = find_connection(half, vec2);
    if (res != make_pair(-1, -1)) {
        return res;
    }

    half.clear();
    for (int i = (int)vec1.size() / 2; i < (int)vec1.size(); i++) {
        half.push_back(vec1[i]);
    }
    return find_connection(half, vec2);
}

int find_position(int el, vector<int> vec) {
    for (int i = 0; i < (int)vec.size(); i++) {
        if (vec[i] == el) {
            return i;
        }
    }
    return -1;
}

vector<int> longest_trip(int N, int D)
{
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    vector<int> path[2];  

    path[0] = {0}; 

    for (int i = 1; i < N; i++) {
        bool which = uniform_int_distribution<int>(0, 1)(rng);
        if (path[which].empty()) {
            which = !which;
        }

        if (are_connected({path[which].back()}, {i})) {
            path[which].push_back(i);
            if (!path[!which].empty() && 
                are_connected({path[!which].back()}, {i})) {
                while (!path[!which].empty()) {
                    path[which].push_back(path[!which].back());
                    path[!which].pop_back();
                }        
            }
        }
        else {
            path[!which].push_back(i);
        }
    }

    if (path[0].empty()) {
        return path[1];
    }
    if (path[1].empty()) {
        return path[0];
    }

    vector<int> res;
    vector<int> path_ends[2];

    for (int i = 0; i <= 1; i++) {
        if (path[i].size() == 1u) {
            path_ends[i] = {path[i][0]};
        }
        else {
            path_ends[i] = {path[i][0], path[i].back()};
        }
    }

    if (are_connected(path_ends[0], path_ends[1])) {
        if (are_connected({path[0][0]}, {path[1][0]})) {
            for (int i: path[1]) {
                res.push_back(i);
            }
            reverse(res.begin(), res.end());
            for (int i: path[0]) {
                res.push_back(i);
            }
        }
        else if(are_connected({path[0][0]}, {path[1].back()})) {
            for (int i: path[1]) {
                res.push_back(i);
            }
            for (int i: path[0]) {
                res.push_back(i);
            }
        }
        else if(are_connected({path[0].back()}, {path[1][0]})) {
            for (int i: path[0]) {
                res.push_back(i);
            }
            for (int i: path[1]) {
                res.push_back(i);
            }
        }
        else {
            assert(false);
        }
    }
    else {
        pair<int, int> conn = find_connection(path[0], path[1]);
        if (conn == make_pair(-1, -1)) {
            res = (path[0].size() > path[1].size())?path[0] : path[1];
        }
        else {
            int pos[2] = {find_position(conn.first, path[0]), find_position(conn.second, path[1])};
            for (int i = (pos[0] + 1) % path[0].size(); i != pos[0]; i = (i + 1) % path[0].size()) {
                res.push_back(path[0][i]);
            }        
            res.push_back(conn.first);
            res.push_back(conn.second);
            for (int i = (pos[1] + 1) % path[1].size(); i != pos[1]; i = (i + 1) % path[1].size()) {
                res.push_back(path[1][i]);
            }
        }
    }

    return res;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 596 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 8 ms 344 KB Output is correct
2 Correct 7 ms 344 KB Output is correct
3 Correct 6 ms 344 KB Output is correct
4 Correct 5 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 8 ms 344 KB Output is correct
2 Correct 7 ms 344 KB Output is correct
3 Correct 6 ms 360 KB Output is correct
4 Correct 6 ms 344 KB Output is correct
5 Correct 5 ms 600 KB Output is correct
6 Correct 10 ms 596 KB Output is correct
7 Correct 6 ms 344 KB Output is correct
8 Correct 6 ms 344 KB Output is correct
9 Correct 5 ms 344 KB Output is correct
10 Correct 5 ms 600 KB Output is correct
11 Correct 4 ms 600 KB Output is correct
12 Correct 5 ms 600 KB Output is correct
13 Correct 6 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 8 ms 344 KB Output is correct
3 Correct 5 ms 344 KB Output is correct
4 Correct 7 ms 344 KB Output is correct
5 Correct 6 ms 600 KB Output is correct
6 Correct 9 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 5 ms 440 KB Output is correct
10 Correct 6 ms 600 KB Output is correct
11 Correct 7 ms 600 KB Output is correct
12 Correct 6 ms 596 KB Output is correct
13 Correct 7 ms 600 KB Output is correct
14 Correct 14 ms 344 KB Output is correct
15 Correct 10 ms 344 KB Output is correct
16 Execution timed out 1795 ms 2097152 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

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