oj.uz

Submission #960317

# Submission time Handle Problem Language Result Execution time Memory
960317 2024-04-10T08:53:28 Z TAhmed33 Longest Trip (IOI23_longesttrip) C++17
5 / 100
 787 ms 1668 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;
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);
        dfs(j);
    }
}
void dfs2 (int pos, bool c = 0) {
    if (c) {
        x.push_back(pos);
        for (auto j : tree[pos]) dfs2(j, c);
    } else {
        if (tree[pos].empty()) {
            x.push_back(pos);
            return;
        }
        for (auto j : adj[pos]) {
            dfs2(j, 0);
            if (adj[pos].size() == 2) c = 1;
        }
        if (adj[pos].size() == 1) x.push_back(pos);
    }
}
vector <int> longest_trip (int n, int d) {
    for (int i = 0; i < n; i++) adj[i].clear(), tree[i].clear();
    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 (tree[i].size() == 2) {
            pos = i;
        }
    }
    if (pos == -1) {
        return x;
    }
    x.clear(); dfs2(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 179 ms 1612 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 28 ms 344 KB Output is correct
3 Correct 142 ms 856 KB Output is correct
4 Correct 379 ms 848 KB Output is correct
5 Correct 774 ms 1304 KB Output is correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 344 KB Output is correct
2 Correct 22 ms 344 KB Output is correct
3 Correct 130 ms 720 KB Output is correct
4 Correct 355 ms 992 KB Output is correct
5 Correct 747 ms 1668 KB Output is correct
6 Incorrect 1 ms 516 KB Incorrect
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.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 135 ms 608 KB Output is correct
4 Correct 361 ms 884 KB Output is correct
5 Correct 753 ms 1268 KB Output is correct
6 Incorrect 0 ms 344 KB Incorrect
7 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 30 ms 344 KB Output is correct
3 Partially correct 110 ms 856 KB Output is partially correct
4 Partially correct 350 ms 988 KB Output is partially correct
5 Partially correct 787 ms 1240 KB Output is partially correct
6 Incorrect 0 ms 344 KB Incorrect
7 Halted 0 ms 0 KB -