oj.uz

Submission #846576

# Submission time Handle Problem Language Result Execution time Memory
846576 2023-09-08T01:34:23 Z math_rabbit_1028 Longest Trip (IOI23_longesttrip) C++17
60 / 100
 834 ms 2052 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;
                swap(clique[0], clique[t]);                    
                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:53:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |                 for (int j = 0; j < clique.size(); j++) res.push_back(clique[j]);
      |                                 ~~^~~~~~~~~~~~~~~
longesttrip.cpp:58:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         for (int i = 0; i < adj[path[s]].size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~~
longesttrip.cpp:63:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |                 for (t = 0; t < clique.size(); t++) if (clique[t] == target) break;
      |                             ~~^~~~~~~~~~~~~~~
longesttrip.cpp:65:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |                 for (int j = 0; j < clique.size(); j++) res.push_back(clique[j]);
      |                                 ~~^~~~~~~~~~~~~~~
longesttrip.cpp:69:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         for (int i = 0; i < clique.size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~
longesttrip.cpp:70:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |             for (int j = 0; j < adj[clique[i]].size(); j++) {
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~~
longesttrip.cpp:80:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |                     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 185 ms 1668 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 24 ms 496 KB Output is correct
3 Correct 134 ms 700 KB Output is correct
4 Correct 380 ms 1000 KB Output is correct
5 Correct 704 ms 1288 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 21 ms 344 KB Output is correct
3 Correct 116 ms 1112 KB Output is correct
4 Correct 357 ms 1216 KB Output is correct
5 Correct 743 ms 1796 KB Output is correct
6 Correct 8 ms 344 KB Output is correct
7 Correct 22 ms 344 KB Output is correct
8 Correct 123 ms 1104 KB Output is correct
9 Correct 271 ms 984 KB Output is correct
10 Correct 742 ms 1380 KB Output is correct
11 Correct 762 ms 1592 KB Output is correct
12 Correct 739 ms 1772 KB Output is correct
13 Correct 746 ms 1144 KB Output is correct

Subtask #3
25.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 130 ms 960 KB Output is correct
4 Correct 371 ms 856 KB Output is correct
5 Correct 807 ms 1560 KB Output is correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 25 ms 344 KB Output is correct
8 Correct 120 ms 704 KB Output is correct
9 Correct 308 ms 1368 KB Output is correct
10 Correct 758 ms 1876 KB Output is correct
11 Correct 735 ms 1388 KB Output is correct
12 Correct 785 ms 1604 KB Output is correct
13 Correct 754 ms 1740 KB Output is correct
14 Correct 7 ms 344 KB Output is correct
15 Correct 13 ms 344 KB Output is correct
16 Correct 42 ms 344 KB Output is correct
17 Correct 84 ms 600 KB Output is correct
18 Correct 120 ms 860 KB Output is correct
19 Correct 290 ms 732 KB Output is correct
20 Correct 272 ms 964 KB Output is correct
21 Correct 742 ms 1860 KB Output is correct
22 Correct 781 ms 1492 KB Output is correct
23 Correct 751 ms 1660 KB Output is correct
24 Correct 797 ms 1660 KB Output is correct
25 Correct 8 ms 344 KB Output is correct
26 Correct 12 ms 796 KB Output is correct
27 Correct 24 ms 344 KB Output is correct
28 Correct 23 ms 344 KB Output is correct
29 Correct 19 ms 344 KB Output is correct
30 Correct 165 ms 704 KB Output is correct
31 Correct 168 ms 956 KB Output is correct
32 Correct 163 ms 696 KB Output is correct
33 Correct 299 ms 864 KB Output is correct
34 Correct 265 ms 1228 KB Output is correct
35 Correct 266 ms 968 KB Output is correct
36 Correct 821 ms 1376 KB Output is correct
37 Correct 811 ms 1292 KB Output is correct
38 Correct 763 ms 1024 KB Output is correct
39 Correct 709 ms 1236 KB Output is correct
40 Correct 755 ms 1368 KB Output is correct
41 Correct 746 ms 1284 KB Output is correct
42 Correct 834 ms 1500 KB Output is correct
43 Correct 819 ms 1224 KB Output is correct
44 Correct 745 ms 1356 KB Output is correct
45 Correct 13 ms 344 KB Output is correct
46 Correct 13 ms 344 KB Output is correct
47 Correct 21 ms 344 KB Output is correct
48 Correct 33 ms 344 KB Output is correct
49 Correct 27 ms 344 KB Output is correct
50 Correct 173 ms 964 KB Output is correct
51 Correct 150 ms 956 KB Output is correct
52 Correct 162 ms 948 KB Output is correct
53 Correct 292 ms 1368 KB Output is correct
54 Correct 277 ms 864 KB Output is correct
55 Correct 273 ms 856 KB Output is correct
56 Correct 731 ms 1332 KB Output is correct
57 Correct 734 ms 1552 KB Output is correct
58 Correct 765 ms 1832 KB Output is correct
59 Correct 718 ms 1576 KB Output is correct
60 Correct 766 ms 1316 KB Output is correct
61 Correct 788 ms 1268 KB Output is correct
62 Correct 755 ms 1252 KB Output is correct
63 Correct 693 ms 1848 KB Output is correct
64 Correct 788 ms 1276 KB Output is correct

Subtask #4
19.999999998 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 344 KB Output is correct
2 Correct 26 ms 344 KB Output is correct
3 Partially correct 130 ms 856 KB Output is partially correct
4 Partially correct 383 ms 976 KB Output is partially correct
5 Partially correct 745 ms 1128 KB Output is partially correct
6 Correct 8 ms 344 KB Output is correct
7 Correct 25 ms 544 KB Output is correct
8 Partially correct 119 ms 868 KB Output is partially correct
9 Partially correct 277 ms 1236 KB Output is partially correct
10 Partially correct 818 ms 1784 KB Output is partially correct
11 Partially correct 735 ms 1316 KB Output is partially correct
12 Partially correct 742 ms 1632 KB Output is partially correct
13 Partially correct 737 ms 1372 KB Output is partially correct
14 Correct 6 ms 344 KB Output is correct
15 Correct 11 ms 344 KB Output is correct
16 Correct 47 ms 344 KB Output is correct
17 Partially correct 81 ms 600 KB Output is partially correct
18 Partially correct 117 ms 1112 KB Output is partially correct
19 Partially correct 283 ms 1368 KB Output is partially correct
20 Partially correct 281 ms 1376 KB Output is partially correct
21 Correct 9 ms 344 KB Output is correct
22 Correct 13 ms 344 KB Output is correct
23 Correct 27 ms 344 KB Output is correct
24 Correct 28 ms 596 KB Output is correct
25 Correct 27 ms 344 KB Output is correct
26 Partially correct 166 ms 948 KB Output is partially correct
27 Partially correct 210 ms 696 KB Output is partially correct
28 Partially correct 184 ms 952 KB Output is partially correct
29 Partially correct 321 ms 1120 KB Output is partially correct
30 Partially correct 274 ms 948 KB Output is partially correct
31 Partially correct 287 ms 968 KB Output is partially correct
32 Correct 10 ms 344 KB Output is correct
33 Correct 9 ms 344 KB Output is correct
34 Correct 26 ms 344 KB Output is correct
35 Correct 28 ms 344 KB Output is correct
36 Correct 26 ms 344 KB Output is correct
37 Partially correct 172 ms 696 KB Output is partially correct
38 Partially correct 186 ms 956 KB Output is partially correct
39 Partially correct 170 ms 948 KB Output is partially correct
40 Partially correct 280 ms 1112 KB Output is partially correct
41 Partially correct 279 ms 968 KB Output is partially correct
42 Partially correct 256 ms 868 KB Output is partially correct
43 Partially correct 768 ms 1680 KB Output is partially correct
44 Partially correct 739 ms 1852 KB Output is partially correct
45 Partially correct 750 ms 1640 KB Output is partially correct
46 Partially correct 755 ms 1528 KB Output is partially correct
47 Partially correct 768 ms 1284 KB Output is partially correct
48 Partially correct 832 ms 1980 KB Output is partially correct
49 Partially correct 781 ms 1284 KB Output is partially correct
50 Partially correct 815 ms 1344 KB Output is partially correct
51 Partially correct 800 ms 1596 KB Output is partially correct
52 Partially correct 823 ms 984 KB Output is partially correct
53 Partially correct 794 ms 1264 KB Output is partially correct
54 Partially correct 811 ms 1340 KB Output is partially correct
55 Partially correct 747 ms 1700 KB Output is partially correct
56 Partially correct 747 ms 1504 KB Output is partially correct
57 Partially correct 724 ms 1372 KB Output is partially correct
58 Partially correct 725 ms 1780 KB Output is partially correct
59 Partially correct 718 ms 2052 KB Output is partially correct
60 Partially correct 804 ms 1032 KB Output is partially correct
61 Partially correct 791 ms 1284 KB Output is partially correct
62 Partially correct 744 ms 1976 KB Output is partially correct
63 Partially correct 732 ms 1460 KB Output is partially correct
64 Partially correct 733 ms 948 KB Output is partially correct
65 Partially correct 747 ms 1360 KB Output is partially correct
66 Partially correct 754 ms 1788 KB Output is partially correct
67 Partially correct 747 ms 1540 KB Output is partially correct
68 Partially correct 757 ms 1004 KB Output is partially correct
69 Partially correct 755 ms 1352 KB Output is partially correct
70 Partially correct 720 ms 1292 KB Output is partially correct
71 Partially correct 763 ms 1720 KB Output is partially correct
72 Partially correct 715 ms 1844 KB Output is partially correct
73 Partially correct 728 ms 1384 KB Output is partially correct
74 Partially correct 786 ms 1304 KB Output is partially correct
75 Partially correct 770 ms 1260 KB Output is partially correct
76 Partially correct 774 ms 1548 KB Output is partially correct
77 Partially correct 741 ms 1628 KB Output is partially correct
78 Partially correct 791 ms 1360 KB Output is partially correct
79 Partially correct 725 ms 1684 KB Output is partially correct
80 Partially correct 728 ms 1460 KB Output is partially correct
81 Partially correct 775 ms 1292 KB Output is partially correct
82 Partially correct 744 ms 1232 KB Output is partially correct