oj.uz

답안 #839846

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
839846 2023-08-30T18:43:38 Z jtnydv25 가장 긴 여행 (IOI23_longesttrip) C++17
0 / 100
 26 ms 392 KB 
#include "longesttrip.h"

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define all(c) ((c).begin()), ((c).end())
#define sz(x) ((int)(x).size())

#ifdef LOCAL
#include <print.h>
#else
#define trace(...)
#define endl "\n" // remove in interactive
#endif

vector<vector<int>>  remove(vector<vector<int>> P, int a, int b){
    vector<vector<int>> ret;
    for(int i = 0; i < sz(P); i++) if(i != a && i != b) ret.push_back(P[i]);
    return ret;
}

vector<int> longest_trip(int n, int d){
    vector<vector<int>> paths;
    
    vector<int> nodes(n), b(n - 1);
    iota(all(nodes), 0);
    random_shuffle(all(nodes));
    // for(int i = 0; i < n - 1; i++){
    //     b[i] = are_connected({nodes[i]}, {nodes[i + 1]});
    // }
    vector<int> vis(n);
    // for(int i = 0; i < n; i++) if(!vis[i]){
    //     int j = i;
    //     vector<int> path;
    //     while(j < n){
    //         path.push_back(nodes[j]);
    //         vis[j] = true;
    //         if(j == n - 1) break;
    //         if(j < n - 1 && b[j]){
    //             j++;
    //             continue;
    //         } else if(j < n - 2 && !b[j + 1]){
    //             j += 2;
    //             continue;
    //         }
    //         break;
    //     }
    //     paths.push_back(path);
    // }
    for(int i = 0; i < n; i++) paths.push_back({i});
    if(sz(paths) == 1) return paths[0];
    // return {};
    while(sz(paths) > 2){
        int k = sz(paths);
        int p = rand() % k, q = rand() % k, r = rand() % k;
        while(p == q || q == r || p == r){
            p = rand() % k, q = rand() % k, r = rand() % k;
        }
        int pp = p, qq = q;
        if(!are_connected({paths[p][0]}, {paths[q][0]})){
            if(rand() % 2) swap(p, q);
            if(are_connected({paths[q][0]}, {paths[r][0]})){
                pp = q; qq = r;
            } else{
                qq = r;
            }
        }
        vector<int> newpath = paths[pp];
        reverse(all(newpath));
        copy(all(paths[qq]), back_inserter(newpath));
        paths = remove(paths, pp, qq);
        paths.push_back(newpath);
    }

    // for(int i = 0; i < 2; i++){
    //     for(int j = 0; j < 2; j++){
    //         if(are_connected({paths[0][0]}, {paths[1][0]})){
    //             vector<int> Q = paths[0];
    //             reverse(all(Q));
    //             copy(all(paths[1]), back_inserter(Q));
    //             return Q;
    //         }
    //         reverse(all(paths[1]));
    //     }
    //     reverse(all(paths[0]));
    // }
    // vector<int> P = paths[0], Q = paths[1];
    // if(are_connected(paths[0], paths[1])){
    //     for(int i = 0; i < 2; i++){
    //         while(sz(paths[i]) > 1){
    //             int k = sz(paths[i]) / 2;
    //             vector<int> lft(paths[i].begin(), paths[i].begin() + k);
    //             vector<int> rgt(paths[i].begin() + k, paths[i].end());
    //             if(are_connected(lft, paths[i ^ 1])){
    //                 paths[i] = lft;
    //             } else paths[i] = rgt;
    //         }
    //     }
    //     vector<int> final_path;
    //     int posP = find(all(P), paths[0][0]) - P.begin();
    //     int posQ = find(all(P), paths[0][0]) - P.begin();
    //     posP = (posP + 1) % sz(P);
    //     rotate(P.begin(), P.begin() + posP, P.end());
    //     rotate(Q.begin(), Q.begin() + posQ, Q.end());
    //     copy(all(Q), back_inserter(P));
    //     return P;
    // }

    return sz(paths[0]) > sz(paths[1]) ? paths[0] : paths[1];
}

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 208 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #1
0.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 208 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 208 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 208 KB Output is correct
2 Correct 8 ms 208 KB Output is correct
3 Correct 10 ms 356 KB Output is correct
4 Correct 14 ms 336 KB Output is correct
5 Correct 26 ms 336 KB Output is correct
6 Correct 8 ms 208 KB Output is correct
7 Correct 8 ms 208 KB Output is correct
8 Correct 12 ms 336 KB Output is correct
9 Correct 12 ms 336 KB Output is correct
10 Correct 19 ms 336 KB Output is correct
11 Correct 21 ms 336 KB Output is correct
12 Correct 18 ms 392 KB Output is correct
13 Correct 18 ms 336 KB Output is correct
14 Incorrect 1 ms 208 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 208 KB Incorrect
2 Halted 0 ms 0 KB -