Submission #1096674

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096674		onlk97	Fun Tour (APIO20_fun)	C++14	47 / 100	100 ms	20324 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]==1) 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>,greater <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;
    if (s[2].empty()){
        if (s[0].size()<s[1].size()) swap(s[0],s[1]);
        for (int i=0; i<N-1; i++){
            if (i%2==0){
                op.push_back((*s[0].begin()).second);
                s[0].erase(s[0].begin());
            } else {
                op.push_back((*s[1].begin()).second);
                s[1].erase(s[1].begin());
            }
        }
    } else {
        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={-1,-1};
            int ha=-1;
            for (int i=0; i<3; i++){
                if (prv==i||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 (prv==-1){
            int nxt=(w+1)%3;
            for (auto j:s[(nxt+1)%3]) s[nxt].insert(j);
            while (!s[w].empty()){
                op.push_back((*s[w].begin()).second); s[w].erase(s[w].begin());
                op.push_back((*s[nxt].begin()).second); s[nxt].erase(s[nxt].begin());
            }
        } else {
            int rem=w^prv^3;
            if ((*s[rem].begin()).first>=(*s[w].begin()).first){
                int f=1;
                while (!s[w].empty()){
                    if (f){
                        pair <int,int> tp=*s[rem].begin();
                        op.push_back(tp.second);
                        for (auto j:s[rem]) s[prv].insert(j);
                        s[prv].erase(tp);
                    } else {
                        op.push_back((*s[prv].begin()).second);
                        s[prv].erase(s[prv].begin());
                    }
                    op.push_back((*s[w].begin()).second);
                    s[w].erase(s[w].begin());
                    f=0;
                }
            } else {
                for (auto j:s[rem]) s[prv].insert(j);
                while (!s[w].empty()){
                    op.push_back((*s[w].begin()).second);
                    s[w].erase(s[w].begin());
                    op.push_back((*s[prv].begin()).second);
                    s[prv].erase(s[prv].begin());
                }
            }
        }
    }
    op.push_back(rt);
    return op;
}

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