oj.uz

Submission #1056410

# Submission time Handle Problem Language Result Execution time Memory
1056410 2024-08-13T09:18:59 Z Ignut Longest Trip (IOI23_longesttrip) C++17
15 / 100
 1000 ms 1104 KB 
/* Ignut
started: 13.08.2024
now: 13.08.2024
████████████████████████████████████████████████████████████████████
████████████████████████████████    ████████████████████████████████
██████████████████████████████        ██████████████████████████████
██████      ██████████████████        ██████████████████      ██████
██████          ██████████████        ██████████████          ██████
██████      ██    ████████████        ████████████    ██      ██████
██████      ████    ██████████        ██████████    ████      ██████
██████      ████      ██████████    ██████████      ████      ██████
██████      ████      ██████████    ██████████    ██████      ██████
██████      ██████    ██████████    ██████████    ██████      ██████
██████      ██████    ████████        ████████    ██████      ██████
██████      ██████      ██████        ██████      ██████      ██████
██████      ████        ████            ████        ████      ██████
██████            ██████████    ████    ██████████            ██████
██████      ██      ██████    ████████    ██████      ██      ██████
██████      ██████            ████████            ██████      ██████
██████                    ██            ██                    ██████
██████████████████████      ████    ████      ██████████████████████
████████████████████████      ██    ██      ████████████████████████
██████████████████████████                ██████████████████████████
██████████████████████████████        ██████████████████████████████
████████████████████████████████████████████████████████████████████
*/
 
#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
mt19937 rnd(11223344);
 
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);
    used[v] = true;
    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);
            }
        }
    }
 
    vector<int> res;
    for (int start = 0; start < N; start ++) {
        for (int i= 0; i < N; i ++) {
            used[i] = false;
            shuffle(g[i].begin(), g[i].end(), rnd);
        }
        order.clear();
        dfs(start);
        if (order.size() > res.size()) res = order;
    }
    return res;
}

Compilation message

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:74: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]
   74 |         for (int i = 0; i < lst.size(); i ++) res.push_back(lst[i].first);
      |                         ~~^~~~~~~~~~~~
longesttrip.cpp:76: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]
   76 |         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 Correct 0 ms 344 KB Output is correct
2 Correct 244 ms 1060 KB Output is correct

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 340 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 5 ms 344 KB Output is correct
2 Correct 19 ms 344 KB Output is correct
3 Correct 127 ms 344 KB Output is correct
4 Correct 390 ms 344 KB Output is correct
5 Correct 704 ms 424 KB Output is correct
6 Correct 5 ms 344 KB Output is correct
7 Correct 25 ms 340 KB Output is correct
8 Correct 126 ms 344 KB Output is correct
9 Correct 274 ms 344 KB Output is correct
10 Correct 696 ms 428 KB Output is correct
11 Correct 705 ms 344 KB Output is correct
12 Correct 660 ms 344 KB Output is correct
13 Correct 657 ms 424 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 19 ms 344 KB Output is correct
3 Correct 138 ms 344 KB Output is correct
4 Correct 439 ms 600 KB Output is correct
5 Execution timed out 1080 ms 1104 KB Time limit exceeded
6 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 19 ms 344 KB Output is correct
3 Partially correct 154 ms 344 KB Output is partially correct
4 Partially correct 444 ms 624 KB Output is partially correct
5 Execution timed out 1105 ms 856 KB Time limit exceeded
6 Halted 0 ms 0 KB -