Submission #1071701

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071701		Malix	Fun Tour (APIO20_fun)	C++14	0 / 100	75 ms	17636 KiB

fun

#include "fun.h"
#include <bits/stdc++.h>

using namespace std;

#define REP(a,b,c) for(int a=b;a<c;a++)
#define PB push_back
#define F first 
#define S second

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;

vii a;
vi p,s;
int n,k;

void dfs(int x){
  for(auto u:a[x]){
    if(u==p[x])continue;
    p[u]=x;
    dfs(u);
    s[x]+=s[u];
  }
}

int centroid(int x){
  int mx=0;int y=x;
  for(auto u:a[x])if(mx<s[u]){
    mx=s[u];
    y=u;
  }
  if(mx<=n/2)return x;
  s[x]-=s[y];
  s[y]=n;
  return centroid(y);
}

pii bfs(int x){
  pii arr;
  queue<pi> pq;
  vi vis(n,0);
  vis[k]=1;
  pq.push({1,x});
  while(!pq.empty()){
    int y=pq.front().F;
    int z=pq.front().S;
    pq.pop();
    arr.PB({y,z});vis[z]=1;
    for(auto u:a[z])if(vis[u]==0)pq.push({y+1,u});
  }
  return arr;
}

std::vector<int> createFunTour(int N, int q) {
  n=N;
  if(n==2)return {0,1};
  a.resize(n);p.resize(n,-1);s.resize(n,1);
  REP(i,0,n)REP(j,i+1,n)if(hoursRequired(i,j)==1){
    a[i].PB(j);
    a[j].PB(i);
  }
  dfs(0);
  k=centroid(0);
  int m=a[k].size();
  if(m==2){
    int c=a[k][0];
    int d=a[k][1];
    pii arr=bfs(c);
    pii brr=bfs(d);
    if(arr.size()<brr.size())swap(arr,brr);
    vi ans;
    while(!brr.empty()){
      ans.PB(arr.back().S);
      ans.PB(brr.back().S);
      arr.pop_back();brr.pop_back();
    }
    if(!arr.empty())ans.PB(arr.back().S);
    ans.PB(k);
    return ans;
  }
  else{
    vi ans;
    vector<pii> arr(3);
    REP(i,0,3)arr[i]=bfs(a[k][i]);
    vi sa(3);
    REP(i,0,3)sa[i]=arr[i].size();
    int g=0;
    if(n%2==0)g=1;
    while(sa[0]-g!=sa[1]+sa[2]&&sa[1]-g!=sa[0]+sa[2]&&sa[2]-g!=sa[0]+sa[1]){
      int pos=0;
      REP(i,1,3)if(arr[pos].back().F<arr[i].back().F)pos=i;
      ans.PB(arr[pos].back().S);
      arr[pos].pop_back();
      int pos2=0;
      if(pos==0)pos2++;
      REP(i,0,3){
        if(i==pos)continue;
        if(arr[pos2].back().S<arr[i].back().S)pos2=i;
      }
      ans.PB(arr[pos2].back().S);
      arr[pos2].pop_back();
      sa[pos]--;sa[pos2]--;
    }
    if(arr[1].size()<arr[2].size())swap(arr[1],arr[2]);
    if(arr[0].size()<arr[2].size())swap(arr[0],arr[2]);
    if(arr[0].size()<arr[1].size())swap(arr[0],arr[1]);
    for(auto u:arr[2])arr[1].PB(u);
    sort(arr[1].begin(),arr[1].end());
    while(!arr[1].empty()){
      ans.PB(arr[0].back().S);
      ans.PB(arr[1].back().S);
      arr[0].pop_back();
      arr[1].pop_back();
    }
    if(!arr[0].empty())ans.PB(arr[0].back().S);
    ans.PB(k);
    return ans;
  }
  // int A = attractionsBehind(0, n - 1);
  return std::vector<int>(n);
}

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