oj.uz

Submission #979998

# Submission time Handle Problem Language Result Execution time Memory
979998 2024-05-11T19:06:49 Z vjudge1 Longest Trip (IOI23_longesttrip) C++17
15 / 100
 895 ms 2780 KB 
#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector <int>;
using vll = vector <ll>;

const ll MAXN = 256;
vll adj[MAXN];
ll mat[MAXN][MAXN];

// diameter common fishel L
pair <ll, vi> bfs (ll n, ll u) {
    vector <char> vis(n, false);
    vll dis(n), from(n);
    queue <ll> q;
    vis[u] = true;
    dis[u] = 0;
    from[u] = u;
    q.push(u);
    ll far = u;
    while (q.size()) {
        ll u = q.front(); q.pop();
        for (ll v : adj[u]) {
            if (vis[v]) continue;
            vis[v] = true;
            dis[v] = dis[u]+1;
            from[v] = u;
            q.push(v);
            far = v;
        }
    }
    ll ffar = far;
    vi path;
    while (far != from[far]) {
        path.push_back(far);
        far = from[far];
    }
    path.push_back(far);
    return { ffar, path };
}

vi longest_trip (int n, int d) {
    fill(adj, adj+n, vll({}));
    for (ll u = 0; u < n; u++) {
        for (ll v = u+1; v < n; v++) {
            if (are_connected(vi({ int(u) }), vi({ int(v) }))) {
                adj[u].push_back(v);
                adj[v].push_back(u);
                mat[u][v] = true;
                mat[v][u] = true;
            } else {
                mat[u][v] = false;
                mat[v][u] = false;
            }
        }
    }
    vi ans = {};
    for (ll u = 0; u < n; u++) {
        vi path = bfs(n, bfs(n, 0).first).second;
        if (path.size() > ans.size()) ans = path;
    }
    deque <int> dq;
    for (ll i : ans) dq.push_back(i);
    ll ex1 = dq.front(), ex2 = dq.back();
    vector <char> vis(n, false);
    for (ll u : dq) vis[u] = true;
    for (ll k = 0; k < n; k++) {
        for (ll u = 0; u < n; u++) {
            if (vis[u]) continue;
            vis[u] = true;
            if (mat[u][ex1]) {
                dq.push_front(u);
                ex1 = u;
            } else if (mat[u][ex2]) {
                dq.push_back(u);
                ex2 = u;
            } else vis[u] = false;
        }
    }
    ans = {};
    for (ll i : dq) ans.push_back(i);
    return ans;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 344 KB Output is correct
2 Correct 22 ms 344 KB Output is correct
3 Correct 127 ms 856 KB Output is correct
4 Correct 375 ms 1372 KB Output is correct
5 Correct 841 ms 2512 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 596 KB Output is correct
2 Correct 25 ms 344 KB Output is correct
3 Correct 126 ms 600 KB Output is correct
4 Correct 377 ms 1408 KB Output is correct
5 Correct 845 ms 2400 KB Output is correct
6 Correct 10 ms 344 KB Output is correct
7 Correct 26 ms 344 KB Output is correct
8 Correct 127 ms 600 KB Output is correct
9 Correct 303 ms 1384 KB Output is correct
10 Correct 845 ms 2328 KB Output is correct
11 Correct 877 ms 2648 KB Output is correct
12 Correct 788 ms 2416 KB Output is correct
13 Correct 893 ms 2176 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 28 ms 340 KB Output is correct
3 Correct 146 ms 860 KB Output is correct
4 Correct 412 ms 1188 KB Output is correct
5 Correct 866 ms 2352 KB Output is correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 20 ms 344 KB Output is correct
8 Correct 127 ms 856 KB Output is correct
9 Correct 269 ms 1636 KB Output is correct
10 Correct 854 ms 2128 KB Output is correct
11 Correct 844 ms 1904 KB Output is correct
12 Correct 895 ms 2128 KB Output is correct
13 Correct 819 ms 2204 KB Output is correct
14 Correct 8 ms 344 KB Output is correct
15 Incorrect 2 ms 344 KB Incorrect
16 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 110 ms 600 KB Output is partially correct
4 Partially correct 366 ms 1564 KB Output is partially correct
5 Partially correct 887 ms 2232 KB Output is partially correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 21 ms 344 KB Output is correct
8 Partially correct 123 ms 344 KB Output is partially correct
9 Partially correct 283 ms 1692 KB Output is partially correct
10 Partially correct 857 ms 2548 KB Output is partially correct
11 Partially correct 841 ms 2780 KB Output is partially correct
12 Partially correct 865 ms 2496 KB Output is partially correct
13 Partially correct 856 ms 2464 KB Output is partially correct
14 Incorrect 0 ms 344 KB Incorrect
15 Halted 0 ms 0 KB -