oj.uz

Submission #1016999

# Submission time Handle Problem Language Result Execution time Memory
1016999 2024-07-08T16:56:46 Z Andrey Longest Trip (IOI23_longesttrip) C++17
15 / 100
 12 ms 856 KB 
#include "longesttrip.h"
#include<bits/stdc++.h>
using namespace std;

deque<int> haha[500];

int n;

void merge(int a, int b) {
    for(int i = 0; i < haha[b].size(); i++) {
        haha[a].push_front(haha[b][i]);
    }
    haha[b].clear();
}

int dude(int p1, int p2) {
    vector<int> a(0);
    vector<int> b(0);
    for(int i = 0; i < haha[p2].size(); i++) {
        b.push_back(haha[p2][i]);
    }
    int l = 0,r = haha[p1].size()-1;
    while(l < r) {
        int m = (l+r)/2;
        a.clear();
        for(int i = l; i <= m; i++) {
            a.push_back(haha[p1][i]);
        }
        if(are_connected(a,b)) {
            r = m;
        }
        else {
            l = m+1;
        }
    }
    return l;
}

std::vector<int> longest_trip(int N, int D)
{
    n = N;
    for(int i = 0; i < n; i++) {
        haha[i].clear();
        haha[i].push_back(i);
    }
    for(int i = 0; i < n-2; i++) {
        vector<int> wut(0);
        for(int j = 0; j < n; j++) {
            if(haha[j].size() > 0) {
                wut.push_back(j);
                if(wut.size() == 3) {
                    break;
                }
            }
        }
        if(are_connected({haha[wut[0]][0]},{haha[wut[1]][0]})) {
            merge(wut[0],wut[1]);
        }
        else if(are_connected({haha[wut[0]][0]},{haha[wut[2]][0]})) {
            merge(wut[0],wut[2]);
        }
        else {
            merge(wut[1],wut[2]);
        }
    }
    int p1 = -1,p2;
    for(int i = 0; i < n; i++) {
        if(haha[i].size() > 0) {
            if(p1 == -1) {
                p1 = i;
            }
            else {
                p2 = i;
            }
        }
    }
    
    vector<int> ans(0);
    if(are_connected({haha[p1][0]},{haha[p2][0]})) {
        for(int i = haha[p1].size()-1; i >= 0; i--) {
            ans.push_back(haha[p1][i]);
        }
        for(int i = 0; i < haha[p2].size(); i++) {
            ans.push_back(haha[p2][i]);
        }
        return ans;
    }
    if(are_connected({haha[p1][haha[p1].size()-1]},{haha[p2][0]})) {
        for(int i = 0; i < haha[p1].size(); i++) {
            ans.push_back(haha[p1][i]);
        }
        for(int i = 0; i < haha[p2].size(); i++) {
            ans.push_back(haha[p2][i]);
        }
        return ans;
    }
    if(are_connected({haha[p1][0]},{haha[p2][haha[p2].size()-1]})) {
        for(int i = haha[p1].size()-1; i >= 0; i--) {
            ans.push_back(haha[p1][i]);
        }
        for(int i = haha[p2].size()-1; i >= 0; i--) {
            ans.push_back(haha[p2][i]);
        }
        return ans;
    }
    vector<int> a(0);
    vector<int> b(0);
    for(int i = 0; i < haha[p1].size(); i++) {
        a.push_back(haha[p1][i]);
    }
    for(int i = 0; i < haha[p2].size(); i++) {
        b.push_back(haha[p2][i]);
    }
    if(!are_connected(a,b)) {
        if(a.size() > b.size()) {
            return a;
        }
        else {
            return b;
        }
    }
    int x1 = dude(p1,p2);
    int x2 = dude(p2,p1);
    for(int i = x1+1; i < haha[p1].size(); i++) {
        ans.push_back(haha[p1][i]);
    }
    for(int i = 0; i <= x1; i++) {
        ans.push_back(haha[p1][i]);
    }
    for(int i = x2; i < haha[p2].size(); i++) {
        ans.push_back(haha[p2][i]);
    }
    for(int i = 0; i < x2; i++) {
        ans.push_back(haha[p2][i]);
    }
    return ans;
}

