oj.uz

답안 #843015

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
843015 2023-09-03T14:37:49 Z pit4h 가장 긴 여행 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -