Submission #1312364

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312364		eri16	Longest Trip (IOI23_longesttrip)	C++20	15 / 100	4 ms	408 KiB

longesttrip

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

vector <int> adj[256];
int vis[256];

void dfs(int u, int v){
    if (vis[u]==1){
        return;
    }    
    vis[u]=1;
    for (auto child : adj[u]){
        if (child != v && vis[child]==0){
            dfs(child,u);
        }
    }
} 


vector <int> longest_trip(int n, int d){
    vector <int> a,b;
    vector <int> ans;
    if (d==3){
        for (int i=0; i<n; i++){
            ans.push_back(i);
        }
        return ans;
    }
    if (d==2){
        ans.push_back(0);
        for (int i=1; i<n; i++){
            a.clear();
            b.clear();
            
            a.push_back(i);
            b.push_back(i-1);
            
            bool found =  are_connected(a,b);
            
            if (found){ans.push_back(i);}
            else if(i<n-1){
                ans.push_back(i+1);
                ans.push_back(i);
                i++;
            }
            else{
                vector <int> useless;
                
                useless.push_back(ans[ans.size()-1]);
                useless.push_back(ans[ans.size()-2]);
                useless.push_back(ans[ans.size()-3]);               
                
                ans.pop_back();
                ans.pop_back();
                
                a.clear();
                b.clear();
            
                a.push_back(useless[0]);
                b.push_back(useless[2]);
                
                bool found =  are_connected(a,b);
            
                if (found){ans.push_back(useless[0]);ans.push_back(useless[1]);ans.push_back(i);}
                else{ans.push_back(i);ans.push_back(useless[0]);ans.push_back(useless[1]);}
            }
        }
        return ans;
    }
    if (d==3){
        for (int i=0; i<n; i++){
            for (int j=i+1; j<n; j++){
                a.clear();
                b.clear();                
                a.push_back(i);
                b.push_back(j);
                bool found =  are_connected(a,b);
                if (found){
                    adj[i].push_back(j);
                    adj[j].push_back(i);
                }
            }
        }
        for (int i=0; i<256; i++){vis[i]=0;}
        dfs(0,-1);
        int sm=0;
        for (int i=0; i<n; i++){
            if (vis[i]==1){sm++;}
        }
        if (sm>=(n+1)/2){
            for (int i=0; i<n; i++){
                if (vis[i]==1){ans.push_back(i);}
            }
        }
        else{
            for (int i=0; i<n; i++){
                if (vis[i]==0){ans.push_back(i);}
            }            
        }
        return ans;
    }
}

Compilation message (stderr)

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:103:1: warning: control reaches end of non-void function [-Wreturn-type]
  103 | }
      | ^

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