oj.uz

Submission #1065236

# Submission time Handle Problem Language Result Execution time Memory
1065236 2024-08-19T04:02:32 Z LittleOrange Longest Trip (IOI23_longesttrip) C++17
40 / 100
 938 ms 852 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 = 500000/max(n,10);
    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 6 ms 344 KB Output is correct
2 Incorrect 200 ms 680 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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 449 ms 344 KB Output is correct
2 Correct 501 ms 344 KB Output is correct
3 Correct 238 ms 344 KB Output is correct
4 Correct 456 ms 488 KB Output is correct
5 Correct 840 ms 600 KB Output is correct
6 Correct 645 ms 344 KB Output is correct
7 Correct 570 ms 344 KB Output is correct
8 Correct 237 ms 344 KB Output is correct
9 Correct 361 ms 344 KB Output is correct
10 Correct 859 ms 688 KB Output is correct
11 Correct 851 ms 684 KB Output is correct
12 Correct 906 ms 688 KB Output is correct
13 Correct 846 ms 852 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 428 ms 344 KB Output is correct
2 Correct 507 ms 344 KB Output is correct
3 Correct 263 ms 344 KB Output is correct
4 Correct 433 ms 484 KB Output is correct
5 Correct 855 ms 600 KB Output is correct
6 Correct 676 ms 344 KB Output is correct
7 Correct 567 ms 344 KB Output is correct
8 Correct 259 ms 344 KB Output is correct
9 Correct 341 ms 344 KB Output is correct
10 Correct 810 ms 688 KB Output is correct
11 Correct 719 ms 688 KB Output is correct
12 Correct 764 ms 684 KB Output is correct
13 Correct 716 ms 688 KB Output is correct
14 Correct 668 ms 596 KB Output is correct
15 Correct 701 ms 344 KB Output is correct
16 Correct 543 ms 344 KB Output is correct
17 Correct 310 ms 344 KB Output is correct
18 Correct 298 ms 344 KB Output is correct
19 Correct 338 ms 464 KB Output is correct
20 Correct 387 ms 460 KB Output is correct
21 Correct 801 ms 692 KB Output is correct
22 Correct 735 ms 696 KB Output is correct
23 Correct 856 ms 692 KB Output is correct
24 Correct 872 ms 688 KB Output is correct
25 Correct 720 ms 344 KB Output is correct
26 Correct 659 ms 344 KB Output is correct
27 Correct 564 ms 344 KB Output is correct
28 Correct 565 ms 344 KB Output is correct
29 Correct 591 ms 344 KB Output is correct
30 Correct 256 ms 344 KB Output is correct
31 Correct 294 ms 344 KB Output is correct
32 Correct 331 ms 344 KB Output is correct
33 Correct 354 ms 344 KB Output is correct
34 Correct 376 ms 344 KB Output is correct
35 Correct 357 ms 344 KB Output is correct
36 Correct 862 ms 600 KB Output is correct
37 Correct 812 ms 600 KB Output is correct
38 Correct 898 ms 600 KB Output is correct
39 Correct 818 ms 600 KB Output is correct
40 Correct 908 ms 600 KB Output is correct
41 Correct 891 ms 600 KB Output is correct
42 Correct 895 ms 600 KB Output is correct
43 Correct 911 ms 600 KB Output is correct
44 Correct 876 ms 600 KB Output is correct
45 Correct 725 ms 344 KB Output is correct
46 Correct 770 ms 344 KB Output is correct
47 Correct 569 ms 344 KB Output is correct
48 Correct 575 ms 344 KB Output is correct
49 Correct 583 ms 344 KB Output is correct
50 Correct 258 ms 344 KB Output is correct
51 Correct 296 ms 344 KB Output is correct
52 Correct 308 ms 344 KB Output is correct
53 Correct 383 ms 344 KB Output is correct
54 Correct 417 ms 344 KB Output is correct
55 Correct 376 ms 344 KB Output is correct
56 Correct 863 ms 600 KB Output is correct
57 Correct 872 ms 600 KB Output is correct
58 Correct 903 ms 600 KB Output is correct
59 Correct 922 ms 600 KB Output is correct
60 Correct 887 ms 684 KB Output is correct
61 Correct 867 ms 688 KB Output is correct
62 Correct 874 ms 684 KB Output is correct
63 Correct 938 ms 688 KB Output is correct
64 Correct 857 ms 684 KB Output is correct

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 470 ms 344 KB Output is correct
2 Correct 503 ms 344 KB Output is correct
3 Partially correct 246 ms 344 KB Output is partially correct
4 Partially correct 436 ms 496 KB Output is partially correct
5 Partially correct 855 ms 852 KB Output is partially correct
6 Correct 666 ms 344 KB Output is correct
7 Correct 566 ms 344 KB Output is correct
8 Partially correct 244 ms 344 KB Output is partially correct
9 Partially correct 336 ms 344 KB Output is partially correct
10 Partially correct 873 ms 688 KB Output is partially correct
11 Partially correct 823 ms 684 KB Output is partially correct
12 Partially correct 873 ms 684 KB Output is partially correct
13 Partially correct 850 ms 600 KB Output is partially correct
14 Correct 646 ms 344 KB Output is correct
15 Correct 673 ms 344 KB Output is correct
16 Incorrect 31 ms 344 KB Incorrect
17 Halted 0 ms 0 KB -