oj.uz

Submission #980229

# Submission time Handle Problem Language Result Execution time Memory
980229 2024-05-12T01:25:26 Z vjudge1 Longest Trip (IOI23_longesttrip) C++17
15 / 100
 807 ms 2600 KB 
#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using dll = deque <ll>;
using vi = vector <int>;

const ll MAXN = 256+16;
vll adj[MAXN];
bool mat[MAXN][MAXN];
ll comp[MAXN];

void dfs (ll u, ll col, ll &sz) {
    if (comp[u]) return;
    comp[u] = col;
    sz++;
    for (ll v : adj[u]) {
        dfs(v, col, sz);
    }
}

vi longest_trip (int n, int d) {
    fill(adj, adj+n+5, vll({}));
    fill(comp, comp+n+5, 0);
    for (ll u = 0; u < n; u++) {
        mat[u][u] = false;
        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;
            }
        }
    }
    ll c = 1;
    vll sz;
    for (ll u = 0; u < n; u++) {
        if (comp[u]) continue;
        sz.push_back(0);
        dfs(u, c++, sz.back());
    }
    assert(c == 2 || c == 3);
    if (c == 2) {
        vll fr, bk;
        fr.push_back(0);
        vector <char> vis(n, false);
        vis[0] = true;
        for (ll v = 0; v < n; v++) {
            if (mat[0][v]) {
                vis[v] = true;
                bk.push_back(v);
                break;
            }
        }
        assert(fr.size() == 1);
        assert(bk.size() == 1);
        ll skip = 0;
        for (ll u = 1; u < n; u++) {
            if (u == fr[0] || u == bk[0]) { skip++; continue; }
            if (mat[u][fr.back()]) {
                fr.push_back(u);
            } else if (mat[u][bk.back()]) {
                bk.push_back(u);
            } else assert(false);
        }
        // assert(skip == 0);
        vi ans(fr.rbegin(), fr.rend());
        for (ll i : bk) ans.push_back(i);
        return ans;
    } else if (c == 3) {
        assert(sz.size() == 2);
        if (sz[0] > sz[1]) {
            vi ans;
            for (ll u = 0; u < n; u++) {
                if (comp[u] == 1) {
                    ans.push_back(u);
                }
            }
            return ans;
        } else {
            vi ans;
            for (ll u = 0; u < n; u++) {
                if (comp[u] == 2) {
                    ans.push_back(u);
                }
            }
            return ans;
        }
    }
}

Compilation message

longesttrip.cpp: In function 'vi longest_trip(int, int)':
longesttrip.cpp:41:9: warning: control reaches end of non-void function [-Wreturn-type]
   41 |     vll sz;
      |         ^~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Runtime error 157 ms 2600 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 19 ms 600 KB Output is correct
3 Correct 120 ms 856 KB Output is correct
4 Correct 331 ms 1508 KB Output is correct
5 Correct 723 ms 1888 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 21 ms 344 KB Output is correct
3 Correct 108 ms 600 KB Output is correct
4 Correct 346 ms 1624 KB Output is correct
5 Correct 694 ms 1496 KB Output is correct
6 Correct 6 ms 344 KB Output is correct
7 Correct 19 ms 344 KB Output is correct
8 Correct 118 ms 600 KB Output is correct
9 Correct 252 ms 1504 KB Output is correct
10 Correct 729 ms 1960 KB Output is correct
11 Correct 777 ms 1820 KB Output is correct
12 Correct 784 ms 2160 KB Output is correct
13 Correct 683 ms 2120 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 344 KB Output is correct
2 Correct 23 ms 596 KB Output is correct
3 Correct 127 ms 732 KB Output is correct
4 Correct 375 ms 1372 KB Output is correct
5 Correct 707 ms 1920 KB Output is correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 26 ms 344 KB Output is correct
8 Correct 122 ms 984 KB Output is correct
9 Correct 259 ms 1276 KB Output is correct
10 Correct 694 ms 1676 KB Output is correct
11 Correct 697 ms 1652 KB Output is correct
12 Correct 680 ms 1676 KB Output is correct
13 Correct 718 ms 1752 KB Output is correct
14 Correct 7 ms 344 KB Output is correct
15 Runtime error 2 ms 452 KB Execution killed with signal 6
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 600 KB Output is correct
3 Partially correct 108 ms 864 KB Output is partially correct
4 Partially correct 382 ms 1140 KB Output is partially correct
5 Partially correct 807 ms 1656 KB Output is partially correct
6 Correct 6 ms 344 KB Output is correct
7 Correct 27 ms 344 KB Output is correct
8 Partially correct 114 ms 984 KB Output is partially correct
9 Partially correct 289 ms 856 KB Output is partially correct
10 Partially correct 749 ms 1872 KB Output is partially correct
11 Partially correct 708 ms 1780 KB Output is partially correct
12 Partially correct 766 ms 1828 KB Output is partially correct
13 Partially correct 721 ms 2160 KB Output is partially correct
14 Correct 7 ms 344 KB Output is correct
15 Runtime error 2 ms 600 KB Execution killed with signal 6
16 Halted 0 ms 0 KB -