oj.uz

Submission #1007065

# Submission time Handle Problem Language Result Execution time Memory
1007065 2024-06-24T11:21:00 Z 3as8 Longest Trip (IOI23_longesttrip) C++17
15 / 100
 839 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;
        }

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

    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 189 ms 488 KB Output is correct

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 344 KB Output is correct
2 Correct 21 ms 344 KB Output is correct
3 Correct 146 ms 344 KB Output is correct
4 Correct 388 ms 452 KB Output is correct
5 Correct 795 ms 500 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 22 ms 344 KB Output is correct
3 Correct 139 ms 344 KB Output is correct
4 Correct 380 ms 456 KB Output is correct
5 Correct 796 ms 488 KB Output is correct
6 Correct 5 ms 344 KB Output is correct
7 Correct 14 ms 344 KB Output is correct
8 Correct 142 ms 344 KB Output is correct
9 Correct 301 ms 448 KB Output is correct
10 Correct 783 ms 492 KB Output is correct
11 Correct 797 ms 496 KB Output is correct
12 Correct 818 ms 488 KB Output is correct
13 Correct 754 ms 496 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 20 ms 344 KB Output is correct
3 Correct 138 ms 344 KB Output is correct
4 Correct 389 ms 344 KB Output is correct
5 Correct 775 ms 492 KB Output is correct
6 Correct 6 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 294 ms 452 KB Output is correct
10 Correct 839 ms 492 KB Output is correct
11 Correct 799 ms 492 KB Output is correct
12 Correct 824 ms 492 KB Output is correct
13 Correct 793 ms 492 KB Output is correct
14 Correct 5 ms 596 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 -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 18 ms 344 KB Output is correct
3 Partially correct 121 ms 344 KB Output is partially correct
4 Partially correct 390 ms 452 KB Output is partially correct
5 Partially correct 796 ms 492 KB Output is partially correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 25 ms 600 KB Output is correct
8 Partially correct 138 ms 344 KB Output is partially correct
9 Partially correct 295 ms 592 KB Output is partially correct
10 Partially correct 775 ms 492 KB Output is partially correct
11 Partially correct 760 ms 492 KB Output is partially correct
12 Partially correct 752 ms 488 KB Output is partially correct
13 Partially correct 815 ms 492 KB Output is partially correct
14 Correct 6 ms 344 KB Output is correct
15 Correct 14 ms 344 KB Output is correct
16 Incorrect 1 ms 344 KB Incorrect
17 Halted 0 ms 0 KB -