oj.uz

Submission #1038172

# Submission time Handle Problem Language Result Execution time Memory
1038172 2024-07-29T13:57:29 Z aymanrs Longest Trip (IOI23_longesttrip) C++17
60 / 100
 927 ms 1260 KB 
#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
bool g[300][300] = {{false}};
bool ej[256] = {false};
pair<vector<int>,vector<int>> fl(const vector<int>& V){
    memset(ej, 0, sizeof(ej));
    queue<int> q;q.push(V[0]);
    ej[V[0]]=true;
    vector<int> a;a.push_back(V[0]);
    while(!q.empty()){
        int t = q.front();
        q.pop();
        for(int j : V){
            if(g[t][j] && !ej[j]){
                ej[j]=true;
                q.push(j);
                a.push_back(j);
            }
        }
    }
    vector<int> b, c;
    if(a.size()<V.size()){
        for(int i : V) if(!ej[i]) b.push_back(i);
        return {a,b};
    }
    int i, j;
    for(i = 0;i < V.size();i++){
        for(j = i+1;j < V.size();j++){
            if(!g[V[i]][V[j]]) goto hoho;
        }
    }
    hoho:
    if(i >= V.size() || j >= V.size()) return {a, {}};
    a.clear();
    i=V[i];j=V[j];
    for(int k : V){
        if(k==i||k==j) continue;
        if(!g[k][j]) a.push_back(k);
        else if(!g[k][i]) c.push_back(k);
        else {
            b.push_back(k);
        }
    }
    if(b.empty()){
        a.push_back(i);
        for(int& k : a){
            for(int& l : c){
                if(g[k][l]){
                    swap(k, a.back());
                    swap(l, c[0]);
                    c.push_back(j);
                    for(int x : c) a.push_back(x);
                    return {a, {}};
                }
            }
        }
    }
    auto L = fl(b);
    if(L.second.empty()){
        a.push_back(i);
        for(int k : L.first) a.push_back(k);
        a.push_back(j);
        for(int k : c) a.push_back(k);
        return {a, {}};
    } else {
        if(a.empty()){
            L.first.push_back(i);
            for(int k : L.second) L.first.push_back(k);
            L.first.push_back(j);
            for(int k : c) L.first.push_back(k);
            return {L.first, {}};
        }
        if(g[a[0]][L.first[0]]){
            a.push_back(i);
            swap(a.back(), a[0]);
            for(int k : L.first) a.push_back(k);
            for(int k : a) L.second.push_back(k);
            L.second.push_back(j);
            for(int k : c) L.second.push_back(k);
            return {L.second, {}};
        } else {
            a.push_back(i);
            swap(a.back(), a[0]);
            for(int k : L.second) a.push_back(k);
            for(int k : a) L.first.push_back(k);
            L.first.push_back(j);
            for(int k : c) L.first.push_back(k);
            return {L.first, {}};
        }
    }

}
std::vector<int> longest_trip(int N, int D)
{
    vector<int> V;
    for(int i = 0;i < N;i++) for(int j = 0;j < N;j++) g[i][j] = false;
    for(int i = 0;i < N;i++){
        V.push_back(i);
        for(int j = i+1;j < N;j++){
            if(are_connected({i}, {j})){
                g[i][j]=g[j][i]=true;
            }
        }
    }
    auto L = fl(V);
   if(L.first.size()>=L.second.size()) return L.first;
   return L.second;
}

Compilation message

