oj.uz

Submission #993047

# Submission time Handle Problem Language Result Execution time Memory
993047 2024-06-05T09:15:54 Z Muhammet Longest Trip (IOI23_longesttrip) C++17
15 / 100
 1000 ms 3560 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] = 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 344 KB Output is correct
2 Correct 209 ms 3560 KB Output is correct

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 22 ms 544 KB Output is correct
3 Correct 159 ms 600 KB Output is correct
4 Correct 415 ms 3028 KB Output is correct
5 Correct 898 ms 3232 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 344 KB Output is correct
2 Correct 33 ms 344 KB Output is correct
3 Correct 164 ms 680 KB Output is correct
4 Correct 443 ms 2904 KB Output is correct
5 Correct 882 ms 3420 KB Output is correct
6 Correct 8 ms 344 KB Output is correct
7 Correct 27 ms 344 KB Output is correct
8 Correct 181 ms 680 KB Output is correct
9 Correct 326 ms 3024 KB Output is correct
10 Correct 861 ms 3256 KB Output is correct
11 Correct 904 ms 3060 KB Output is correct
12 Correct 900 ms 3028 KB Output is correct
13 Correct 992 ms 3008 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 32 ms 428 KB Output is correct
3 Correct 149 ms 600 KB Output is correct
4 Correct 426 ms 2896 KB Output is correct
5 Correct 985 ms 3036 KB Output is correct
6 Correct 9 ms 344 KB Output is correct
7 Correct 26 ms 344 KB Output is correct
8 Correct 143 ms 600 KB Output is correct
9 Correct 349 ms 2648 KB Output is correct
10 Correct 927 ms 3188 KB Output is correct
11 Correct 894 ms 3464 KB Output is correct
12 Execution timed out 1002 ms 3268 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.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 Partially correct 142 ms 600 KB Output is partially correct
4 Partially correct 484 ms 3024 KB Output is partially correct
5 Partially correct 948 ms 3368 KB Output is partially correct
6 Correct 5 ms 344 KB Output is correct
7 Correct 27 ms 340 KB Output is correct
8 Partially correct 146 ms 600 KB Output is partially correct
9 Partially correct 368 ms 2768 KB Output is partially correct
10 Partially correct 928 ms 3320 KB Output is partially correct
11 Partially correct 950 ms 3160 KB Output is partially correct
12 Partially correct 904 ms 3080 KB Output is partially correct
13 Partially correct 906 ms 3268 KB Output is partially correct
14 Correct 9 ms 344 KB Output is correct
15 Correct 11 ms 344 KB Output is correct
16 Incorrect 8 ms 344 KB Incorrect
17 Halted 0 ms 0 KB -