Submission #916133

#	Time	Username	Problem	Language	Result	Execution time	Memory
916133		chirathnirodha	Longest Trip (IOI23_longesttrip)	C++17	15 / 100	774 ms	2036 KiB

longesttrip

#include "longesttrip.h"
#include<bits/stdc++.h>
using namespace std;
#define PB push_back
#define MP make_pair
#define P push
#define I insert 
#define F first
#define S second
typedef long long ll;
 
vector<int> longest_trip(int n, int D){
    if(D==3){
        vector<int> tt;for(int i=0;i<n;i++)tt.PB(i);
        return tt;
    }
    vector<int> v[n];
    bool grid[n][n];
    for(int i=0;i<n;i++)v[i].clear();
    memset(grid,0,sizeof(grid));
 
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            if(are_connected({i},{j})){v[i].PB(j);v[j].PB(i); grid[i][j]=grid[j][i]=1;}
        }
    }
    vector<int> v1,v2;
    v1.PB(0);v2.PB(1);
    for(int i=2;i<n;i++){
        if(grid[i][v1.back()])v1.PB(i);
        else if(grid[i][v2.back()])v2.PB(i);
        else{
            for(int j=v2.size()-1;j>=0;j--)v1.PB(v2[j]);
            v2.clear();
            v2.PB(i);
        }
    }
    
    if(grid[v1.back()][v2[0]]){
        for(int i=0;i<v2.size();i++)v1.PB(v2[i]);
        return v1;
    }
    if(grid[v1.back()][v2.back()]){
        for(int i=v2.size()-1;i>=0;i--)v1.PB(v2[i]);
        return v1;
    }
    if(grid[v1[0]][v2[0]]){
        reverse(v1.begin(),v1.end());
        for(int i=0;i<v2.size();i++)v1.PB(v2[i]);
        return v1;
    }
    if(grid[v1[0]][v2.back()]){
        reverse(v1.begin(),v1.end());
        for(int i=v2.size()-1;i>=0;i--)v1.PB(v2[i]);
        return v1;
    }

    vector<int> ans;
    for(int i=0;i<v1.size();i++){
        for(int j=0;j<v2.size();j++){
            if(!grid[v1[i]][v2[j]])continue;
            for(int k=0;k<v1.size();k++){
                int x=(i-1-k+v1.size())%v1.size();
                ans.PB(v1[x]);
            }
            for(int k=0;k<v2.size();k++){
                int x=(j-1-k+v2.size())%v2.size();
                ans.PB(v2[x]);
            }
            return ans;
        }
    }
    if(v1.size()>v2.size()) return v1;
    else return v2;
}

Compilation message (stderr)

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:40:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for(int i=0;i<v2.size();i++)v1.PB(v2[i]);
      |                     ~^~~~~~~~~~
longesttrip.cpp:49:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         for(int i=0;i<v2.size();i++)v1.PB(v2[i]);
      |                     ~^~~~~~~~~~
longesttrip.cpp:59:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for(int i=0;i<v1.size();i++){
      |                 ~^~~~~~~~~~
longesttrip.cpp:60:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         for(int j=0;j<v2.size();j++){
      |                     ~^~~~~~~~~~
longesttrip.cpp:62:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |             for(int k=0;k<v1.size();k++){
      |                         ~^~~~~~~~~~
longesttrip.cpp:66:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |             for(int k=0;k<v2.size();k++){
      |                         ~^~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 25
• Subtask 4: 0 / 60