Submission #898366

#	Time	Username	Problem	Language	Result	Execution time	Memory
898366		irmuun	Fun Tour (APIO20_fun)	C++17	26 / 100	23 ms	1372 KiB

fun

#include<bits/stdc++.h>
#include "fun.h"
 
using namespace std;
 
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

const int maxN=5e2;

vector<int>adj[maxN];
int dist[maxN][maxN],root=0,d=0;
void dfs(int x,int p){
    dist[root][x]=d;
    for(auto y:adj[x]){
        if(y!=p){
            d++;
            dfs(y,x);
        }
    }
    d--;
};

vector<int>createFunTour(int N,int Q){
    if(N<=500){
        for(int i=0;i<N;i++){
            for(int j=i+1;j<N;j++){
                if(hoursRequired(i,j)==1){
                    adj[i].pb(j);
                    adj[j].pb(i);
                }
            }
        }
        for(int i=0;i<N;i++){
            root=i;
            d=0;
            dfs(i,-1);
        }
        int cur=0,mx=0;
        for(ll i=0;i<N;i++){
            if(dist[0][i]>mx){
                mx=dist[0][i];
                cur=i;
            }
        }
        vector<int>ans;
        vector<bool>used(N,0);
        while(ans.size()<N){
            ans.pb(cur);
            used[cur]=true;
            mx=-1;
            int nxt=0;
            for(int i=0;i<N;i++){
                if(!used[i]&&dist[cur][i]>mx){
                    mx=dist[cur][i];
                    nxt=i;
                }
            }
            cur=nxt;
        }
        return ans;
    }
}

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:52:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   52 |         while(ans.size()<N){
      |               ~~~~~~~~~~^~
fun.cpp:67:1: warning: control reaches end of non-void function [-Wreturn-type]
   67 | }
      | ^

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 34