oj.uz

Submission #839846

# Submission time Handle Problem Language Result Execution time Memory
839846 2023-08-30T18:43:38 Z jtnydv25 Longest Trip (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

# Verdict Execution time Memory Grader output
1 Incorrect 1 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 208 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 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

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