oj.uz

Submission #962522

# Submission time Handle Problem Language Result Execution time Memory
962522 2024-04-13T18:32:28 Z chifwin Race (IOI11_race) C++17
100 / 100
 1149 ms 113664 KB 
#include "race.h"

#include <bits/stdc++.h>

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#define ll long long
#define ull unsigned long long
#define ld long double
#define vll vector<ll>
#define pll pair<ll, ll>
#define plll pair<pll, ll>
#define lpll pair<ll, pll>
#define FOR(i, start, stop) for(ll i = (start); i < (stop); i++)
#define fi(n)  FOR(i, 0, n)
#define fj(n)  FOR(j, 0, n)
#define fk(n)  FOR(k, 0, n)
#define fio(n) FOR(i, 1, n)
#define fjo(n) FOR(j, 1, n)
#define fko(n) FOR(k, 1, n)
#define fiv(n) for (ll i = n-1; i >= 0; i--)
#define fjv(n) for (ll j = n-1; j >= 0; j--)
#define fkv(n) for (ll k = n-1; k >= 0; k--)
#define f first
#define s second
#define pb push_back
#define rt return
#define cn continue;
#define br break;
#define sz(x) ((ll)x.size())
#define all(queries) begin(queries),end(queries)
#define rall(queries) (queries).rbegin(),(queries).rend()
#define YESNO(flag) cout<<(flag ? "YES" : "NO") <<'\n';
#define dbg(...) {cerr << "\033[33m" << (#__VA_ARGS__) << ": "; dbg_vals(__VA_ARGS__); cerr << "\033[0m\n";}
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

template<class T> istream& operator>>(istream& in, vector<T>& x){for(T& i : x) in >> i; return in; }
template<class T, class TT> istream& operator>>(istream& in, pair<T, TT>& x){ in >> x.f >> x.s; return in; }
template<class T, class TT> ostream& operator<<(ostream& out, const pair<T, TT>& x){ out << x.f << ' ' << x.s; return out; }
template <typename Iter, typename=decltype(declval<Iter>().begin()), typename=enable_if_t<!is_convertible_v<Iter, string>>> ostream& operator<<(ostream& out, const Iter& x){ for (const auto& i : x) out << i << ' '; return out;}

template<typename T> void dbg_vals(T x){ cerr<< "\033[31m" << x << "\033[0m"; }
template<typename T, typename... Args> void dbg_vals(T x, Args... args){ dbg_vals(x); cerr << " | "; dbg_vals(args...); }

struct custom_hash { static uint64_t splitmix64(uint64_t x) {/*http://xorshift.di.unimi.it/splitmix64.c*/ x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31);} size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();return splitmix64(x + FIXED_RANDOM);}};
template<class T> using ll_umap = unordered_map<ll, T, custom_hash>;
using ll_uset = unordered_set<ll, custom_hash>;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
template<class T, class comp=less<T>> using ordered_set = __gnu_pbds::tree<T, __gnu_pbds::null_type, comp, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
// find_by_order(k) - iterator on k's elements
// order_of_key(x) - number of elements, strictly less than x

template<class T> using min_pq = priority_queue<T, vector<T>, greater<T>>;

const ll MAXN = 212345;
const ll MOD = 1000'000'007;
const ld EPS = 1e-10;
const ll INF = (ll)(1ll<<60) + (ll)((1ll<<30)-1);
const ld PI = atanl(1)*4;

