Submission #1030556

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030556		_8_8_	Fun Tour (APIO20_fun)	C++17	100 / 100	182 ms	22240 KiB

fun

#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
int n,q;
int find_cen(){
    vector<pair<int,int>> a;
    for(int i = 1;i < n;i++){
        int s = attractionsBehind(0,i); 
        if(s*2 > n){
            a.emplace_back(s,i);
        }
    }
    if(a.empty()) return 0;
    sort(a.begin(),a.end());
    return a[0].second;
}
const int N = 1e5 + 12;
int val[N],bel[N];
vector<int> createFunTour(int nn, int qq) {
    if(nn == 2){
        return {0,1};
    }
    n = nn;q = qq;
    int c = find_cen();
    array<int,3> ver = {-1,-1,-1};
    array<vector<pair<int,int>>,3> vec;
    for(int i = 0;i < n;i++){
        if(i == c) continue;
        val[i] = hoursRequired(c,i);
        if(val[i] == 1){
            for(int j = 0;j < 3;j++){
                if(ver[j] == -1){
                    ver[j] = i;
                    break;
                }
            }
        }
    }
    vector<int> res;
    for(int i = 0;i < n;i++){
        if(i == c) continue;
        if(val[i] == 1){
            if(i == ver[0]){
                vec[0].push_back({1,i});
            }else if(i == ver[1]){
                bel[i] = 1;
                vec[1].push_back({1,i});
            }else{
                bel[i] = 2;
                vec[2].push_back({1,i});
            }
            continue;
        }
        int _ = -1;
        for(int k = 0;k < 2;k++){
            if(val[i] - 1 == hoursRequired(i,ver[k])){
                _=k;
                break;
            }
        }
        if(_ == -1) _ = 2;
        bel[i] = _;
        vec[_].push_back({val[i],i});
    }
    int lst = -1;
    int l = 0;
    bool OK = true;
    int _x = (int)vec[0].size(),_y = (int)vec[1].size(),_z = (int)vec[2].size();
    if(true){
        vector<pair<int,int>> cc;
        for(int i = 0;i < 3;i++){
            cc.push_back({(int)vec[i].size(),i});
        }
        sort(cc.begin(),cc.end());
        vec[(int)cc[0].second].push_back({0,c});
    }
    for(int i = 0;i < 3;i++){
        sort(vec[i].begin(),vec[i].end());
    }
    while(true){
        int _x = (int)vec[0].size(),_y = (int)vec[1].size(),_z = (int)vec[2].size();
        if(_x == _y + _z || _y == _x + _z || _z == _x + _y){
            break;
        }
        pair<int,int> mx = {-1,-1};
        int id = -1;
        auto upd = [&](vector<pair<int,int>> &a,int j){
            if(j != lst && (int)a.size()){
                pair<int,int> nv = make_pair(a.back().first,(int)a.size());
                if(nv > mx){
                    mx = nv;
                    id = j;
                }
            }
        };
        auto del = [&](vector<pair<int,int>> &x){ 
            res.push_back(x.back().second);
            x.pop_back();
        };
        int cc = 0;
        for(int i = 0;i < 3;i++){
            upd(vec[i],i);
        }
        lst = id;
        del(vec[id]);
    }
    vector<int> X,Y;
    vector<pair<int,int>> bff;
    int F = 0;
    for(int i = 0;i < 3;i++){
        bff.push_back({(int)vec[i].size(),i});
        if((int)vec[i].size()){
            F = max(F,vec[i].back().first);
        }
    }
    sort(bff.begin(),bff.end());
    bool ok = false;
    for(int i = 0;i < 3;i++){
        int j = bff[i].second;
        if(i < 2){
            if(lst == j) ok = 1;
            for(auto f:vec[j]){
                X.push_back(f.second);
            }
        }else{
            for(auto f:vec[j]){
                Y.push_back(f.second);
            }
        }
    }
    auto cmp = [&](int x,int y)->bool{
        return val[x] > val[y];
    };
    assert((int)X.size() == (int)Y.size());
    sort(X.begin(),X.end(),cmp);
    sort(Y.begin(),Y.end(),cmp);
    if(X.empty()) return res;
    if(ok){
        X.swap(Y);
    }
    if(bel[Y[0]] != lst && val[Y[0]] > val[X[0]]){
        X.swap(Y);
    }
    for(int i = 0;i < (int)X.size();i++){
        res.push_back(X[i]);
        res.push_back(Y[i]);
    }
    return res;
}

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:100:13: warning: unused variable 'cc' [-Wunused-variable]
  100 |         int cc = 0;
      |             ^~
fun.cpp:66:9: warning: unused variable 'l' [-Wunused-variable]
   66 |     int l = 0;
      |         ^
fun.cpp:67:10: warning: unused variable 'OK' [-Wunused-variable]
   67 |     bool OK = true;
      |          ^~
fun.cpp:68:9: warning: unused variable '_x' [-Wunused-variable]
   68 |     int _x = (int)vec[0].size(),_y = (int)vec[1].size(),_z = (int)vec[2].size();
      |         ^~
fun.cpp:68:33: warning: unused variable '_y' [-Wunused-variable]
   68 |     int _x = (int)vec[0].size(),_y = (int)vec[1].size(),_z = (int)vec[2].size();
      |                                 ^~
fun.cpp:68:57: warning: unused variable '_z' [-Wunused-variable]
   68 |     int _x = (int)vec[0].size(),_y = (int)vec[1].size(),_z = (int)vec[2].size();
      |                                                         ^~

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