제출 #1072139

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1072139		Malix	즐거운 행로 (APIO20_fun)	C++14	31 / 100	90 ms	19400 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,dist;
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];
  }
}

pii bfs(int x){
  pii arr;
  arr.PB({1,x});
  REP(i,0,n){
    if(i==x||i==k)continue;
    int y=hoursRequired(x,i);
    int z=dist[i];
    if(y>z)continue;
    arr.PB({y+1,i});
  }
  sort(arr.begin(),arr.end());
  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);
  dfs(0);
  vi cn(n,n);
  k=0;
  bool flag=0;
  REP(i,1,n)cn[i]=attractionsBehind(0,i);
  REP(i,1,n)if(cn[i]>n/2)flag=1;
  if(flag)REP(i,1,n)if(cn[i]>n/2&&cn[i]<cn[k])k=i;
  dist.resize(n);
  REP(i,0,n)dist[i]=hoursRequired(k,i);
  REP(i,0,n)if(dist[i]==1)a[k].PB(i);
  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,2)arr[i]=bfs(a[k][i]);
    vi used(n,0);
    used[k]=1;
    REP(i,0,2)for(auto u:arr[i])used[u.S]=1;
    REP(i,0,n)if(used[i]==0)arr[2].PB({dist[i],i});
    sort(arr[2].begin(),arr[2].end());
    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]);
    vi sa(3);
    REP(i,0,3)sa[i]=arr[i].size();
    int pos=0;
    REP(i,1,3)if(arr[pos].back().F<arr[i].back().F)pos=i;
    int tmp=-1;
    // if(n%2==0&&sa[0]==n/2){
    //   sa[0]--;
    //   ans.PB(arr[0].back().S);
    //   arr[0].pop_back();
    //   tmp=arr[0].back().S;
    // }
    while(sa[0]!=sa[1]+sa[2]&&sa[1]!=sa[0]+sa[2]&&sa[2]!=sa[0]+sa[1]){
      ans.PB(arr[pos].back().S);
      arr[pos].pop_back();
      sa[pos]--;
      tmp=arr[pos].back().S;
      int pos2=0;
      if(pos==0)pos2++;
      REP(i,0,3){
        if(i==pos)continue;
        if(arr[pos2].back().F<arr[i].back().F)pos2=i;
      }
      pos=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());
    if(tmp==arr[0].back().S){
      ans.PB(arr[1].back().S);
      arr[1].pop_back();
    }
    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: 10 / 10
• Subtask 2: 0 / 16
• Subtask 3: 21 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 34