ll rll(ll r=numeric_limits<ll>::max(), ll l=0){ /*random long long*/ static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); return uniform_int_distribution<ll>(l, r)(rng); }
template<typename F> auto time_measure(F f){ auto start = chrono::steady_clock::now(); f(); auto end = chrono::steady_clock::now(); return std::chrono::duration_cast<std::chrono::microseconds>(end - start).count(); }
array<ll, 3> extgcd(ll a, ll b) { if (!b) return {a, 1, 0}; auto [d, y, x] = extgcd(b, a % b); return {d, x, y - a/b * x}; } // {gcd, x, y} such that a*x + b*y = gcd(a, b)
ll gcd(ll x, ll y){ return __gcd(x, y); }
ll binpow(ll x, ll p, ll mod){ if (p < 0) return 0; x %= mod; ll ans = 1; while(p){ if (p&1) ans = (ans*x)%mod; x = (x*x)%mod; p >>= 1; } return ans; }
ll invmod(ll x, ll mod=MOD){ return binpow(x, mod-2, mod); }
ll sign(ll x){ if (x < 0) rt -1; rt !!x; }
void FREOPEN(string s){ freopen(string(s + ".in").c_str(), "r", stdin); freopen(string(s + ".out").c_str(), "w", stdout); }
template<class T, class TT> bool mineq(T& a, const TT& b){ if (b < a) {a = b; return true;} return false;}
template<class T, class TT> bool maxeq(T& a, const TT& b){ if (b > a) {a = b; return true;} return false;}
const pll dxy[4] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
const pll dxy8[8] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};

ll n, m, k, q;
ll ar[MAXN];
vll gr[MAXN];
vector<pll> grw[MAXN];
ll ans = INF;

struct Centroids_Tree{
    int root;
    vector<int> label;
    vector<vector<int>> tree, parent;
    Centroids_Tree(const vll gr[], ll n){
        parent.resize(n), tree.resize(n), label.resize(n);
        vector<int> sizes(n, 1);
        function<int(int, int)> siz = [&](int x, int p){
            for(auto i: gr[x]) if (i != p && parent[i].empty()) sizes[x] += siz(i, x);
            return sizes[x];
        }; siz(0, -1);
        function<int(int, int, int)> dfs = [&](int x, int pc, int lab){
            int n = sizes[x];
            for (int ok = 1, p = -1; ok; ){
                ok = 0;
                for(auto i : gr[x]){
                    if (i == p || !parent[i].empty() || sizes[i] <= n/2) cn;
                    ok = 1, p = x;
                    sizes[x] = n - sizes[i];
                    x = i;
                    break;
                }
            }
            if (pc == -1) pc = x;
            parent[x] = parent[pc];
            parent[x].pb(x);
            label[x] = lab;
            for(auto i: gr[x]) if (parent[i].empty()) 
                tree[x].push_back(dfs(i, x, lab+1));
            return x;
        }; 
        root = dfs(0, -1, 0);
    }
};

void dfs(ll x, ll p=-1){
	for(auto [i, w] : grw[x]){
		if (i == p) cn;
		ar[i] = ar[x] + w;
		dfs(i, x);
	}
}

int best_path(int n, int K, int H[][2], int L[]){
	k = K;
	fi(n-1){
		gr[H[i][0]].pb(H[i][1]);
		gr[H[i][1]].pb(H[i][0]);
		grw[H[i][0]].pb({H[i][1], L[i]});
		grw[H[i][1]].pb({H[i][0], L[i]});
	}
	Centroids_Tree ctree(gr, n);
	dfs(0);
    fi(n){
        int rlab = ctree.label[i];
        map<ll, ll> cur, sub;
        function<void(map<ll,ll>&, ll, ll)> add = [&](map<ll,ll>& mp, ll key, ll val){
            ll &posv = mp[key];
            if (posv) mineq(posv, val);
            else posv = val;
        };
        function<void(int, int, int, int)> dfs = [&](int x, int p, int cnte, int len){
            if (ctree.label[x] < rlab) return;
            add(sub, len, cnte);
            for(auto [i, w] : grw[x]) if (i != p) dfs(i, x, cnte+1, len+w);
        };
        cur[0] = 0;
        for(auto [x, w] : grw[i]){
            if (x == i) cn;
            dfs(x, i, 1, w);
            for(auto [len, cnte] : sub){
                if (cur.count(k - len)) mineq(ans, cur[k-len] + cnte);
            }
            for(auto [len, cnte] : sub){
                add(cur, len, cnte);
            }
            sub.clear();
        }
    }
	if (ans == INF) ans = -1;
	rt ans;
}

Compilation message

