Submission #62002256

---

Source Code Expand

// 木を焼きなまし（近傍：部分木を別の親に付け替える）
#include <bits/stdc++.h>
using namespace std;

// util functions
void chmax(int &v, const int &nv) {if (v < nv) v = nv;}

// constants
const int N = 1000, H = 10;
const int TIME_LIMIT = 1950;
const int INF = 2e+9;
const double START_TEMP = 200;
const double END_TEMP = 0.0001;

// time management
chrono::system_clock::time_point start_time;
int now() {return chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now() - start_time).count();}

// random
random_device seed_gen;
mt19937_64 engine(seed_gen());
int uniform_int(int l, int r) {uniform_int_distribution<int> dist(l, r);return dist(engine);}
double uniform_double(double l, double r) {return l + (r-l)*((uniform_int(0, INF)+0.0)/INF);}

void get_input(vector<int> &A, vector<vector<int>> &G) {
    int n, m, h;
    cin >> n >> m >> h;
    A.resize(N);
    for (int &a : A) cin >> a;
    G.resize(N);
    while (m--) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for (int i = 0; i < N; i++) {
        sort(G[i].begin(), G[i].end(), [&](const int &l, const int &r) {return A[l] < A[r];});
    }
}

void print_output(const vector<int> &par) {
    for (const int &x : par) {
        cout << x << " ";
    }
    cout << "\n";
}

bool is_loop(const int &u, int p, const vector<int> &par) {
    while (p != -1) {
        if (p == u) return true;
        p = par[p];
    }
    return false;
}

vector<int> simulated_annealing(const vector<int> &A, const vector<vector<int>> &G) {
    vector<int> par(N, -1), height(N, 0), subtree_height_max(N, 0), subtree_a_sum = A;
    vector<vector<int>> childs(N);
    int score = 1;
    for (int u = 0; u < N; u++) score += A[u];
    int t = 0;

    int best_score = score;
    vector<int> best_par = par;

    for (int step = 0; true; step++) {
        if (step % 10000 == 0) {
            t = now();
            if (t > TIME_LIMIT) break;
            // if (step % 1000000) cerr << step << " " << score << endl;
        }
        int u = uniform_int(0, N-1);
        int np = uniform_int(-1, G[u].size()-1), nh = 0;
        if (np >= 0) {
            np = G[u][np];
            nh = height[np] + 1;
        }

        if (par[u]==np || nh + subtree_height_max[u] - height[u] > H || is_loop(u, np, par)) continue;

        int score_update = (nh - height[u]) * subtree_a_sum[u];
        double temp = START_TEMP +  (END_TEMP - START_TEMP) * t/TIME_LIMIT;
        double prob = exp(score_update / temp);
        if (uniform_double(0.0, 1.0) < prob) {
            // uの部分木の更新
            int hight_diff = nh - height[u];
            int old_subtree_hight_max = subtree_height_max[u];
            queue<int> Q;
            Q.push(u);
            while (!Q.empty()) {
                int v = Q.front();
                Q.pop();
                height[v] += hight_diff;
                subtree_height_max[v] += hight_diff;
                for (const int &nv : childs[v]) Q.push(nv);
            }
            // uの元の祖先の更新
            int p = par[u];
            if (p != -1) {
                childs[p].erase(find(childs[p].begin(), childs[p].end(), u));
                while (p != -1) {
                    subtree_a_sum[p] -= subtree_a_sum[u];
                    if (subtree_height_max[p] == old_subtree_hight_max) {
                        subtree_height_max[p] = height[p];
                        for (const int &q : childs[p]) chmax(subtree_height_max[p], subtree_height_max[q]);
                    }
                    p = par[p];
                }
            }
            // uの新しい祖先の更新
            par[u] = np;
            if (np != -1) {
                childs[np].emplace_back(u);
                while (np != -1) {
                    subtree_a_sum[np] += subtree_a_sum[u];
                    chmax(subtree_height_max[np], subtree_height_max[u]);
                    np = par[np];
                }
            }

            score += score_update;
            if (score > best_score) {
                best_score = score;
                best_par = par;
            }
        }
    }
    cerr << best_score << endl;
    return best_par;
}

int main() {
    start_time = chrono::system_clock::now();
    vector<int> A;
    vector<vector<int>> G;
    get_input(A, G);

    vector<int> par = simulated_annealing(A, G);

    print_output(par);
}

Submission Info

Judge Result