oj.uz

Submission #846575

# Submission time Handle Problem Language Result Execution time Memory
846575 2023-09-08T00:53:09 Z math_rabbit_1028 Longest Trip (IOI23_longesttrip) C++17
15 / 100
 823 ms 1828 KB 
#include <bits/stdc++.h>
#include "longesttrip.h"
using namespace std;

vector<int> longest_trip(int N, int D) {
    int n = N; 
    vector<int> adj[256];
    vector<int> res;
    res.clear();
    for (int i = 0; i < n; i++) adj[i].clear();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (are_connected({i}, {j})) {
                adj[i].push_back(j);
                adj[j].push_back(i);
            }
        }
    }

    int ch[256]; for (int i = 0; i < n; i++) ch[i] = 0;
    vector<int> path, clique;
    path.push_back(0);
    ch[0] = 1;
    while (true) {
        int bef = path.size();
        for (int i = 0; i < adj[path.back()].size(); i++) {
            int v = adj[path.back()][i];
            if (ch[v] == 0) {
                ch[v] = 1;
                path.push_back(v);
                break;
            }
        }
        if (bef == path.size()) break;
    }
    for (int i = 0; i < n; i++) if (ch[i] == 0) clique.push_back(i);

    bool connected = false;
    for (int i = 0; i < path.size(); i++) {
        for (int j = 0; j < adj[path[i]].size(); j++) {
            if (ch[adj[path[i]][j]] == 0) connected = true;
        }
    }
    if (connected) {
        for (int i = 0; i < adj[path[0]].size(); i++) {
            if (ch[adj[path[0]][i]] == 0) {
                int target = adj[path[0]][i];
                res = path;
                reverse(res.begin(), res.end());
                int t = 0;
                for (t = 0; t < clique.size(); t++) if (clique[t] == target) break;
                for (int j = 0; j < clique.size(); j++) res.push_back(clique[j]);
                return res;
            }
        }
        int s = path.size() - 1;
        for (int i = 0; i < adj[path[s]].size(); i++) {
            if (ch[adj[path[s]][i]] == 0) {
                int target = adj[path[s]][i];
                res = path;
                int t = 0;
                for (t = 0; t < clique.size(); t++) if (clique[t] == target) break;
                swap(clique[0], clique[t]);
                for (int j = 0; j < clique.size(); j++) res.push_back(clique[j]);
                return res;
            }
        }
        for (int i = 0; i < clique.size(); i++) {
            for (int j = 0; j < adj[clique[i]].size(); j++) {
                if (ch[adj[clique[i]][j]] == 1) {
                    int target = adj[clique[i]][j];
                    swap(clique[i], clique.back());
                    res = clique;
                    while (path[0] != target) {
                        int front = path[0];
                        path.erase(path.begin());
                        path.push_back(front);
                    }
                    for (int k = 0; k < path.size(); k++) res.push_back(path[k]);
                    return res;
                }
            }
        }
    }
    else {
        if (path.size() > clique.size()) return path;
        return clique;
    }
    return {}; // never reached
}

Compilation message

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:26:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         for (int i = 0; i < adj[path.back()].size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~
longesttrip.cpp:34:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         if (bef == path.size()) break;
      |             ~~~~^~~~~~~~~~~~~~
longesttrip.cpp:39:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for (int i = 0; i < path.size(); i++) {
      |                     ~~^~~~~~~~~~~~~
longesttrip.cpp:40:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for (int j = 0; j < adj[path[i]].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~~
longesttrip.cpp:45:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for (int i = 0; i < adj[path[0]].size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~~
longesttrip.cpp:51:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |                 for (t = 0; t < clique.size(); t++) if (clique[t] == target) break;
      |                             ~~^~~~~~~~~~~~~~~
longesttrip.cpp:52:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |                 for (int j = 0; j < clique.size(); j++) res.push_back(clique[j]);
      |                                 ~~^~~~~~~~~~~~~~~
longesttrip.cpp:57:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for (int i = 0; i < adj[path[s]].size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~~
longesttrip.cpp:62:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |                 for (t = 0; t < clique.size(); t++) if (clique[t] == target) break;
      |                             ~~^~~~~~~~~~~~~~~
longesttrip.cpp:64:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |                 for (int j = 0; j < clique.size(); j++) res.push_back(clique[j]);
      |                                 ~~^~~~~~~~~~~~~~~
longesttrip.cpp:68:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         for (int i = 0; i < clique.size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~
longesttrip.cpp:69:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |             for (int j = 0; j < adj[clique[i]].size(); j++) {
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~~
longesttrip.cpp:79:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |                     for (int k = 0; k < path.size(); k++) res.push_back(path[k]);
      |                                     ~~^~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 170 ms 1316 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 23 ms 344 KB Output is correct
3 Correct 122 ms 856 KB Output is correct
4 Correct 344 ms 1204 KB Output is correct
5 Correct 765 ms 1324 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 25 ms 596 KB Output is correct
3 Correct 137 ms 956 KB Output is correct
4 Correct 346 ms 984 KB Output is correct
5 Correct 773 ms 1128 KB Output is correct
6 Correct 6 ms 344 KB Output is correct
7 Correct 22 ms 344 KB Output is correct
8 Correct 124 ms 712 KB Output is correct
9 Correct 266 ms 864 KB Output is correct
10 Correct 783 ms 1628 KB Output is correct
11 Correct 757 ms 1648 KB Output is correct
12 Correct 782 ms 1528 KB Output is correct
13 Correct 743 ms 1776 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 344 KB Output is correct
2 Correct 34 ms 344 KB Output is correct
3 Correct 123 ms 596 KB Output is correct
4 Correct 365 ms 1360 KB Output is correct
5 Correct 785 ms 1032 KB Output is correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 22 ms 344 KB Output is correct
8 Correct 112 ms 464 KB Output is correct
9 Correct 303 ms 1220 KB Output is correct
10 Correct 777 ms 1556 KB Output is correct
11 Correct 805 ms 1540 KB Output is correct
12 Correct 777 ms 1516 KB Output is correct
13 Correct 767 ms 1736 KB Output is correct
14 Correct 9 ms 344 KB Output is correct
15 Correct 11 ms 344 KB Output is correct
16 Correct 57 ms 344 KB Output is correct
17 Correct 72 ms 600 KB Output is correct
18 Correct 115 ms 1112 KB Output is correct
19 Correct 268 ms 1380 KB Output is correct
20 Incorrect 244 ms 1628 KB Incorrect
21 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 29 ms 344 KB Output is correct
3 Partially correct 127 ms 856 KB Output is partially correct
4 Partially correct 389 ms 1208 KB Output is partially correct
5 Partially correct 804 ms 1792 KB Output is partially correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 22 ms 340 KB Output is correct
8 Partially correct 128 ms 856 KB Output is partially correct
9 Partially correct 275 ms 1368 KB Output is partially correct
10 Partially correct 773 ms 1448 KB Output is partially correct
11 Partially correct 823 ms 1828 KB Output is partially correct
12 Partially correct 714 ms 1268 KB Output is partially correct
13 Partially correct 734 ms 1276 KB Output is partially correct
14 Correct 6 ms 344 KB Output is correct
15 Correct 12 ms 344 KB Output is correct
16 Correct 34 ms 344 KB Output is correct
17 Partially correct 84 ms 600 KB Output is partially correct
18 Partially correct 106 ms 856 KB Output is partially correct
19 Partially correct 307 ms 888 KB Output is partially correct
20 Incorrect 248 ms 1252 KB Incorrect
21 Halted 0 ms 0 KB -