Submission #1096431

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096431		onlk97	Fun Tour (APIO20_fun)	C++14	0 / 100	1 ms	396 KiB

fun

#include "fun.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;

vector <int> createFunTour(int N,int Q){
    int sz[N];
    for (int i=0; i<N; i++) sz[i]=attractionsBehind(0,i);
    int rt=0,mn=N;
    for (int i=1; i<N; i++){
        if (2*sz[i]>N&&sz[i]<mn){
            mn=sz[i];
            rt=i;
        }
    }
    int dep[N];
    for (int i=0; i<N; i++) dep[i]=hoursRequired(rt,i);
    if (N==2) return {0,1};
    vector <int> neigh;
    for (int i=0; i<N; i++) if (dep[i]) neigh.push_back(i);
    int col[N];
    for (int i=0; i<N; i++){
        col[i]=2;
        for (int j=0; j<2; j++){
            if (hoursRequired(neigh[j],i)+1==dep[i]){
                col[i]=j;
                break;
            }
        }
        if (i==rt) col[i]=-1;
    }
    set <pair <int,int> > s[3];
    for (int i=0; i<N; i++) if (col[i]!=-1) s[col[i]].insert({dep[i],i});
    vector <int> op;
    op.push_back(rt);
    int prv=-1;
    while (s[0].size()!=s[1].size()+s[2].size()&&s[1].size()!=s[0].size()+s[2].size()&&s[2].size()!=s[0].size()+s[1].size()){
        pair <int,int> best={1e9,1e9};
        int ha=0;
        for (int i=0; i<3; i++){
            if (i==prv||s[i].empty()) continue;
            pair <int,int> tp=*s[i].begin();
            if (tp<best){
                best=tp;
                ha=i;
            }
        }
        op.push_back(best.second);
        prv=ha;
        s[ha].erase(best);
    }
    int w=2;
    if (s[0].size()==s[1].size()+s[2].size()) w=0;
    else if (s[1].size()==s[0].size()+s[2].size()) w=1;
    if (w==prv){
        while (!s[w].empty()){
            pair <int,int> best={1e9,1e9};
            int ha=0;
            for (int i=0; i<3; i++){
                if (i==w||s[i].empty()) continue;
                pair <int,int> tp=*s[i].begin();
                if (tp<best){
                    best=tp;
                    ha=i;
                }
            }
            op.push_back(best.second);
            s[ha].erase(best);
            pair <int,int> tp=*s[w].begin();
            op.push_back(tp.second);
            s[w].erase(tp);
        }
    } else {
        while (!s[w].empty()){
            pair <int,int> tp=*s[w].begin();
            op.push_back(tp.second);
            s[w].erase(tp);
            pair <int,int> best={1e9,1e9};
            int ha=0;
            for (int i=0; i<3; i++){
                if (i==w||s[i].empty()) continue;
                tp=*s[i].begin();
                if (tp<best){
                    best=tp;
                    ha=i;
                }
            }
            op.push_back(best.second);
            s[ha].erase(best);
        }
    }
    reverse(op.begin(),op.end());
    return op;
}

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