Compilation message

longesttrip.cpp: In function 'void merge(int, int)':
longesttrip.cpp:10:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for(int i = 0; i < haha[b].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~~
longesttrip.cpp: In function 'int dude(int, int)':
longesttrip.cpp:19:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for(int i = 0; i < haha[p2].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~~~
longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:83:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |         for(int i = 0; i < haha[p2].size(); i++) {
      |                        ~~^~~~~~~~~~~~~~~~~
longesttrip.cpp:89:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         for(int i = 0; i < haha[p1].size(); i++) {
      |                        ~~^~~~~~~~~~~~~~~~~
longesttrip.cpp:92:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |         for(int i = 0; i < haha[p2].size(); i++) {
      |                        ~~^~~~~~~~~~~~~~~~~
longesttrip.cpp:108:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |     for(int i = 0; i < haha[p1].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~~~
longesttrip.cpp:111:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |     for(int i = 0; i < haha[p2].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~~~
longesttrip.cpp:124:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |     for(int i = x1+1; i < haha[p1].size(); i++) {
      |                       ~~^~~~~~~~~~~~~~~~~
longesttrip.cpp:130:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |     for(int i = x2; i < haha[p2].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 2 ms 600 KB Output is correct

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 600 KB Output is correct
2 Correct 6 ms 600 KB Output is correct
3 Correct 6 ms 600 KB Output is correct
4 Correct 5 ms 600 KB Output is correct
5 Correct 6 ms 600 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 600 KB Output is correct
2 Correct 5 ms 600 KB Output is correct
3 Correct 6 ms 600 KB Output is correct
4 Correct 6 ms 600 KB Output is correct
5 Correct 8 ms 600 KB Output is correct
6 Correct 6 ms 600 KB Output is correct
7 Correct 6 ms 600 KB Output is correct
8 Correct 5 ms 600 KB Output is correct
9 Correct 5 ms 600 KB Output is correct
10 Correct 7 ms 600 KB Output is correct
11 Correct 8 ms 600 KB Output is correct
12 Correct 6 ms 600 KB Output is correct
13 Correct 8 ms 856 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 600 KB Output is correct
2 Correct 7 ms 600 KB Output is correct
3 Correct 5 ms 600 KB Output is correct
4 Correct 7 ms 600 KB Output is correct
5 Correct 6 ms 600 KB Output is correct
6 Correct 5 ms 600 KB Output is correct
7 Correct 6 ms 600 KB Output is correct
8 Correct 5 ms 600 KB Output is correct
9 Correct 5 ms 600 KB Output is correct
10 Correct 6 ms 600 KB Output is correct
11 Correct 6 ms 600 KB Output is correct
12 Correct 6 ms 856 KB Output is correct
13 Correct 6 ms 600 KB Output is correct
14 Correct 11 ms 600 KB Output is correct
15 Correct 12 ms 600 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 600 KB Output is correct
2 Correct 7 ms 600 KB Output is correct
3 Correct 6 ms 600 KB Output is correct
4 Correct 5 ms 596 KB Output is correct
5 Correct 6 ms 600 KB Output is correct
6 Correct 6 ms 852 KB Output is correct
7 Correct 5 ms 600 KB Output is correct
8 Correct 7 ms 600 KB Output is correct
9 Correct 8 ms 600 KB Output is correct
10 Correct 5 ms 764 KB Output is correct
11 Correct 5 ms 600 KB Output is correct
12 Correct 8 ms 600 KB Output is correct
13 Correct 6 ms 600 KB Output is correct
14 Correct 12 ms 600 KB Output is correct
15 Correct 10 ms 600 KB Output is correct
16 Incorrect 3 ms 600 KB Incorrect
17 Halted 0 ms 0 KB -