oj.uz

Submission #1060026

# Submission time Handle Problem Language Result Execution time Memory
1060026 2024-08-15T10:09:12 Z noyancanturk Longest Trip (IOI23_longesttrip) C++17
5 / 100
 7 ms 440 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;
            break;
        }else{
            trip.pb(i+1);
        }
    }
    if(trip.size()==n)return trip;
    vector<int>cmp1,cmp2;
    //cerr<<"roots "<<root1<<" "<<root2<<"\n";
    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){
            //cerr<<i<<" in cmp1\n";
            cmp1.pb(i);
        }else{
            //cerr<<i<<" in cmp2\n";
            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;
    }
    //cerr<<"found link "<<link<<"\n";
    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:25:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   25 |     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 1 ms 436 KB Incorrect
3 Halted 0 ms 0 KB -

Subtask #1
5.0 / 5.0

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

Subtask #2
0.0 / 10.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 3 ms 340 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 5 ms 344 KB Output is correct
4 Correct 4 ms 344 KB Output is correct
5 Correct 5 ms 440 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 7 ms 344 KB Output is correct
3 Correct 5 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 -