oj.uz

Submission #1065235

# Submission time Handle Problem Language Result Execution time Memory
1065235 2024-08-19T04:01:33 Z LittleOrange Longest Trip (IOI23_longesttrip) C++17
5 / 100
 1000 ms 688 KB 
#include "longesttrip.h"

#include <vector>
#include<bits/stdc++.h>
using namespace std;
using ll = int;

std::vector<int> longest_trip(int N, int D)
{
    mt19937_64 mt(random_device{}());
    ll n = N;
    if (D==3){
        vector<ll> r(n);
        iota(r.begin(),r.end(),0);
        return r;
    }
    vector<vector<ll>> a(n,vector<ll>(n,0));
    for(ll i = 0;i<n;i++){
        for(ll j = i+1;j<n;j++){
            a[i][j] = a[j][i] = are_connected({i},{j});
        }
    }
    vector<ll> ret;
    vector<ll> ord(n);
    iota(ord.begin(),ord.end(),0);
    vector<ll> cur;
    cur.reserve(n);
    ll cnt = 800000/n;
    while(cnt--){
        shuffle(ord.begin(),ord.end(),mt);
        cur.push_back(ord[0]);
        for(ll i : ord){
            if (a[cur.back()][i]) cur.push_back(i);
        }
        if(cur.size()>ret.size()) ret = cur;
        cur.clear();
    }
    return ret;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 344 KB Output is correct
2 Incorrect 205 ms 688 KB Incorrect
3 Halted 0 ms 0 KB -

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2226 ms 344 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2235 ms 344 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2283 ms 344 KB Time limit exceeded
2 Halted 0 ms 0 KB -