oj.uz

Submission #960336

# Submission time Handle Problem Language Result Execution time Memory
960336 2024-04-10T09:26:51 Z TAhmed33 Longest Trip (IOI23_longesttrip) C++17
15 / 100
 819 ms 1900 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++) {
        assert((int)tree[i].size() <= 2);
        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);
    //if (p[pos] != -1) assert(find(adj[p[pos]].begin(), adj[p[pos]].end(), u) != adj[p[pos]].end());
    auto g = find(x.begin(), x.end(), pos);
    x.erase(g);
    g = find(x.begin(), x.end(), u); g++;
    x.insert(g, pos);
    for (int i = 1; i < (int)x.size(); i++) {
        auto u = find(adj[x[i]].begin(), adj[x[i]].end(), x[i - 1]);
       // assert(u != adj[x[i]].end());
    }
    return x;   
}

Compilation message

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:88:14: warning: variable 'u' set but not used [-Wunused-but-set-variable]
   88 |         auto u = find(adj[x[i]].begin(), adj[x[i]].end(), x[i - 1]);
      |              ^

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 192 ms 1576 KB Output is correct

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 344 KB Output is correct
2 Correct 26 ms 344 KB Output is correct
3 Correct 130 ms 1112 KB Output is correct
4 Correct 370 ms 744 KB Output is correct
5 Correct 750 ms 1896 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 23 ms 344 KB Output is correct
3 Correct 117 ms 856 KB Output is correct
4 Correct 360 ms 856 KB Output is correct
5 Correct 819 ms 1308 KB Output is correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 21 ms 344 KB Output is correct
8 Correct 134 ms 600 KB Output is correct
9 Correct 282 ms 856 KB Output is correct
10 Correct 772 ms 1584 KB Output is correct
11 Correct 711 ms 1132 KB Output is correct
12 Correct 729 ms 1396 KB Output is correct
13 Correct 753 ms 1900 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 21 ms 344 KB Output is correct
3 Correct 116 ms 856 KB Output is correct
4 Correct 350 ms 1224 KB Output is correct
5 Correct 742 ms 1280 KB Output is correct
6 Correct 8 ms 344 KB Output is correct
7 Correct 24 ms 344 KB Output is correct
8 Correct 119 ms 716 KB Output is correct
9 Correct 256 ms 744 KB Output is correct
10 Correct 708 ms 1072 KB Output is correct
11 Correct 679 ms 1404 KB Output is correct
12 Correct 720 ms 1416 KB Output is correct
13 Correct 695 ms 1116 KB Output is correct
14 Correct 6 ms 344 KB Output is correct
15 Correct 9 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 10 ms 344 KB Output is correct
2 Correct 26 ms 344 KB Output is correct
3 Partially correct 122 ms 856 KB Output is partially correct
4 Partially correct 377 ms 740 KB Output is partially correct
5 Partially correct 724 ms 1648 KB Output is partially correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 25 ms 344 KB Output is correct
8 Partially correct 133 ms 600 KB Output is partially correct
9 Partially correct 281 ms 724 KB Output is partially correct
10 Partially correct 713 ms 1324 KB Output is partially correct
11 Partially correct 690 ms 1064 KB Output is partially correct
12 Partially correct 735 ms 1628 KB Output is partially correct
13 Partially correct 702 ms 1336 KB Output is partially correct
14 Correct 7 ms 344 KB Output is correct
15 Correct 11 ms 344 KB Output is correct
16 Incorrect 2 ms 344 KB Incorrect
17 Halted 0 ms 0 KB -