Submission #697396

#	Time	Username	Problem	Language	Result	Execution time	Memory
697396		sharaelong	Fun Tour (APIO20_fun)	C++17	100 / 100	197 ms	21540 KiB

fun

#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

vector<int> createFunTour(int n, int q) {
    if (n == 2) return vector<int>{0,1};
  
    vector<int> origin_sz(n, 0);
    for (int i=1; i<n; ++i) origin_sz[i] = attractionsBehind(0, i);
    int min_val = n+1;
    int cent = 0;
    for (int i=1; i<n; ++i) {
        if (origin_sz[i] > n/2 && min_val > origin_sz[i]) {
            min_val = origin_sz[i];
            cent = i;
        }
    }
    // cout << cent << endl;

    vector<int> dist(n, 0);
    vector<int> subtree_root;
    for (int i=0; i<n; ++i) {
        dist[i] = hoursRequired(cent, i);
        if (dist[i] == 1) subtree_root.push_back(i);
        // cout << dist[i] << ' ';
    }
    // cout << endl;

    vector<vector<int>> subtree(subtree_root.size());
    for (int i=0; i<n; ++i) {
        if (i != cent) {
            bool found = false;
            for (int j=0; j+1<subtree_root.size(); ++j) {
                int d = hoursRequired(subtree_root[j], i);
                if (d == dist[i]-1) {
                    subtree[j].push_back(i);
                    found = true;
                    break;
                }
            }
            if (!found) subtree.back().push_back(i);
        }
    }
    for (vector<int>& v: subtree) {
        sort(v.begin(), v.end(), [&](int a, int b) {
            return dist[a] < dist[b];
        });
    }
    // for (vector<int> v: subtree) {
    //     for (int x: v) {
    //         cout << x << ' ';
    //     }
    //     cout << endl;
    // }

    assert(subtree.size() != 1);
    vector<int> ans;
    if (subtree.size() == 2) {
        assert(abs((int)subtree[0].size()-(int)subtree[1].size()) <= 1);
        if (subtree[0].size() > subtree[1].size()) swap(subtree[0], subtree[1]);
        while (!subtree[0].empty()) {
            ans.push_back(subtree[1].back());
            ans.push_back(subtree[0].back());
            subtree[1].pop_back();
            subtree[0].pop_back();
        }
        if (!subtree[1].empty()) {
            ans.push_back(subtree[1][0]);
            subtree[1].pop_back();
        }
        assert(subtree[1].empty());
    } else {
        assert(subtree.size() == 3);
        int prev_tree = -1;
        while (2 * max({ subtree[0].size(), subtree[1].size(), subtree[2].size() }) < subtree[0].size() + subtree[1].size() + subtree[2].size()) {
            int max_dist = 0;
            int max_tree = -1;
            for (int i=0; i<3; ++i) {
                if (i != prev_tree && max_dist < dist[subtree[i].back()]) {
                    max_dist = dist[subtree[i].back()];
                    max_tree = i;
                }
            }
            ans.push_back(subtree[max_tree].back());
            subtree[max_tree].pop_back();
            prev_tree = max_tree;
        }
        
        for (int i=0; i<3; ++i) {
            for (int j=0; j<3; ++j) {
                if (subtree[i].size() > subtree[j].size()) {
                    if (prev_tree == i) prev_tree = j;
                    else if (prev_tree == j) prev_tree = i;
                    swap(subtree[i], subtree[j]);
                }
            }
        }
        // cout << prev_tree << endl;
        // for (vector<int> v: subtree) {
        //     for (int x: v) {
        //         cout << x << ' ';
        //     }
        //     cout << endl;
        // }
        assert(prev_tree != 0);
        if (prev_tree != -1 && !subtree[3-prev_tree].empty() && dist[subtree[3-prev_tree].back()] > dist[subtree[0].back()]) {
            // previous location of get into subtree 0 has to be deepest place
            if (dist[subtree[prev_tree].back()] < dist[subtree[3-prev_tree].back()]) {
                prev_tree = 3-prev_tree;
                ans.push_back(subtree[prev_tree].back());
                subtree[prev_tree].pop_back();
            }
        }
        while (true) {
            if (prev_tree == 0) {
                int max_dist = 0;
                int max_tree = -1;
                if (!subtree[1].empty() && dist[subtree[1].back()] > max_dist) {
                    max_dist = dist[subtree[1].back()];
                    max_tree = 1;
                }
                if (!subtree[2].empty() && dist[subtree[2].back()] > max_dist) {
                    max_dist = dist[subtree[2].back()];
                    max_tree = 2;
                }
                if (max_tree == -1) break;
                ans.push_back(subtree[max_tree].back());
                subtree[max_tree].pop_back();
                prev_tree = max_tree;
            } else {
                if (subtree[0].empty()) break;
                ans.push_back(subtree[0].back());
                subtree[0].pop_back();
                prev_tree = 0;
            }
        }
    }
    ans.push_back(cent);
    // for (int x: ans) cout << x << ' ';
    // cout << endl;
    return ans;
}

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:35:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |             for (int j=0; j+1<subtree_root.size(); ++j) {
      |                           ~~~^~~~~~~~~~~~~~~~~~~~

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