Submission #812231

#	Time	Username	Problem	Language	Result	Execution time	Memory
812231		Hanksburger	Fun Tour (APIO20_fun)	C++17	26 / 100	77 ms	17108 KiB

fun

#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
int dist[100005], bad[100005];
vector<int> adj[100005], ans;
queue<pair<int, int> > q;
vector<int> createFunTour(int n, int Q)
{
  for (int i=0; i<n; i++)
  {
    for (int j=i+1; j<n; j++)
    {
      if (hoursRequired(i, j)==1)
      {
        adj[i].push_back(j);
        adj[j].push_back(i);
      }
    }
  }
  int cur=0;
  for (int i=0; i<n; i++)
  {
    for (int j=0; j<n; j++)
      dist[j]=1e9;
    dist[cur]=0;
    q.push({cur, -1});
    while (!q.empty())
    {
      int u=q.front().first, p=q.front().second;
      q.pop();
      for (int v:adj[u])
      {
        if (v==p || bad[v])
          continue;
        dist[v]=dist[u]+1;
        q.push({v, u});
      }
    }
    int ind, mx=-1;
    for (int j=0; j<n; j++)
    {
      if (!bad[j] && mx<dist[j])
      {
        mx=dist[j];
        ind=j;
      }
    }
    ans.push_back(ind);
    bad[ind]=1;
    cur=ind;
  }
  return ans;
}

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