oj.uz

Submission #979988

# Submission time Handle Problem Language Result Execution time Memory
979988 2024-05-11T18:55:08 Z vjudge1 Longest Trip (IOI23_longesttrip) C++17
15 / 100
 983 ms 2592 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 u = 0; u < n; u++) {
        if (vis[u]) continue;
        if (mat[u][ex1]) {
            dq.push_front(u);
            ex1 = u;
        } else if (mat[u][ex2]) {
            dq.push_back(u);
            ex2 = u;
        }
    }
    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 1 ms 344 KB Output is correct
2 Incorrect 219 ms 2192 KB Incorrect
3 Halted 0 ms 0 KB -

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 344 KB Output is correct
2 Correct 27 ms 344 KB Output is correct
3 Correct 140 ms 852 KB Output is correct
4 Correct 442 ms 1640 KB Output is correct
5 Correct 942 ms 2480 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 24 ms 344 KB Output is correct
3 Correct 127 ms 856 KB Output is correct
4 Correct 408 ms 1112 KB Output is correct
5 Correct 926 ms 2588 KB Output is correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 22 ms 344 KB Output is correct
8 Correct 140 ms 856 KB Output is correct
9 Correct 287 ms 1212 KB Output is correct
10 Correct 934 ms 2372 KB Output is correct
11 Correct 936 ms 2456 KB Output is correct
12 Correct 934 ms 2592 KB Output is correct
13 Correct 915 ms 2392 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 340 KB Output is correct
2 Correct 23 ms 344 KB Output is correct
3 Correct 147 ms 828 KB Output is correct
4 Correct 413 ms 1508 KB Output is correct
5 Correct 891 ms 2272 KB Output is correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 24 ms 600 KB Output is correct
8 Correct 118 ms 600 KB Output is correct
9 Correct 316 ms 1712 KB Output is correct
10 Correct 972 ms 2528 KB Output is correct
11 Correct 974 ms 2100 KB Output is correct
12 Correct 955 ms 2108 KB Output is correct
13 Correct 965 ms 2076 KB Output is correct
14 Correct 7 ms 344 KB Output is correct
15 Incorrect 1 ms 344 KB Incorrect
16 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.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 Partially correct 123 ms 856 KB Output is partially correct
4 Partially correct 424 ms 1204 KB Output is partially correct
5 Partially correct 922 ms 2476 KB Output is partially correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 19 ms 344 KB Output is correct
8 Partially correct 139 ms 860 KB Output is partially correct
9 Partially correct 307 ms 1204 KB Output is partially correct
10 Partially correct 933 ms 2520 KB Output is partially correct
11 Partially correct 943 ms 2168 KB Output is partially correct
12 Partially correct 983 ms 2048 KB Output is partially correct
13 Partially correct 972 ms 2112 KB Output is partially correct
14 Incorrect 1 ms 344 KB Incorrect
15 Halted 0 ms 0 KB -