oj.uz

Submission #853586

# Submission time Handle Problem Language Result Execution time Memory
853586 2023-09-24T17:06:59 Z Andrey Longest Trip (IOI23_longesttrip) C++17
15 / 100
 773 ms 1176 KB 
#include "longesttrip.h"
#include<bits/stdc++.h>
using namespace std;

bool haha[1000][1000];

vector<int> longest_trip(int n, int d)
{
    for(int i = 0; i < n; i++) {
        haha[i][i] = false;
        for(int j = i+1; j < n; j++) {
            bool c = are_connected({i},{j});
            haha[i][j] = c;
            haha[j][i] = c;
        }
    }
    vector<bool> bruh(n,true);
    deque<int> ans;
    ans.push_back(0);
    bruh[0] = false;
    for(int i = 1; i < n; i++) {
        if(haha[0][i]) {
            ans.push_back(i);
            bruh[i] = false;
            break;
        }
    }
    for(int i = 2; i < n; i++) {
        int p;
        for(int j = 0; j < n; j++) {
            if(bruh[j]) {
                p = j;
            }
        }
        int a = ans[0],b = ans[ans.size()-1];
        if(haha[a][p]) {
            ans.push_front(p);
            bruh[p] = false;
        }
        else if(haha[b][p]) {
            ans.push_back(p);
            bruh[p] = false;
        }
        else {
            int c = -1;
            for(int j = 0; j < n; j++) {
                for(int y = 0; y < n; y++) {
                    if(bruh[j] == false && bruh[y] == true && haha[j][y]) {
                        c = y;
                    }
                }
            }
            if(c == -1) {
                break;
            }
            ans.push_back(c);
            bruh[c] = false;
        }
    }
    vector<int> wut(0);
    for(int i = 0; i < ans.size(); i++) {
        wut.push_back(ans[i]);
    }
    if(ans.size() == n) {
        return wut;
    }
    else {
        if(ans.size() < n-ans.size()) {
            wut.clear();
            for(int i = 0; i < n; i++) {
                if(bruh[i]) {
                    wut.push_back(i);
                }
            }
        }
    }
    return wut;
}

Compilation message

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:61:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for(int i = 0; i < ans.size(); i++) {
      |                    ~~^~~~~~~~~~~~
longesttrip.cpp:64:19: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   64 |     if(ans.size() == n) {
      |        ~~~~~~~~~~~^~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 160 ms 856 KB Incorrect
3 Halted 0 ms 0 KB -

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 344 KB Output is correct
2 Correct 24 ms 344 KB Output is correct
3 Correct 125 ms 344 KB Output is correct
4 Correct 340 ms 600 KB Output is correct
5 Correct 734 ms 664 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 21 ms 344 KB Output is correct
3 Correct 117 ms 344 KB Output is correct
4 Correct 322 ms 544 KB Output is correct
5 Correct 673 ms 668 KB Output is correct
6 Correct 8 ms 344 KB Output is correct
7 Correct 24 ms 344 KB Output is correct
8 Correct 124 ms 344 KB Output is correct
9 Correct 283 ms 520 KB Output is correct
10 Correct 690 ms 1176 KB Output is correct
11 Correct 708 ms 664 KB Output is correct
12 Correct 773 ms 668 KB Output is correct
13 Correct 691 ms 672 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 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 385 ms 544 KB Output is correct
5 Correct 737 ms 664 KB Output is correct
6 Correct 6 ms 344 KB Output is correct
7 Correct 23 ms 344 KB Output is correct
8 Correct 116 ms 344 KB Output is correct
9 Correct 267 ms 512 KB Output is correct
10 Correct 742 ms 672 KB Output is correct
11 Correct 680 ms 672 KB Output is correct
12 Correct 742 ms 856 KB Output is correct
13 Correct 734 ms 1012 KB Output is correct
14 Correct 8 ms 344 KB Output is correct
15 Correct 13 ms 344 KB Output is correct
16 Incorrect 2 ms 600 KB Incorrect
17 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 28 ms 344 KB Output is correct
3 Partially correct 130 ms 344 KB Output is partially correct
4 Partially correct 353 ms 540 KB Output is partially correct
5 Partially correct 771 ms 664 KB Output is partially correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 22 ms 344 KB Output is correct
8 Partially correct 122 ms 344 KB Output is partially correct
9 Partially correct 275 ms 592 KB Output is partially correct
10 Partially correct 692 ms 848 KB Output is partially correct
11 Partially correct 769 ms 1112 KB Output is partially correct
12 Partially correct 721 ms 1112 KB Output is partially correct
13 Partially correct 709 ms 668 KB Output is partially correct
14 Correct 7 ms 344 KB Output is correct
15 Correct 15 ms 344 KB Output is correct
16 Incorrect 3 ms 344 KB Incorrect
17 Halted 0 ms 0 KB -