oj.uz

Submission #993049

# Submission time Handle Problem Language Result Execution time Memory
993049 2024-06-05T09:18:40 Z Muhammet Longest Trip (IOI23_longesttrip) C++17
40 / 100
 999 ms 3808 KB 
#include <bits/stdc++.h>
#include "longesttrip.h"

#define N 1505

using namespace std;

vector <int> v[N], v1;

int c[N], k, y;

bool vis[N][N], vi[N];

void dfs(int x){
    vi[x] = 1;
    if(k < c[x]) y = x;
    k = max(c[x], k);
    for(auto i : v[x]){
        if(vi[i] == 0){
            c[i] = c[x] + 1;
            dfs(i);
        }
    }
}

void df(int x){
    v1.push_back(x);
    if(c[x] == 1) return;
    for(auto i : v[x]){
        if(c[i] == c[x] - 1){
            df(i);
            break;
        }
    }
}

vector<int> longest_trip(int n, int d) {
    vector <int> a(1), b(1);
    for(int i = 0; i < n; i++) v[i].clear();
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            vis[i][j] = 0;
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = i+1; j < n; j++){
            a[0] = i;
            b[0] = j;
            if(are_connected(a, b) and vis[i][j] == 0) {
                vis[i][j] = 1;
                vis[j][i] = 1;
                v[i].push_back(j);
                v[j].push_back(i);
            }
        }
    }
    v1.clear();
    int mx = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            vi[j] = 0;
            c[j] = 0;
        }
        k = y = 0;
        c[i] = 1;
        dfs(i);
        if(k > mx){
            mx = k;
            v1.clear();
            df(y);
        }
    }
    reverse(v1.begin(), v1.end());
    return v1;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 226 ms 3356 KB Output is correct

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2392 KB Output is correct
2 Correct 27 ms 2392 KB Output is correct
3 Correct 131 ms 2392 KB Output is correct
4 Correct 429 ms 2732 KB Output is correct
5 Correct 957 ms 3056 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2392 KB Output is correct
2 Correct 22 ms 2392 KB Output is correct
3 Correct 177 ms 2648 KB Output is correct
4 Correct 456 ms 2736 KB Output is correct
5 Correct 815 ms 2956 KB Output is correct
6 Correct 10 ms 2392 KB Output is correct
7 Correct 24 ms 2392 KB Output is correct
8 Correct 161 ms 2608 KB Output is correct
9 Correct 295 ms 2964 KB Output is correct
10 Correct 866 ms 3192 KB Output is correct
11 Correct 975 ms 2980 KB Output is correct
12 Correct 999 ms 3280 KB Output is correct
13 Correct 973 ms 3128 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2392 KB Output is correct
2 Correct 21 ms 2392 KB Output is correct
3 Correct 147 ms 2648 KB Output is correct
4 Correct 476 ms 2732 KB Output is correct
5 Correct 880 ms 3488 KB Output is correct
6 Correct 8 ms 2392 KB Output is correct
7 Correct 30 ms 2392 KB Output is correct
8 Correct 177 ms 2392 KB Output is correct
9 Correct 340 ms 2648 KB Output is correct
10 Correct 932 ms 3108 KB Output is correct
11 Correct 937 ms 3644 KB Output is correct
12 Correct 942 ms 3404 KB Output is correct
13 Correct 943 ms 3492 KB Output is correct
14 Correct 7 ms 2392 KB Output is correct
15 Correct 9 ms 2392 KB Output is correct
16 Correct 28 ms 2392 KB Output is correct
17 Correct 106 ms 2392 KB Output is correct
18 Correct 151 ms 2392 KB Output is correct
19 Correct 335 ms 3192 KB Output is correct
20 Correct 325 ms 2956 KB Output is correct
21 Correct 948 ms 3248 KB Output is correct
22 Correct 888 ms 3232 KB Output is correct
23 Correct 955 ms 2988 KB Output is correct
24 Correct 909 ms 2896 KB Output is correct
25 Correct 11 ms 2644 KB Output is correct
26 Correct 9 ms 2392 KB Output is correct
27 Correct 23 ms 2392 KB Output is correct
28 Correct 30 ms 2392 KB Output is correct
29 Correct 46 ms 2392 KB Output is correct
30 Correct 206 ms 2392 KB Output is correct
31 Correct 176 ms 2388 KB Output is correct
32 Correct 216 ms 2392 KB Output is correct
33 Correct 345 ms 2648 KB Output is correct
34 Correct 326 ms 2648 KB Output is correct
35 Correct 298 ms 2716 KB Output is correct
36 Correct 917 ms 3008 KB Output is correct
37 Correct 913 ms 3208 KB Output is correct
38 Correct 893 ms 3212 KB Output is correct
39 Correct 899 ms 3664 KB Output is correct
40 Correct 855 ms 3548 KB Output is correct
41 Correct 889 ms 2952 KB Output is correct
42 Correct 930 ms 2900 KB Output is correct
43 Correct 862 ms 3424 KB Output is correct
44 Correct 894 ms 3424 KB Output is correct
45 Correct 14 ms 2392 KB Output is correct
46 Correct 7 ms 2392 KB Output is correct
47 Correct 17 ms 2392 KB Output is correct
48 Correct 29 ms 2392 KB Output is correct
49 Correct 21 ms 2388 KB Output is correct
50 Correct 205 ms 2392 KB Output is correct
51 Correct 177 ms 2648 KB Output is correct
52 Correct 193 ms 2608 KB Output is correct
53 Correct 349 ms 2680 KB Output is correct
54 Correct 325 ms 2896 KB Output is correct
55 Correct 315 ms 2648 KB Output is correct
56 Correct 906 ms 3060 KB Output is correct
57 Correct 902 ms 3112 KB Output is correct
58 Correct 899 ms 3264 KB Output is correct
59 Correct 878 ms 3152 KB Output is correct
60 Correct 910 ms 3808 KB Output is correct
61 Correct 892 ms 3232 KB Output is correct
62 Correct 889 ms 3040 KB Output is correct
63 Correct 858 ms 3364 KB Output is correct
64 Correct 903 ms 3348 KB Output is correct

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2392 KB Output is correct
2 Correct 19 ms 2392 KB Output is correct
3 Partially correct 131 ms 2856 KB Output is partially correct
4 Partially correct 428 ms 2956 KB Output is partially correct
5 Partially correct 907 ms 3408 KB Output is partially correct
6 Correct 5 ms 2392 KB Output is correct
7 Correct 19 ms 2392 KB Output is correct
8 Partially correct 158 ms 2392 KB Output is partially correct
9 Partially correct 316 ms 2648 KB Output is partially correct
10 Partially correct 951 ms 2988 KB Output is partially correct
11 Partially correct 866 ms 3144 KB Output is partially correct
12 Partially correct 943 ms 3256 KB Output is partially correct
13 Partially correct 850 ms 2964 KB Output is partially correct
14 Correct 6 ms 2392 KB Output is correct
15 Correct 11 ms 2392 KB Output is correct
16 Incorrect 6 ms 2392 KB Incorrect
17 Halted 0 ms 0 KB -