longesttrip.cpp: In function 'std::pair<std::vector<int>, std::vector<int> > fl(const std::vector<int>&)':
longesttrip.cpp:28:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(i = 0;i < V.size();i++){
      |               ~~^~~~~~~~~~
longesttrip.cpp:29:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         for(j = i+1;j < V.size();j++){
      |                     ~~^~~~~~~~~~
longesttrip.cpp:34:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     if(i >= V.size() || j >= V.size()) return {a, {}};
      |        ~~^~~~~~~~~~~
longesttrip.cpp:34:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     if(i >= V.size() || j >= V.size()) return {a, {}};
      |                         ~~^~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 168 ms 744 KB Output is correct

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 19 ms 344 KB Output is correct
3 Correct 114 ms 436 KB Output is correct
4 Correct 348 ms 344 KB Output is correct
5 Correct 733 ms 492 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 344 KB Output is correct
3 Correct 143 ms 436 KB Output is correct
4 Correct 393 ms 456 KB Output is correct
5 Correct 814 ms 488 KB Output is correct
6 Correct 5 ms 344 KB Output is correct
7 Correct 22 ms 344 KB Output is correct
8 Correct 150 ms 600 KB Output is correct
9 Correct 295 ms 516 KB Output is correct
10 Correct 822 ms 824 KB Output is correct
11 Correct 789 ms 1260 KB Output is correct
12 Correct 796 ms 1020 KB Output is correct
13 Correct 785 ms 868 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 344 KB Output is correct
2 Correct 17 ms 344 KB Output is correct
3 Correct 155 ms 432 KB Output is correct
4 Correct 368 ms 592 KB Output is correct
5 Correct 841 ms 492 KB Output is correct
6 Correct 9 ms 344 KB Output is correct
7 Correct 22 ms 344 KB Output is correct
8 Correct 163 ms 484 KB Output is correct
9 Correct 314 ms 544 KB Output is correct
10 Correct 819 ms 1012 KB Output is correct
11 Correct 810 ms 1048 KB Output is correct
12 Correct 840 ms 1052 KB Output is correct
13 Correct 806 ms 1052 KB Output is correct
14 Correct 4 ms 344 KB Output is correct
15 Correct 10 ms 344 KB Output is correct
16 Correct 33 ms 344 KB Output is correct
17 Correct 80 ms 344 KB Output is correct
18 Correct 139 ms 344 KB Output is correct
19 Correct 294 ms 600 KB Output is correct
20 Correct 296 ms 344 KB Output is correct
21 Correct 795 ms 520 KB Output is correct
22 Correct 819 ms 768 KB Output is correct
23 Correct 775 ms 520 KB Output is correct
24 Correct 756 ms 752 KB Output is correct
25 Correct 9 ms 344 KB Output is correct
26 Correct 5 ms 340 KB Output is correct
27 Correct 19 ms 344 KB Output is correct
28 Correct 22 ms 344 KB Output is correct
29 Correct 19 ms 344 KB Output is correct
30 Correct 163 ms 344 KB Output is correct
31 Correct 165 ms 344 KB Output is correct
32 Correct 127 ms 344 KB Output is correct
33 Correct 269 ms 448 KB Output is correct
34 Correct 269 ms 600 KB Output is correct
35 Correct 253 ms 460 KB Output is correct
36 Correct 710 ms 492 KB Output is correct
37 Correct 759 ms 496 KB Output is correct
38 Correct 783 ms 496 KB Output is correct
39 Correct 833 ms 492 KB Output is correct
40 Correct 777 ms 488 KB Output is correct
41 Correct 779 ms 492 KB Output is correct
42 Correct 825 ms 492 KB Output is correct
43 Correct 847 ms 488 KB Output is correct
44 Correct 762 ms 488 KB Output is correct
45 Correct 9 ms 344 KB Output is correct
46 Correct 10 ms 344 KB Output is correct
47 Correct 26 ms 344 KB Output is correct
48 Correct 25 ms 344 KB Output is correct
49 Correct 30 ms 344 KB Output is correct
50 Correct 201 ms 344 KB Output is correct
51 Correct 183 ms 600 KB Output is correct
52 Correct 196 ms 344 KB Output is correct
53 Correct 305 ms 448 KB Output is correct
54 Correct 295 ms 344 KB Output is correct
55 Correct 297 ms 456 KB Output is correct
56 Correct 764 ms 488 KB Output is correct
57 Correct 793 ms 496 KB Output is correct
58 Correct 818 ms 744 KB Output is correct
59 Correct 749 ms 496 KB Output is correct
60 Correct 715 ms 496 KB Output is correct
61 Correct 804 ms 488 KB Output is correct
62 Correct 837 ms 492 KB Output is correct
63 Correct 776 ms 492 KB Output is correct
64 Correct 823 ms 744 KB Output is correct

Subtask #4
19.999999998 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 344 KB Output is correct
2 Correct 22 ms 344 KB Output is correct
3 Partially correct 128 ms 428 KB Output is partially correct
4 Partially correct 404 ms 452 KB Output is partially correct
5 Partially correct 822 ms 492 KB Output is partially correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 18 ms 344 KB Output is correct
8 Partially correct 151 ms 600 KB Output is partially correct
9 Partially correct 276 ms 344 KB Output is partially correct
10 Partially correct 800 ms 828 KB Output is partially correct
11 Partially correct 844 ms 1116 KB Output is partially correct
12 Partially correct 835 ms 1044 KB Output is partially correct
13 Partially correct 760 ms 1048 KB Output is partially correct
14 Correct 5 ms 344 KB Output is correct
15 Correct 11 ms 344 KB Output is correct
16 Correct 43 ms 344 KB Output is correct
17 Partially correct 89 ms 344 KB Output is partially correct
18 Partially correct 147 ms 344 KB Output is partially correct
19 Partially correct 273 ms 464 KB Output is partially correct
20 Partially correct 295 ms 444 KB Output is partially correct
21 Correct 11 ms 596 KB Output is correct
22 Correct 8 ms 344 KB Output is correct
23 Correct 31 ms 344 KB Output is correct
24 Correct 21 ms 344 KB Output is correct
25 Correct 23 ms 344 KB Output is correct
26 Partially correct 184 ms 344 KB Output is partially correct
27 Partially correct 206 ms 344 KB Output is partially correct
28 Partially correct 195 ms 344 KB Output is partially correct
29 Partially correct 313 ms 600 KB Output is partially correct
30 Partially correct 335 ms 444 KB Output is partially correct
31 Partially correct 313 ms 456 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 27 ms 344 KB Output is correct
35 Correct 20 ms 344 KB Output is correct
36 Correct 16 ms 344 KB Output is correct
37 Partially correct 177 ms 344 KB Output is partially correct
38 Partially correct 168 ms 344 KB Output is partially correct
39 Partially correct 206 ms 344 KB Output is partially correct
40 Partially correct 315 ms 444 KB Output is partially correct
41 Partially correct 295 ms 440 KB Output is partially correct
42 Partially correct 281 ms 344 KB Output is partially correct
43 Partially correct 804 ms 520 KB Output is partially correct
44 Partially correct 878 ms 768 KB Output is partially correct
45 Partially correct 850 ms 756 KB Output is partially correct
46 Partially correct 793 ms 516 KB Output is partially correct
47 Partially correct 821 ms 492 KB Output is partially correct
48 Partially correct 813 ms 344 KB Output is partially correct
49 Partially correct 795 ms 492 KB Output is partially correct
50 Partially correct 858 ms 496 KB Output is partially correct
51 Partially correct 746 ms 492 KB Output is partially correct
52 Partially correct 790 ms 500 KB Output is partially correct
53 Partially correct 777 ms 488 KB Output is partially correct
54 Partially correct 790 ms 496 KB Output is partially correct
55 Partially correct 761 ms 496 KB Output is partially correct
56 Partially correct 806 ms 492 KB Output is partially correct
57 Partially correct 809 ms 496 KB Output is partially correct
58 Partially correct 764 ms 748 KB Output is partially correct
59 Partially correct 798 ms 488 KB Output is partially correct
60 Partially correct 745 ms 492 KB Output is partially correct
61 Partially correct 712 ms 492 KB Output is partially correct
62 Partially correct 795 ms 488 KB Output is partially correct
63 Partially correct 824 ms 496 KB Output is partially correct
64 Partially correct 829 ms 488 KB Output is partially correct
65 Partially correct 828 ms 500 KB Output is partially correct
66 Partially correct 927 ms 492 KB Output is partially correct
67 Partially correct 842 ms 492 KB Output is partially correct
68 Partially correct 834 ms 492 KB Output is partially correct
69 Partially correct 836 ms 500 KB Output is partially correct
70 Partially correct 815 ms 496 KB Output is partially correct
71 Partially correct 796 ms 592 KB Output is partially correct
72 Partially correct 809 ms 496 KB Output is partially correct
73 Partially correct 872 ms 496 KB Output is partially correct
74 Partially correct 744 ms 748 KB Output is partially correct
75 Partially correct 821 ms 592 KB Output is partially correct
76 Partially correct 865 ms 492 KB Output is partially correct
77 Partially correct 790 ms 592 KB Output is partially correct
78 Partially correct 754 ms 492 KB Output is partially correct
79 Partially correct 753 ms 488 KB Output is partially correct
80 Partially correct 728 ms 492 KB Output is partially correct
81 Partially correct 857 ms 496 KB Output is partially correct
82 Partially correct 752 ms 504 KB Output is partially correct