Submission #1317358

#	Time	Username	Problem	Language	Result	Execution time	Memory
1317358		AzeTurk810	Race (IOI11_race)	C++20	43 / 100	3095 ms	39516 KiB

race

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include "race.h"
#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>
// #include <algo.hpp>
/*
Telebe of Adicto && Mamedov yani AzeTurk810
I see humans but no humanity
*/

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

using ll = long long;
using namespace std;

#define ln '\n'
#define INFi 1e9
#define INFll 1e18

#ifdef ONPC
#include <algo.hpp>
#else
#define dbg(...)
#define dbg_out(...)
#endif

struct CentroiddeComposition {
    int _n_, _k_, _ans_, _cur_;
    vector<vector<pair<int, int>>> g;
    vector<bool> removed;
    vector<int> subSize, distFromCentroid, nodeFromCentroid;
    vector<vector<int>> level;
    vector<int> mp, last;
    CentroiddeComposition(int _n, vector<vector<pair<int, int>>> &_g, const int &_k) : g(_g), _n_(_n), _k_(_k), _ans_(INFi), _cur_(0) {
        removed.assign(_n + 1, false);
        distFromCentroid.assign(_n + 1, INFi);
        nodeFromCentroid.assign(_n + 1, INFi);
        subSize.resize(_n + 1);
        level.resize(_n + 1);
        mp.assign(_k + 1, INFi);
        last.assign(_k + 1, -1);
    }
    int getSubSize(int v, int pa = -1) {
        subSize[v] = 1;
        for (const auto &[u, w] : g[v]) {
            if (u == pa || removed[u])
                continue;
            getSubSize(u, v);
            subSize[v] += subSize[u];
        }
        return subSize[v];
    }

    void getDistFromCentroid(int v, int pa) {
        if (distFromCentroid[v] > _k_) // XXX: it can be in the same subtree
            return;
        // INFO: is it in other side of centroid???
        if (distFromCentroid[v] <= _k_) {
            int target = _k_ - distFromCentroid[v];
            if (last[target] != _cur_) {
                mp[target] = INFi;
                last[target] = _cur_;
            }
            _ans_ = min(_ans_, mp[target] + nodeFromCentroid[v]);
        }
        for (const auto &[u, w] : g[v]) {
            if (pa == u || removed[u])
                continue;
            distFromCentroid[u] = distFromCentroid[v] + w;
            nodeFromCentroid[u] = nodeFromCentroid[v] + 1;
            getDistFromCentroid(u, v);
        }
    }
    void addDistFromCentoid(int v, int pa) {
        if (distFromCentroid[v] > _k_) {
            return;
        }
        if (last[distFromCentroid[v]] != _cur_) {
            mp[distFromCentroid[v]] = INFi;
            last[distFromCentroid[v]] = _cur_;
        }
        mp[distFromCentroid[v]] = min(mp[distFromCentroid[v]], nodeFromCentroid[v]);
        for (const auto &[u, w] : g[v]) {
            if (pa == u || removed[u])
                continue;
            addDistFromCentoid(u, v);
        }
    }

    int findCentroid(int v, int half, int pa = -1) {
        for (const auto &[u, w] : g[v]) {
            if (u == pa || removed[u] || subSize[u] <= half) {
                continue;
            }
            return findCentroid(u, half, v);
        }
        return v;
    }

    int solve(int centroid, int sizeoftree) { // INFO: Centroid ucun cavab
                                              // WARNING: You must initilaze before getDistFromCentroid Manualy
                                              // nodeFromCentroid[v] = 0;
                                              // distFromCentroid[v] = 0;
                                              // mp.clear();
                                              // mp_same.clear();
                                              // getDistFromCentroid(v, -1);
        // mp.assign(_k_ + 1, INFi);// XXX: Can't assign
        _cur_++;
        last[0] = _cur_;
        mp[0] = 0;
        for (const auto &[u, w] : g[centroid]) {
            nodeFromCentroid[u] = 1;
            distFromCentroid[u] = w;
            getDistFromCentroid(u, centroid);
            addDistFromCentoid(u, centroid);
        }
        return _ans_;
    }

    int build(int v = 0, int id = 0) { // TODO: Inside
        int centroid = findCentroid(v, getSubSize(v) >> 1);
        removed[centroid] = true;
        solve(centroid, subSize[v]);
        for (const auto &[u, w] : g[centroid]) {
            if (removed[u])
                continue;
            level[id + 1].push_back(build(u, id + 1)); // WARNING: should it be id + 1 or id  ???
        }
        return centroid;
    }
};

int best_path(int N, int K, int H[][2], int L[]) {
    // return 0;
    vector<vector<pair<int, int>>> g(N);
    for (int i = 0; i < N - 1; i++) {
        const int &u = H[i][0], &v = H[i][1], &w = L[i];
        g[u].push_back(make_pair(v, w));
        g[v].push_back(make_pair(u, w));
    }
    CentroiddeComposition t(N, g, K);
    t.level[0].push_back(t.build(0));
    if (t._ans_ == INFi)
        t._ans_ = -1;
    return t._ans_;
}

