oj.uz

Submission #839848

# Submission time Handle Problem Language Result Execution time Memory
839848 2023-08-30T18:47:49 Z jtnydv25 Longest Trip (IOI23_longesttrip) C++17
0 / 100
 31 ms 496 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;
            }
        }
        assert(are_connected({paths[pp][0]}, {paths[qq][0]}));
        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

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 260 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 208 KB Output is correct
2 Correct 12 ms 208 KB Output is correct
3 Correct 16 ms 316 KB Output is correct
4 Correct 18 ms 356 KB Output is correct
5 Correct 31 ms 368 KB Output is correct
6 Correct 6 ms 208 KB Output is correct
7 Correct 17 ms 208 KB Output is correct
8 Correct 16 ms 332 KB Output is correct
9 Correct 19 ms 348 KB Output is correct
10 Correct 31 ms 372 KB Output is correct
11 Correct 25 ms 496 KB Output is correct
12 Correct 26 ms 348 KB Output is correct
13 Correct 28 ms 368 KB Output is correct
14 Runtime error 1 ms 336 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB Incorrect
2 Halted 0 ms 0 KB -