oj.uz

Submission #1007060

# Submission time Handle Problem Language Result Execution time Memory
1007060 2024-06-24T11:17:27 Z 3as8 Longest Trip (IOI23_longesttrip) C++17
15 / 100
 861 ms 600 KB 
#include "longesttrip.h"

#include<bits/stdc++.h>

#define ll long long
using namespace std;

bool con[300][300];
bool vis[300];
bool bkVis[300];

ll n;
ll l = 0;
void dfs(ll startIndex, vector<int>& curr) {


    vis[startIndex] = true;
    curr.push_back(startIndex);

    bool in = false;
    for(int i = 0; i < n; i++) {
        if(con[startIndex][i] && !vis[i]) {
            dfs(i, curr);
            in = true;
        }
    }

    if(!in) l = startIndex;
}


std::vector<int> longest_trip(int N, int D) {

    n = N;
    for(int i = 0; i < n; i++) {
        for(int j = i + 1; j < n; j++) {

            con[i][j] = con[j][i] = are_connected({i}, {j});
        }
    }

    ll mx = LLONG_MIN;
    vector<int> ans;

    for(int i = 0; i < n; i++) vis[i] = false;


    for(int i = 0; i < n; i++) {
        if(vis[i]) continue;

        for(int j = 0; j < n; j++) bkVis[j] = vis[j];


        vector<int> curr;
        l = i;
        dfs(i, curr);

        for(int j = 0; j < n; j++) vis[j] = bkVis[j];

        vector<int> curr2;

        dfs(l, curr2);

        if(curr2.size() > ans.size()) {
            ans = curr2;
        }
    }

    return ans;
}

Compilation message

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:42:8: warning: unused variable 'mx' [-Wunused-variable]
   42 |     ll mx = LLONG_MIN;
      |        ^~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 182 ms 496 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 29 ms 344 KB Output is correct
3 Correct 146 ms 344 KB Output is correct
4 Correct 417 ms 452 KB Output is correct
5 Correct 824 ms 492 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 25 ms 344 KB Output is correct
3 Correct 144 ms 344 KB Output is correct
4 Correct 396 ms 344 KB Output is correct
5 Correct 796 ms 492 KB Output is correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 28 ms 344 KB Output is correct
8 Correct 150 ms 344 KB Output is correct
9 Correct 297 ms 452 KB Output is correct
10 Correct 794 ms 600 KB Output is correct
11 Correct 846 ms 492 KB Output is correct
12 Correct 841 ms 492 KB Output is correct
13 Correct 803 ms 492 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 21 ms 344 KB Output is correct
3 Correct 128 ms 344 KB Output is correct
4 Correct 360 ms 448 KB Output is correct
5 Correct 842 ms 488 KB Output is correct
6 Correct 10 ms 344 KB Output is correct
7 Correct 21 ms 344 KB Output is correct
8 Correct 146 ms 344 KB Output is correct
9 Correct 303 ms 444 KB Output is correct
10 Correct 810 ms 492 KB Output is correct
11 Correct 781 ms 492 KB Output is correct
12 Correct 823 ms 496 KB Output is correct
13 Correct 716 ms 500 KB Output is correct
14 Correct 5 ms 344 KB Output is correct
15 Correct 9 ms 344 KB Output is correct
16 Incorrect 1 ms 344 KB Incorrect
17 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 136 ms 344 KB Output is partially correct
4 Partially correct 382 ms 456 KB Output is partially correct
5 Partially correct 826 ms 508 KB Output is partially correct
6 Correct 5 ms 344 KB Output is correct
7 Correct 19 ms 344 KB Output is correct
8 Partially correct 150 ms 344 KB Output is partially correct
9 Partially correct 323 ms 448 KB Output is partially correct
10 Partially correct 840 ms 500 KB Output is partially correct
11 Partially correct 861 ms 492 KB Output is partially correct
12 Partially correct 784 ms 496 KB Output is partially correct
13 Partially correct 812 ms 492 KB Output is partially correct
14 Correct 5 ms 344 KB Output is correct
15 Correct 10 ms 344 KB Output is correct
16 Incorrect 1 ms 344 KB Incorrect
17 Halted 0 ms 0 KB -