oj.uz

Submission #1060010

# Submission time Handle Problem Language Result Execution time Memory
1060010 2024-08-15T10:02:29 Z noyancanturk Longest Trip (IOI23_longesttrip) C++17
5 / 100
 8 ms 344 KB 
#include "longesttrip.h"

#include <bits/stdc++.h>
using namespace std;

#define pb push_back

int n,d;

vector<int> longest_trip(int N, int D)
{
    n=N,d=D;
    vector<int>trip;
    trip.pb(0);
    int root1=0,root2=0;
    for(int i=0;i+1<n;i++){
        bool ok=are_connected({i},{i+1});
        if(!ok){
            root1=i,root2=i+1;
        }else{
            trip.pb(i+1);
        }
    }
    if(trip.size()==n)return trip;
    vector<int>cmp1,cmp2;
    cmp1.pb(root1);
    cmp2.pb(root2);
    for(int i=0;i<n;i++){
        if(i==root1||i==root2)continue;
        bool ok=are_connected({root1},{i});
        if(ok){
            cmp1.pb(i);
        }else{
            cmp2.pb(i);
        }
    }
    if(cmp2.size()<cmp1.size()){
        swap(cmp1,cmp2);
        swap(root1,root2);
    }
    int link=-1;
    for(int i:cmp1){
        bool ok=are_connected({i},cmp2);
        if(ok){
            link=i;
            break;
        }
    }
    if(link==-1){
        return cmp2;
    }
    vector<int>path;
    for(int i:cmp1){
        if(i!=link)path.pb(i);
    }
    path.pb(link);
    for(int i:cmp2){
        if(i!=link)path.pb(i);
    }
    return path;
}

Compilation message

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:24:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   24 |     if(trip.size()==n)return trip;
      |        ~~~~~~~~~~~^~~

Subtask #0
0.0 / 0.0

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

Subtask #1
5.0 / 5.0

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

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 8 ms 344 KB Output is correct
3 Correct 7 ms 344 KB Output is correct
4 Correct 5 ms 344 KB Output is correct
5 Correct 5 ms 344 KB Output is correct
6 Incorrect 0 ms 344 KB Incorrect
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 344 KB Output is correct
2 Correct 5 ms 344 KB Output is correct
3 Correct 6 ms 344 KB Output is correct
4 Correct 6 ms 344 KB Output is correct
5 Correct 7 ms 344 KB Output is correct
6 Incorrect 0 ms 344 KB Incorrect
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 344 KB Output is correct
2 Correct 5 ms 344 KB Output is correct
3 Correct 5 ms 344 KB Output is correct
4 Correct 6 ms 344 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Incorrect 0 ms 344 KB Incorrect
7 Halted 0 ms 0 KB -