oj.uz

Submission #960323

# Submission time Handle Problem Language Result Execution time Memory
960323 2024-04-10T09:16:50 Z TAhmed33 Longest Trip (IOI23_longesttrip) C++17
15 / 100
 769 ms 1648 KB 
#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
vector <int> adj[256], tree[256];
bool vis[256];
struct DSU {
    int p[256], sze[256];
    void init (int n) {
        for (int i = 0; i < n; i++) {
            p[i] = i; sze[i] = 1;
        }
    }
    int find (int x) {
        return p[x] == x ? x : p[x] = find(p[x]);
    }
    bool merge (int a, int b) {
        a = find(a), b = find(b);
        if (a == b) return 0;
        if (sze[a] > sze[b]) swap(a, b);
        sze[b] += sze[a]; p[a] = b;
        return 1;
    }
} cur;
vector <int> x;
int p[256];
void dfs (int pos) {
    vis[pos] = 1; x.push_back(pos);
    for (auto j : adj[pos]) {
        if (vis[j]) continue;
        tree[pos].push_back(j);
        p[j] = pos;
        dfs(j);
    }
}
int get (int x) {
    if (tree[x].empty()) return x;
    return get(tree[x][0]);
}
vector <int> longest_trip (int n, int d) {
    for (int i = 0; i < n; i++) adj[i].clear(), tree[i].clear();
    memset(p, -1, sizeof(p));
    cur.init(n);
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (are_connected({i}, {j})) {
                adj[i].push_back(j);
                adj[j].push_back(i);
                cur.merge(i, j);
            }
        }
    }
    bool flag = 0;
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            flag |= cur.merge(i, j);
        }
    }
    if (flag) {
        memset(vis, 0, sizeof(vis));
        vector <int> ret; 
        for (int i = 0; i < n; i++) {
            if (!vis[i]) {
                x.clear(); dfs(i);
                if ((int)x.size() > (int)ret.size()) ret = x;
            }
        }
        return ret;
    }
    memset(vis, 0, sizeof(vis));
    x.clear(); dfs(0);
    int pos = -1;
    for (int i = 0; i < n; i++) {
        if ((int)tree[i].size() == 2) {
            assert(pos == -1);
            pos = i;
        }
    }
    if (pos == -1) return x;
    int u = get(tree[pos][0]), v = get(tree[pos][1]);
    if (p[pos] != -1 && find(adj[p[pos]].begin(), adj[p[pos]].end(), u) == adj[p[pos]].end()) swap(u, v);
    auto g = find(x.begin(), x.end(), pos) - x.begin();
    x.erase(x.begin() + g);
    g = find(x.begin(), x.end(), u) - x.begin(); g++;
    x.insert(x.begin() + g, pos);
    return x;   
}

Subtask #0
0.0 / 0.0

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

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 120 ms 852 KB Output is correct
4 Correct 351 ms 980 KB Output is correct
5 Correct 736 ms 1512 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 19 ms 344 KB Output is correct
3 Correct 109 ms 856 KB Output is correct
4 Correct 351 ms 1372 KB Output is correct
5 Correct 769 ms 1068 KB Output is correct
6 Correct 6 ms 344 KB Output is correct
7 Correct 20 ms 344 KB Output is correct
8 Correct 119 ms 856 KB Output is correct
9 Correct 259 ms 980 KB Output is correct
10 Correct 716 ms 1620 KB Output is correct
11 Correct 754 ms 1400 KB Output is correct
12 Correct 713 ms 1648 KB Output is correct
13 Correct 716 ms 1236 KB Output is correct

Subtask #3
0.0 / 25.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 134 ms 856 KB Output is correct
4 Correct 355 ms 860 KB Output is correct
5 Correct 749 ms 1336 KB Output is correct
6 Correct 9 ms 500 KB Output is correct
7 Correct 21 ms 344 KB Output is correct
8 Correct 128 ms 964 KB Output is correct
9 Correct 247 ms 876 KB Output is correct
10 Correct 736 ms 1040 KB Output is correct
11 Correct 754 ms 1424 KB Output is correct
12 Correct 756 ms 1512 KB Output is correct
13 Correct 758 ms 1580 KB Output is correct
14 Correct 7 ms 344 KB Output is correct
15 Correct 10 ms 344 KB Output is correct
16 Incorrect 2 ms 344 KB Incorrect
17 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 22 ms 344 KB Output is correct
3 Partially correct 168 ms 856 KB Output is partially correct
4 Partially correct 356 ms 1472 KB Output is partially correct
5 Partially correct 709 ms 1136 KB Output is partially correct
6 Correct 6 ms 344 KB Output is correct
7 Correct 25 ms 344 KB Output is correct
8 Partially correct 125 ms 600 KB Output is partially correct
9 Partially correct 288 ms 1212 KB Output is partially correct
10 Partially correct 732 ms 1368 KB Output is partially correct
11 Partially correct 750 ms 1624 KB Output is partially correct
12 Partially correct 717 ms 1616 KB Output is partially correct
13 Partially correct 767 ms 1560 KB Output is partially correct
14 Correct 6 ms 344 KB Output is correct
15 Correct 10 ms 344 KB Output is correct
16 Incorrect 2 ms 344 KB Incorrect
17 Halted 0 ms 0 KB -