Submission #1316093

#	Time	Username	Problem	Language	Result	Execution time	Memory
1316093		eri16	Longest Trip (IOI23_longesttrip)	C++20	40 / 100	409 ms	5544 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==1){
        map <pair<int,int>,int> mp;
        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){
                    mp[{i,j}]=mp[{j,i}]=1;
                    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!=0 && sm!=n){
            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;
        }
        
        int x=1;
        
        vector <int> v1,v2;
        
        v1.push_back(0);
        v2.push_back(1);
        
        for (int i=2; i<n; i++){
        
            int u = v1[v1.size()-1];
            int v = v2[v2.size()-1];        
            
            if (mp.contains({u,v})){
                reverse(v2.begin(),v2.end());
                v1.insert(v1.end(), v2.begin(), v2.end());
                v2.clear();
                v2.push_back(i);
            }
            else{
                if (mp.contains({u,i})){                
                    v1.push_back(i);
                }
                else{
                    v2.push_back(i);
                }
            }
        }
        if (v2.size()>v1.size())return v2;
        else{return v1;}
    }
}

Compilation message (stderr)

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

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