oj.uz

Submission #1056849

# Submission time Handle Problem Language Result Execution time Memory
1056849 2024-08-13T11:46:00 Z perekopskad Longest Trip (IOI23_longesttrip) C++17
5 / 100
 816 ms 2024 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

#define el '\n'
#define ff first
#define ss second
#define pii pair <ll, ll>
#define pb push_back
#define mkp make_pair
#define fr(i, l, r) for(ll i = l; i <= r; i++)
#define debug(x) \
    { cout << #x << " = " << x << el; }

template<class T, class S>
inline bool chmax(T &a, const S &b) {
    return (a < b ? a = b, 1 : 0);
}

template<class T, class S>
inline bool chmin(T &a, const S &b) {
    return (a > b ? a = b, 1 : 0);
}

const ll N = 310;
const ll M = 1e5 + 10;
const ll K = 400;
const ll INF = 1e18 + 10;
const ll inf = 1e9 + 10;
const ll LOG = 20;
const ll mod = 1000002022;
mt19937 rnd(time(0));

bool used[N];
vector <int> g[N], vv;

bool are_connected(std::vector<int> A, std::vector<int> B);

void dfs(int v) {
    vv.pb(v);
    used[v] = 1;
    for(int u : g[v]) {
        if(!used[u]) dfs(u);
    }
}

std::vector<int> longest_trip(int N, int D) {
    if(D == 3) {
        vector <int> v;
        fr(i, 0, N - 1)
            v.pb(i);
        return v;
    }

    for(int i = 0; i < N; i++) {
        for(int j = i + 1; j < N; j++) {
            if(are_connected({i}, {j})) {
                g[i].pb(j);
                g[j].pb(i);
            }
        }
    }

    vector <int> ans;
    for(int i = 0; i < N; i++) {
        fill(used, used + N, 0);
        vv.clear();
        dfs(i);
        if(vv.size() > ans.size())
            ans = vv;
    }
    return ans;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 21 ms 704 KB Output is correct
3 Correct 156 ms 592 KB Output is correct
4 Correct 373 ms 1112 KB Output is correct
5 Correct 806 ms 1504 KB Output is correct
6 Incorrect 0 ms 344 KB Incorrect
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 456 KB Output is correct
2 Correct 22 ms 344 KB Output is correct
3 Correct 141 ms 676 KB Output is correct
4 Correct 385 ms 996 KB Output is correct
5 Correct 816 ms 2024 KB Output is correct
6 Incorrect 0 ms 344 KB Incorrect
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 456 KB Output is correct
2 Correct 29 ms 488 KB Output is correct
3 Partially correct 146 ms 664 KB Output is partially correct
4 Partially correct 406 ms 1372 KB Output is partially correct
5 Partially correct 777 ms 1748 KB Output is partially correct
6 Incorrect 0 ms 344 KB Incorrect
7 Halted 0 ms 0 KB -