oj.uz

Submission #1056400

# Submission time Handle Problem Language Result Execution time Memory
1056400 2024-08-13T09:14:18 Z Ignut Longest Trip (IOI23_longesttrip) C++17
15 / 100
 1000 ms 2097152 KB 
/* Ignut
started: 13.08.2024
now: 13.08.2024
████████████████████████████████████████████████████████████████████
████████████████████████████████    ████████████████████████████████
██████████████████████████████        ██████████████████████████████
██████      ██████████████████        ██████████████████      ██████
██████          ██████████████        ██████████████          ██████
██████      ██    ████████████        ████████████    ██      ██████
██████      ████    ██████████        ██████████    ████      ██████
██████      ████      ██████████    ██████████      ████      ██████
██████      ████      ██████████    ██████████    ██████      ██████
██████      ██████    ██████████    ██████████    ██████      ██████
██████      ██████    ████████        ████████    ██████      ██████
██████      ██████      ██████        ██████      ██████      ██████
██████      ████        ████            ████        ████      ██████
██████            ██████████    ████    ██████████            ██████
██████      ██      ██████    ████████    ██████      ██      ██████
██████      ██████            ████████            ██████      ██████
██████                    ██            ██                    ██████
██████████████████████      ████    ████      ██████████████████████
████████████████████████      ██    ██      ████████████████████████
██████████████████████████                ██████████████████████████
██████████████████████████████        ██████████████████████████████
████████████████████████████████████████████████████████████████████
*/

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

bool are_connected(vector<int> A, vector<int> B);

const int MAXN = 333;

vector<int> g[MAXN];
bool used[MAXN];

vector<int> order;

void dfs(int v) {
    order.push_back(v);
    for (int to : g[v]) {
        if (used[to]) continue;
        dfs(to);
        return;
    }
}

vector<int> longest_trip(int N, int D) {
    if (D == 3) {
        vector<int> vec;
        for (int i = 0; i < N; i ++) vec.push_back(i);
        return vec;
    }
    if (D == 2) {
        vector<pair<int, int>> lst;
        int cnt[N] = {};
        for (int i = 0; i < N; i ++) {
            for (int j = i + 1; j < N; j ++) {
                if (!are_connected({i}, {j})) {
                    lst.push_back({i, j});
                    cnt[i] ++, cnt[j] ++;
                }
            }
        }
        vector<int> free;
        for (int i = 0; i < N; i ++) if (cnt[i] == 0) free.push_back(i);
        vector<int> res;
        for (int i = 0; i < lst.size(); i ++) res.push_back(lst[i].first);
        for (int val : free) res.push_back(val);
        for (int i = 0; i < lst.size(); i ++) res.push_back(lst[i].second);
        return res;
    }

    order.clear();
    for (int i = 0; i < N; i ++) {
        g[i].clear();
        used[i] = false;
    }

    for (int i = 0; i < N; i ++) {
        for (int j = i + 1; j < N; j ++) {
            if (are_connected({i}, {j})) {
                g[i].push_back(j);
                g[j].push_back(i);
            }
        }
    }

    int vertex = 0;
    for (int i = 1; i < N; i ++) if (g[i].size() < g[vertex].size()) vertex = i;
    dfs(vertex);
    return order;
}

Compilation message

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:71:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         for (int i = 0; i < lst.size(); i ++) res.push_back(lst[i].first);
      |                         ~~^~~~~~~~~~~~
longesttrip.cpp:73:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         for (int i = 0; i < lst.size(); i ++) res.push_back(lst[i].second);
      |                         ~~^~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1172 ms 2097152 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 344 KB Output is correct
2 Correct 15 ms 344 KB Output is correct
3 Correct 120 ms 344 KB Output is correct
4 Correct 306 ms 344 KB Output is correct
5 Correct 725 ms 420 KB Output is correct
6 Correct 6 ms 344 KB Output is correct
7 Correct 20 ms 344 KB Output is correct
8 Correct 132 ms 344 KB Output is correct
9 Correct 269 ms 344 KB Output is correct
10 Correct 670 ms 420 KB Output is correct
11 Correct 688 ms 424 KB Output is correct
12 Correct 587 ms 420 KB Output is correct
13 Correct 647 ms 420 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1182 ms 2097152 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1163 ms 2097152 KB Time limit exceeded
2 Halted 0 ms 0 KB -