제출 #1166723

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1166723		SmuggingSpun	Fun Tour (APIO20_fun)	C++20	0 / 100	0 ms	328 KiB

fun

#include<bits/stdc++.h>
#include "fun.h"
using namespace std;
const int INF = 1e9;
template<class T>bool minimize(T& a, T b){
    if(a > b){
        a = b;
        return true;
    }
    return false;
}
template<class T>bool maximize(T& a, T b){
    if(a < b){
        a = b;
        return true;
    }
    return false;
}
int n;
namespace sub1{
    vector<int>solve(){
        vector<vector<int>>d(n, vector<int>(n));
        for(int i = 0; i < n; i++){
            d[i][i] = 0;
            for(int j = i + 1; j < n; j++){
                d[i][j] = d[j][i] = hoursRequired(i, j);
            }
        }
        vector<vector<int>>dp(1 << n, vector<int>(n, -INF)), to(1 << n, vector<int>(n));
        for(int mask = 1; mask < (1 << n); mask++){
            vector<int>p;
            for(int i = 0; i < n; i++){
                if(1 << i & mask){
                    p.emplace_back(i);
                }
            }
            if(p.size() == 1){
                dp[mask][p[0]] = INF;
                continue; 
            }
            for(int& i : p){
                for(int& j : p){
                    if(i != j && d[i][j] <= dp[mask ^ (1 << i)][j] && maximize(dp[mask][i], d[i][j])){
                        to[mask][i] = j;
                    }
                }
            }
        }
        vector<int>ans;
        int state = (1 << n) - 1, i = -1;
        for(i = 0; i < n; i++){
            if(dp[state][i] > -1){
                break;
            }
        }
        for(int _ = 1; _ < n; _++){
            ans.emplace_back(i);
            int I = to[state][i];
            state ^= 1 << i;
            i = I;
        }
        ans.emplace_back(i);
        reverse(ans.begin(), ans.end());
        return ans;
    }
}
namespace sub2{
    vector<int>solve(){
        vector<vector<int>>g(n);
        vector<bool>vis(n, false);
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                if(hoursRequired(i, j) == 1){
                    g[i].emplace_back(j);
                    g[j].emplace_back(i);
                }
            }
        }
        function<pair<int, int>(int, int, int)>dfs;
        dfs = [&] (int s, int p, int h){
            pair<int, int>ret = make_pair(h, s);
            for(int& d : g[s]){
                if(d != p && !vis[d]){
                    maximize(ret, dfs(d, s, h + 1));
                }
            }
            return ret;
        };
        int u = dfs(0, -1, 0).second;
        vector<int>ans = {u};
        for(int _ = 1; _ < n; _++){
            vis[u] = true;
            ans.emplace_back(u = dfs(u, -1, 0).second);
        }
        return ans;
    }
}
namespace sub345{
    vector<int>solve(){
        int centroid = 0, opt_cnt = n;
        for(int i = 1; i < n; i++){
            int cnt = attractionsBehind(0, i);
            //cout << i << " " << cnt << " ||| " << endl;
            if(cnt > ((n + 1) >> 1) && minimize(opt_cnt, cnt)){
                centroid = i;
            }
        }
        vector<int>d(n), near;
        for(int i = d[centroid] = 0; i < n; i++){
            if(i != centroid && (d[i] = hoursRequired(centroid, i)) == 1){
                near.emplace_back(i);
            }
        }    
        vector<vector<int>>part(near.size());
        for(int i = 0; i < near.size(); i++){
            part[i].emplace_back(near[i]);
        }
        for(int i = 0; i < n; i++){
            if(i != centroid && find(near.begin(), near.end(), i) == near.end()){
                bool flag = true;
                for(int j = 0; j + 1 < near.size(); j++){
                    if(d[i] == hoursRequired(near[j], i) + 1){
                        flag = false;
                        part[j].emplace_back(i);
                        break;
                    }
                }
                if(flag){
                    part.back().emplace_back(i);
                }
            }   
        }
        int belong = 0;
        for(int i = 0; i < part.size(); i++){
            sort(part[i].begin(), part[i].end(), [&] (int x, int y){
                return d[x] < d[y];
            });
            if(d[part[i].back()] > d[part[belong].back()]){
                belong = i;
            }
        }
        vector<int>ans;
        for(int _ = 1; _ < n; _++){
            int u = part[belong].back();
            part[belong].pop_back();
            ans.emplace_back(u);
            int next_belong = -1;
            for(int i = 0; i < part.size(); i++){
                if(i != belong && !part[i].empty() && (next_belong == -1 || d[part[i].back()] > d[part[next_belong].back()])){
                    next_belong = i;
                }
            }
            belong = next_belong;
        }
        ans.emplace_back(centroid);
        return ans;
    }
}
vector<int>createFunTour(int __n, int __q){
    if((n = __n) <= 17){
        return sub345::solve();
        return sub1::solve();
    }
    if(n <= 500){
        return sub345::solve();
        return sub2::solve();
    }
    return sub345::solve();
}

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