oj.uz

Submission #980214

# Submission time Handle Problem Language Result Execution time Memory
980214 2024-05-12T01:16:41 Z vjudge1 Longest Trip (IOI23_longesttrip) C++17
15 / 100
 801 ms 2492 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());
    }
    if (c == 2) {
        dll dq;
        dq.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;
                dq.push_back(v);
                break;
            }
        }
        assert(dq.size() == 2);
        for (ll u = 0; u < n; u++) {
            if (vis[u]) continue;
            vis[u] = true;
            if (mat[u][dq.front()]) {
                dq.push_front(u);
            } else if (mat[u][dq.back()]) {
                dq.push_back(u);
            }
        }
        vi ans(dq.begin(), dq.end());
        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 0 ms 344 KB Output is correct
2 Incorrect 173 ms 1608 KB Incorrect
3 Halted 0 ms 0 KB -

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 22 ms 344 KB Output is correct
3 Correct 118 ms 856 KB Output is correct
4 Correct 391 ms 856 KB Output is correct
5 Correct 746 ms 1832 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 23 ms 344 KB Output is correct
3 Correct 134 ms 984 KB Output is correct
4 Correct 346 ms 1176 KB Output is correct
5 Correct 769 ms 1880 KB Output is correct
6 Correct 8 ms 344 KB Output is correct
7 Correct 33 ms 596 KB Output is correct
8 Correct 133 ms 1112 KB Output is correct
9 Correct 289 ms 1112 KB Output is correct
10 Correct 696 ms 1768 KB Output is correct
11 Correct 801 ms 1872 KB Output is correct
12 Correct 762 ms 1856 KB Output is correct
13 Correct 762 ms 1752 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 344 KB Output is correct
3 Correct 129 ms 860 KB Output is correct
4 Correct 327 ms 1112 KB Output is correct
5 Correct 745 ms 1456 KB Output is correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 25 ms 344 KB Output is correct
8 Correct 125 ms 1112 KB Output is correct
9 Correct 252 ms 1148 KB Output is correct
10 Correct 747 ms 1496 KB Output is correct
11 Correct 766 ms 1472 KB Output is correct
12 Correct 735 ms 2040 KB Output is correct
13 Correct 793 ms 1908 KB Output is correct
14 Correct 8 ms 344 KB Output is correct
15 Correct 11 ms 344 KB Output is correct
16 Correct 37 ms 344 KB Output is correct
17 Correct 78 ms 600 KB Output is correct
18 Correct 126 ms 856 KB Output is correct
19 Correct 277 ms 1360 KB Output is correct
20 Correct 279 ms 1264 KB Output is correct
21 Correct 747 ms 1860 KB Output is correct
22 Correct 757 ms 2360 KB Output is correct
23 Correct 696 ms 2008 KB Output is correct
24 Correct 755 ms 1716 KB Output is correct
25 Correct 11 ms 344 KB Output is correct
26 Correct 8 ms 344 KB Output is correct
27 Correct 23 ms 344 KB Output is correct
28 Correct 23 ms 344 KB Output is correct
29 Correct 27 ms 344 KB Output is correct
30 Correct 170 ms 704 KB Output is correct
31 Correct 174 ms 952 KB Output is correct
32 Correct 153 ms 704 KB Output is correct
33 Correct 293 ms 1036 KB Output is correct
34 Correct 284 ms 1272 KB Output is correct
35 Correct 270 ms 1308 KB Output is correct
36 Correct 753 ms 2100 KB Output is correct
37 Correct 787 ms 1816 KB Output is correct
38 Correct 715 ms 1752 KB Output is correct
39 Correct 725 ms 1872 KB Output is correct
40 Correct 740 ms 1408 KB Output is correct
41 Correct 753 ms 1124 KB Output is correct
42 Correct 762 ms 1184 KB Output is correct
43 Correct 702 ms 2220 KB Output is correct
44 Correct 677 ms 2492 KB Output is correct
45 Correct 9 ms 344 KB Output is correct
46 Correct 9 ms 344 KB Output is correct
47 Correct 21 ms 344 KB Output is correct
48 Correct 21 ms 344 KB Output is correct
49 Correct 23 ms 344 KB Output is correct
50 Correct 158 ms 504 KB Output is correct
51 Incorrect 12 ms 968 KB Incorrect
52 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 340 KB Output is correct
2 Correct 21 ms 344 KB Output is correct
3 Partially correct 126 ms 856 KB Output is partially correct
4 Partially correct 381 ms 1284 KB Output is partially correct
5 Partially correct 726 ms 1760 KB Output is partially correct
6 Correct 6 ms 344 KB Output is correct
7 Correct 29 ms 600 KB Output is correct
8 Partially correct 121 ms 852 KB Output is partially correct
9 Partially correct 249 ms 1324 KB Output is partially correct
10 Partially correct 745 ms 2184 KB Output is partially correct
11 Partially correct 690 ms 1660 KB Output is partially correct
12 Partially correct 735 ms 1480 KB Output is partially correct
13 Partially correct 692 ms 2368 KB Output is partially correct
14 Correct 7 ms 340 KB Output is correct
15 Incorrect 2 ms 344 KB Incorrect
16 Halted 0 ms 0 KB -