// Attack on titan<3
// Just Imaginary
/*
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣀⠀⠀⠀⢀⣴⣾⠀⠀⠀⡀⢀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣿⣦⣾⣿⣿⣿⣿⣿⡆⠁⠀⢀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠹⣿⣿⣿⣿⣿⣿⣿⣿⡿⠁⠀⡠⠂⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠠⠔⠚⣿⣿⣿⣿⣿⣦⡄⠀⠁⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢀⠠⠐⢂⠉⡀⣀⣤⣄⢻⣿⣿⡟⢈⡹⣿⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⡀⠄⠂⠈⠀⣶⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠘⣷⡀⠀⡀⠐⠂⠐⢄
⠀⠀⠀⠀⠀⠀⠀⣿⣿⠟⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⣀⣾⣷⠯⠀⠤⠤⠄⠈
⠀⠀⠀⠀⠀⠀⣼⣿⡟⠀⠀⣹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣄⡀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⣰⣿⠋⠀⠀⢠⣾⣿⣿⣿⣿⣿⣭⠟⢻⣿⣿⣿⣿⡿⠁⠀⠀⠀⠀
⠀⠀⠀⣀⣶⡟⠁⠀⢾⣶⣿⠟⠉⠈⢻⣿⣿⣿⣦⣜⠀⠛⠛⠿⠁⠀⠀⠀⠀⠀
⠚⠻⠿⠿⡿⠁⠀⢠⣿⣿⠁⠀⣠⠖⠋⠉⠻⣿⣿⣿⣶⡀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⣰⣿⡿⠃⠠⠊⠁⠀⠀⠀⠀⠈⢿⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⢀⣴⡿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⣠⣾⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⢀⣴⠾⠟⠛⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
*/

Compilation message (stderr)

race.cpp:21:39: warning: bad option '-fwhole-program' to pragma 'optimize' [-Wpragmas]
   21 | #pragma GCC optimize("-fwhole-program")
      |                                       ^
race.cpp:28:41: warning: bad option '-fstrict-overflow' to pragma 'optimize' [-Wpragmas]
   28 | #pragma GCC optimize("-fstrict-overflow")
      |                                         ^
race.cpp:30:41: warning: bad option '-fcse-skip-blocks' to pragma 'optimize' [-Wpragmas]
   30 | #pragma GCC optimize("-fcse-skip-blocks")
      |                                         ^
race.cpp:44:51: warning: bad option '-funsafe-loop-optimizations' to pragma 'optimize' [-Wpragmas]
   44 | #pragma GCC optimize("-funsafe-loop-optimizations")
      |                                                   ^
In file included from race.cpp:47:
race.h:1:48: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
    1 | int best_path(int N, int K, int H[][2], int L[]);
      |                                                ^
race.h:1:48: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
race.h:1:48: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
race.h:1:48: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
race.h:1:48: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
race.h:1:48: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
race.h:1:48: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
race.h:1:48: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
race.cpp:81:84: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   81 |     CentroiddeComposition(int _n, vector<vector<pair<int, int>>> &_g, const int &_k) : g(_g), _n_(_n), _k_(_k), _ans_(INFi), _cur_(0) {
      |                                                                                    ^
race.cpp:81:84: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
race.cpp:81:84: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
race.cpp:81:84: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
race.cpp:90:38: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   90 |     int getSubSize(int v, int pa = -1) {
      |                                      ^
race.cpp:90:38: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
race.cpp:90:38: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
race.cpp:90:38: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
race.cpp:101:43: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  101 |     void getDistFromCentroid(int v, int pa) {
      |                                           ^
race.cpp:101:43: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
race.cpp:101:43: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
race.cpp:101:43: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
race.cpp:121:42: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  121 |     void addDistFromCentoid(int v, int pa) {
      |                                          ^
race.cpp:121:42: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
race.cpp:121:42: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
race.cpp:121:42: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
race.cpp:137:50: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  137 |     int findCentroid(int v, int half, int pa = -1) {
      |                                                  ^
race.cpp:137:50: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
race.cpp:137:50: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
race.cpp:137:50: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
race.cpp:147:43: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  147 |     int solve(int centroid, int sizeoftree) { // INFO: Centroid ucun cavab
      |                                           ^
race.cpp:147:43: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
race.cpp:147:43: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
race.cpp:147:43: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
race.cpp:167:36: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  167 |     int build(int v = 0, int id = 0) { // TODO: Inside
      |                                    ^
race.cpp:167:36: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
race.cpp:167:36: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
race.cpp:167:36: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
race.cpp:180:48: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  180 | int best_path(int N, int K, int H[][2], int L[]) {
      |                                                ^
race.cpp:180:48: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
race.cpp:180:48: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
race.cpp:180:48: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 0 / 57