oj.uz

Submission #992851

# Submission time Handle Problem Language Result Execution time Memory
992851 2024-06-05T07:52:23 Z Muhammet Longest Trip (IOI23_longesttrip) C++17
40 / 100
 960 ms 3784 KB 
#include <bits/stdc++.h>
#include "longesttrip.h"

#define N 3005

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] = 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;
}

Compilation message

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:60:49: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   60 |         for(int j = 0; j < n; j++) vi[j] = c[j] = 0;
      |                                            ~~~~~^~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 210 ms 3528 KB Output is correct

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 26 ms 344 KB Output is correct
3 Correct 137 ms 600 KB Output is correct
4 Correct 422 ms 2776 KB Output is correct
5 Correct 899 ms 2988 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 344 KB Output is correct
2 Correct 22 ms 344 KB Output is correct
3 Correct 120 ms 600 KB Output is correct
4 Correct 482 ms 2904 KB Output is correct
5 Correct 910 ms 3156 KB Output is correct
6 Correct 8 ms 344 KB Output is correct
7 Correct 24 ms 344 KB Output is correct
8 Correct 147 ms 688 KB Output is correct
9 Correct 341 ms 2764 KB Output is correct
10 Correct 845 ms 3164 KB Output is correct
11 Correct 940 ms 3080 KB Output is correct
12 Correct 855 ms 3336 KB Output is correct
13 Correct 908 ms 3524 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 21 ms 344 KB Output is correct
3 Correct 134 ms 600 KB Output is correct
4 Correct 462 ms 2760 KB Output is correct
5 Correct 923 ms 3152 KB Output is correct
6 Correct 8 ms 344 KB Output is correct
7 Correct 22 ms 344 KB Output is correct
8 Correct 158 ms 600 KB Output is correct
9 Correct 313 ms 2772 KB Output is correct
10 Correct 886 ms 3108 KB Output is correct
11 Correct 823 ms 3100 KB Output is correct
12 Correct 875 ms 3372 KB Output is correct
13 Correct 894 ms 3160 KB Output is correct
14 Correct 10 ms 340 KB Output is correct
15 Correct 11 ms 344 KB Output is correct
16 Correct 38 ms 344 KB Output is correct
17 Correct 103 ms 600 KB Output is correct
18 Correct 151 ms 856 KB Output is correct
19 Correct 337 ms 2648 KB Output is correct
20 Correct 308 ms 2644 KB Output is correct
21 Correct 940 ms 3376 KB Output is correct
22 Correct 909 ms 3024 KB Output is correct
23 Correct 881 ms 3348 KB Output is correct
24 Correct 960 ms 3288 KB Output is correct
25 Correct 9 ms 344 KB Output is correct
26 Correct 9 ms 344 KB Output is correct
27 Correct 20 ms 344 KB Output is correct
28 Correct 30 ms 344 KB Output is correct
29 Correct 24 ms 344 KB Output is correct
30 Correct 190 ms 2752 KB Output is correct
31 Correct 171 ms 2748 KB Output is correct
32 Correct 190 ms 2748 KB Output is correct
33 Correct 341 ms 2896 KB Output is correct
34 Correct 339 ms 2896 KB Output is correct
35 Correct 323 ms 2904 KB Output is correct
36 Correct 946 ms 3152 KB Output is correct
37 Correct 891 ms 3036 KB Output is correct
38 Correct 888 ms 3040 KB Output is correct
39 Correct 842 ms 3552 KB Output is correct
40 Correct 958 ms 3112 KB Output is correct
41 Correct 846 ms 2896 KB Output is correct
42 Correct 866 ms 3244 KB Output is correct
43 Correct 851 ms 3252 KB Output is correct
44 Correct 914 ms 3260 KB Output is correct
45 Correct 6 ms 344 KB Output is correct
46 Correct 8 ms 344 KB Output is correct
47 Correct 20 ms 344 KB Output is correct
48 Correct 27 ms 344 KB Output is correct
49 Correct 18 ms 344 KB Output is correct
50 Correct 202 ms 2904 KB Output is correct
51 Correct 213 ms 2896 KB Output is correct
52 Correct 211 ms 2740 KB Output is correct
53 Correct 295 ms 2768 KB Output is correct
54 Correct 328 ms 2648 KB Output is correct
55 Correct 322 ms 2648 KB Output is correct
56 Correct 916 ms 3408 KB Output is correct
57 Correct 886 ms 3744 KB Output is correct
58 Correct 907 ms 3784 KB Output is correct
59 Correct 907 ms 3272 KB Output is correct
60 Correct 898 ms 3424 KB Output is correct
61 Correct 869 ms 3080 KB Output is correct
62 Correct 815 ms 3036 KB Output is correct
63 Correct 786 ms 3328 KB Output is correct
64 Correct 814 ms 3612 KB Output is correct

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 26 ms 344 KB Output is correct
3 Partially correct 139 ms 600 KB Output is partially correct
4 Partially correct 392 ms 2768 KB Output is partially correct
5 Partially correct 822 ms 3168 KB Output is partially correct
6 Correct 8 ms 344 KB Output is correct
7 Correct 27 ms 344 KB Output is correct
8 Partially correct 93 ms 600 KB Output is partially correct
9 Partially correct 307 ms 2648 KB Output is partially correct
10 Partially correct 853 ms 3292 KB Output is partially correct
11 Partially correct 838 ms 3340 KB Output is partially correct
12 Partially correct 868 ms 3076 KB Output is partially correct
13 Partially correct 782 ms 3172 KB Output is partially correct
14 Correct 7 ms 344 KB Output is correct
15 Correct 17 ms 552 KB Output is correct
16 Incorrect 11 ms 344 KB Incorrect
17 Halted 0 ms 0 KB -