race.cpp: In function 'void FREOPEN(std::string)':
race.cpp:73:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 | void FREOPEN(string s){ freopen(string(s + ".in").c_str(), "r", stdin); freopen(string(s + ".out").c_str(), "w", stdout); }
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
race.cpp:73:80: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 | void FREOPEN(string s){ freopen(string(s + ".in").c_str(), "r", stdin); freopen(string(s + ".out").c_str(), "w", stdout); }
      |                                                                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14680 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 4 ms 14684 KB Output is correct
4 Correct 3 ms 14680 KB Output is correct
5 Correct 3 ms 14684 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 3 ms 14684 KB Output is correct
8 Correct 4 ms 14680 KB Output is correct
9 Correct 3 ms 14684 KB Output is correct
10 Correct 3 ms 14684 KB Output is correct
11 Correct 4 ms 14684 KB Output is correct
12 Correct 4 ms 14680 KB Output is correct
13 Correct 3 ms 14684 KB Output is correct
14 Correct 3 ms 14684 KB Output is correct
15 Correct 3 ms 14684 KB Output is correct
16 Correct 3 ms 14684 KB Output is correct
17 Correct 3 ms 14684 KB Output is correct
18 Correct 3 ms 14684 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14680 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 4 ms 14684 KB Output is correct
4 Correct 3 ms 14680 KB Output is correct
5 Correct 3 ms 14684 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 3 ms 14684 KB Output is correct
8 Correct 4 ms 14680 KB Output is correct
9 Correct 3 ms 14684 KB Output is correct
10 Correct 3 ms 14684 KB Output is correct
11 Correct 4 ms 14684 KB Output is correct
12 Correct 4 ms 14680 KB Output is correct
13 Correct 3 ms 14684 KB Output is correct
14 Correct 3 ms 14684 KB Output is correct
15 Correct 3 ms 14684 KB Output is correct
16 Correct 3 ms 14684 KB Output is correct
17 Correct 3 ms 14684 KB Output is correct
18 Correct 3 ms 14684 KB Output is correct
19 Correct 3 ms 14768 KB Output is correct
20 Correct 3 ms 14684 KB Output is correct
21 Correct 4 ms 14940 KB Output is correct
22 Correct 5 ms 14940 KB Output is correct
23 Correct 5 ms 14940 KB Output is correct
24 Correct 5 ms 14940 KB Output is correct
25 Correct 4 ms 14940 KB Output is correct
26 Correct 4 ms 14940 KB Output is correct
27 Correct 4 ms 15028 KB Output is correct
28 Correct 4 ms 14940 KB Output is correct
29 Correct 5 ms 14940 KB Output is correct
30 Correct 5 ms 14940 KB Output is correct
31 Correct 4 ms 14940 KB Output is correct
32 Correct 5 ms 14936 KB Output is correct
33 Correct 5 ms 14940 KB Output is correct
34 Correct 5 ms 15064 KB Output is correct
35 Correct 4 ms 14940 KB Output is correct
36 Correct 4 ms 14940 KB Output is correct
37 Correct 5 ms 14940 KB Output is correct
38 Correct 5 ms 14940 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14680 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 4 ms 14684 KB Output is correct
4 Correct 3 ms 14680 KB Output is correct
5 Correct 3 ms 14684 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 3 ms 14684 KB Output is correct
8 Correct 4 ms 14680 KB Output is correct
9 Correct 3 ms 14684 KB Output is correct
10 Correct 3 ms 14684 KB Output is correct
11 Correct 4 ms 14684 KB Output is correct
12 Correct 4 ms 14680 KB Output is correct
13 Correct 3 ms 14684 KB Output is correct
14 Correct 3 ms 14684 KB Output is correct
15 Correct 3 ms 14684 KB Output is correct
16 Correct 3 ms 14684 KB Output is correct
17 Correct 3 ms 14684 KB Output is correct
18 Correct 3 ms 14684 KB Output is correct
19 Correct 263 ms 41428 KB Output is correct
20 Correct 254 ms 42300 KB Output is correct
21 Correct 238 ms 41908 KB Output is correct
22 Correct 239 ms 41552 KB Output is correct
23 Correct 295 ms 46636 KB Output is correct
24 Correct 145 ms 38736 KB Output is correct
25 Correct 191 ms 52684 KB Output is correct
26 Correct 105 ms 55020 KB Output is correct
27 Correct 411 ms 60936 KB Output is correct
28 Correct 1062 ms 113664 KB Output is correct
29 Correct 1083 ms 112628 KB Output is correct
30 Correct 417 ms 61592 KB Output is correct
31 Correct 383 ms 61512 KB Output is correct
32 Correct 513 ms 61152 KB Output is correct
33 Correct 632 ms 72228 KB Output is correct
34 Correct 1053 ms 87820 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14680 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 4 ms 14684 KB Output is correct
4 Correct 3 ms 14680 KB Output is correct
5 Correct 3 ms 14684 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 3 ms 14684 KB Output is correct
8 Correct 4 ms 14680 KB Output is correct
9 Correct 3 ms 14684 KB Output is correct
10 Correct 3 ms 14684 KB Output is correct
11 Correct 4 ms 14684 KB Output is correct
12 Correct 4 ms 14680 KB Output is correct
13 Correct 3 ms 14684 KB Output is correct
14 Correct 3 ms 14684 KB Output is correct
15 Correct 3 ms 14684 KB Output is correct
16 Correct 3 ms 14684 KB Output is correct
17 Correct 3 ms 14684 KB Output is correct
18 Correct 3 ms 14684 KB Output is correct
19 Correct 3 ms 14768 KB Output is correct
20 Correct 3 ms 14684 KB Output is correct
21 Correct 4 ms 14940 KB Output is correct
22 Correct 5 ms 14940 KB Output is correct
23 Correct 5 ms 14940 KB Output is correct
24 Correct 5 ms 14940 KB Output is correct
25 Correct 4 ms 14940 KB Output is correct
26 Correct 4 ms 14940 KB Output is correct
27 Correct 4 ms 15028 KB Output is correct
28 Correct 4 ms 14940 KB Output is correct
29 Correct 5 ms 14940 KB Output is correct
30 Correct 5 ms 14940 KB Output is correct
31 Correct 4 ms 14940 KB Output is correct
32 Correct 5 ms 14936 KB Output is correct
33 Correct 5 ms 14940 KB Output is correct
34 Correct 5 ms 15064 KB Output is correct
35 Correct 4 ms 14940 KB Output is correct
36 Correct 4 ms 14940 KB Output is correct
37 Correct 5 ms 14940 KB Output is correct
38 Correct 5 ms 14940 KB Output is correct
39 Correct 263 ms 41428 KB Output is correct
40 Correct 254 ms 42300 KB Output is correct
41 Correct 238 ms 41908 KB Output is correct
42 Correct 239 ms 41552 KB Output is correct
43 Correct 295 ms 46636 KB Output is correct
44 Correct 145 ms 38736 KB Output is correct
45 Correct 191 ms 52684 KB Output is correct
46 Correct 105 ms 55020 KB Output is correct
47 Correct 411 ms 60936 KB Output is correct
48 Correct 1062 ms 113664 KB Output is correct
49 Correct 1083 ms 112628 KB Output is correct
50 Correct 417 ms 61592 KB Output is correct
51 Correct 383 ms 61512 KB Output is correct
52 Correct 513 ms 61152 KB Output is correct
53 Correct 632 ms 72228 KB Output is correct
54 Correct 1053 ms 87820 KB Output is correct
55 Correct 26 ms 17500 KB Output is correct
56 Correct 16 ms 16988 KB Output is correct
57 Correct 150 ms 45396 KB Output is correct
58 Correct 58 ms 35644 KB Output is correct
59 Correct 329 ms 62828 KB Output is correct
60 Correct 1128 ms 112060 KB Output is correct
61 Correct 416 ms 62508 KB Output is correct
62 Correct 400 ms 61364 KB Output is correct
63 Correct 575 ms 61496 KB Output is correct
64 Correct 1147 ms 76592 KB Output is correct
65 Correct 1062 ms 80444 KB Output is correct
66 Correct 1149 ms 107620 KB Output is correct
67 Correct 201 ms 56620 KB Output is correct
68 Correct 579 ms 69968 KB Output is correct
69 Correct 675 ms 68536 KB Output is correct
70 Correct 626 ms 68328 KB Output is correct