Submission #1072168

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072168		Malix	Fun Tour (APIO20_fun)	C++14	31 / 100	100 ms	19264 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]);
        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;
        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