oj.uz

Submission #548989

# Submission time Handle Problem Language Result Execution time Memory
548989 2022-04-14T22:12:48 Z Bungmint Race (IOI11_race) C++17
100 / 100
 693 ms 126880 KB 
//Copyright © 2022 Youngmin Park. All rights reserved.
//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;
using vpi = vector<pii>;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vpl = vector<pll>;
using ld = long double;
template <typename T, size_t SZ>
using ar = array<T, SZ>;

#define all(v) (v).begin(), (v).end()
#define pb push_back
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i, a) ROF(i, 0, a)
#define REP(a) F0R(_, a)

const int INF = 1e9;
const ll LINF = 1e18;
const int MOD = 1e9 + 7; //998244353;
const ld PI = acos((ld)-1.0);
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
template <typename T>
bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template <typename T>
bool ckmax(T &a, const T &b) { return b > a ? a = b, 1 : 0; }

template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p)
{
    return os << '(' << p.first << ", " << p.second << ')';
}
template <typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type>
ostream &operator<<(ostream &os, const T_container &v)
{
    os << '{';
    string sep;
    for (const T &x : v)
        os << sep << x, sep = ", ";
    return os << '}';
}
void dbg_out()
{
    cerr << endl;
}
template <typename Head, typename... Tail>
void dbg_out(Head H, Tail... T)
{
    cerr << ' ' << H;
    dbg_out(T...);
}
#ifdef LOCAL
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...) 42
#endif

inline namespace RecursiveLambda{
	template <typename Fun>
	struct y_combinator_result{
		Fun fun_;
		template <typename T> 
		explicit y_combinator_result(T &&fun): fun_(forward<T>(fun)){}
		template <typename...Args>
		decltype(auto) operator()(Args &&...args){
			return fun_(ref(*this), forward<Args>(args)...);
		}
	};
	template <typename Fun>
	decltype(auto) y_combinator(Fun &&fun){
		return y_combinator_result<decay_t<Fun>>(forward<Fun>(fun));
	}
};

void setIO(string s) // USACO
{
	#ifndef LOCAL
	    freopen((s + ".in").c_str(), "r", stdin);
	    freopen((s + ".out").c_str(), "w", stdout);
	#endif
}


const int MN = 1e6;
const int MX = 2e5;
vpi adj[MX];
vi v[MX];
pair<int, ll> up[20][MX];
int sub[MX], depth[MX];
int targ;
int ans = INF;
ll shift = 0;
map<ll, int> cnt;
int extra = 0;
void init(int u, int pu) {
	sub[u] = 1;
	for (auto &[e, w] : adj[u]) {
		if (e == pu) continue;
		depth[e] = depth[u] + 1;
		up[0][e] = {u, w};
		FOR(i, 1, 20) {
			auto [nxt, d] = up[i - 1][e];
			up[i][e].fi = up[i - 1][nxt].fi;
			up[i][e].se = up[i - 1][nxt].se + d;
		}
		init(e, u);
		sub[u] += sub[e];
	}
}
ll dist(int u, int v) { // u is a descendant
	int d = depth[u] - depth[v];
	ll res = 0;
	R0F(i, 20) {
		if (d & (1 << i)) {
			res += up[i][u].se;
			u = up[i][u].fi;
		}
	}
	return res;
}
void dfs(int u, int pu, bool keep) {
	int mx = 0, big = -1;
	int dd = 0;
	for (auto &[e, w] : adj[u]) {
		if (e == pu) continue;
		if (ckmax(mx, sub[e])) big = e, dd = w;
	}
	for (auto &[e, w] : adj[u]) {
		if (e == pu || e == big) continue;
		dfs(e, u, 0);
	}
	if (big != -1) {
		dfs(big, u, 1);
		shift += dd;
		swap(v[u], v[big]);
		extra++;
	}
	v[u].pb(u);
	if (cnt.count(targ - shift)) ckmin(ans, cnt[targ - shift] + extra);
	ckmin(cnt[-shift], -extra);
	for (auto &[e, w] : adj[u]) {
		if (e == pu || e == big) continue;
		for (auto &x : v[e]) {
			v[u].pb(x);
			ll y = dist(x, u);
			if (cnt.count(targ - y - shift)) ckmin(ans, cnt[targ - y - shift] + depth[x] - depth[u] + extra);
		}
		for (auto &x : v[e]) {
			ll y = dist(x, u);
			if (cnt.count(y - shift)) ckmin(cnt[y - shift], -extra + depth[x] - depth[u]);
			else cnt[y - shift] = -extra + depth[x] - depth[u];
		}
		v[e].clear();
	}
	
	if (!keep) cnt.clear(), extra = shift = 0;
	
}
int best_path(int N, int K, int H[][2], int L[]) {
	targ = K;
	FOR(i, 0, N - 1) {
		auto u = H[i][0];
		auto vv = H[i][1];
		adj[u].pb({vv, L[i]});
		adj[vv].pb({u, L[i]});
	}
	init(0, -1);
	dfs(0, -1, 0);
	return (ans == INF ? -1 : ans);
}

// void solve()
// {
	// int n, k;
	// cin >> n >> k;
	// int h[n - 1][2];
	// int l[n - 1];
	// F0R(i, n - 1) cin >> h[i][0] >> h[i][1];
	// F0R(i, n - 1) cin >> l[i];
	// cout << best_path(n, k, h, l) << '\n';
// }
// 
// int main()
// {
    // cin.tie(0)->sync_with_stdio(0);
    // cin.exceptions(cin.failbit);
    // int testcase=1;
    // // cin >> testcase;
    // while (testcase--)
    // {
        // solve();
    // }
// }

Compilation message

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

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9940 KB Output is correct
2 Correct 5 ms 9828 KB Output is correct
3 Correct 5 ms 9940 KB Output is correct
4 Correct 5 ms 9844 KB Output is correct
5 Correct 5 ms 9848 KB Output is correct
6 Correct 5 ms 9836 KB Output is correct
7 Correct 5 ms 9940 KB Output is correct
8 Correct 5 ms 9840 KB Output is correct
9 Correct 6 ms 9832 KB Output is correct
10 Correct 6 ms 9840 KB Output is correct
11 Correct 6 ms 9940 KB Output is correct
12 Correct 6 ms 9836 KB Output is correct
13 Correct 6 ms 10068 KB Output is correct
14 Correct 6 ms 9840 KB Output is correct
15 Correct 5 ms 9940 KB Output is correct
16 Correct 5 ms 9940 KB Output is correct
17 Correct 5 ms 9940 KB Output is correct
18 Correct 5 ms 9888 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9940 KB Output is correct
2 Correct 5 ms 9828 KB Output is correct
3 Correct 5 ms 9940 KB Output is correct
4 Correct 5 ms 9844 KB Output is correct
5 Correct 5 ms 9848 KB Output is correct
6 Correct 5 ms 9836 KB Output is correct
7 Correct 5 ms 9940 KB Output is correct
8 Correct 5 ms 9840 KB Output is correct
9 Correct 6 ms 9832 KB Output is correct
10 Correct 6 ms 9840 KB Output is correct
11 Correct 6 ms 9940 KB Output is correct
12 Correct 6 ms 9836 KB Output is correct
13 Correct 6 ms 10068 KB Output is correct
14 Correct 6 ms 9840 KB Output is correct
15 Correct 5 ms 9940 KB Output is correct
16 Correct 5 ms 9940 KB Output is correct
17 Correct 5 ms 9940 KB Output is correct
18 Correct 5 ms 9888 KB Output is correct
19 Correct 5 ms 9836 KB Output is correct
20 Correct 5 ms 9812 KB Output is correct
21 Correct 6 ms 10196 KB Output is correct
22 Correct 7 ms 10324 KB Output is correct
23 Correct 7 ms 10360 KB Output is correct
24 Correct 7 ms 10240 KB Output is correct
25 Correct 7 ms 10364 KB Output is correct
26 Correct 7 ms 10312 KB Output is correct
27 Correct 6 ms 10196 KB Output is correct
28 Correct 7 ms 10348 KB Output is correct
29 Correct 8 ms 10324 KB Output is correct
30 Correct 7 ms 10352 KB Output is correct
31 Correct 7 ms 10452 KB Output is correct
32 Correct 8 ms 10324 KB Output is correct
33 Correct 7 ms 10360 KB Output is correct
34 Correct 6 ms 10196 KB Output is correct
35 Correct 7 ms 10252 KB Output is correct
36 Correct 6 ms 10232 KB Output is correct
37 Correct 6 ms 10228 KB Output is correct
38 Correct 7 ms 10236 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9940 KB Output is correct
2 Correct 5 ms 9828 KB Output is correct
3 Correct 5 ms 9940 KB Output is correct
4 Correct 5 ms 9844 KB Output is correct
5 Correct 5 ms 9848 KB Output is correct
6 Correct 5 ms 9836 KB Output is correct
7 Correct 5 ms 9940 KB Output is correct
8 Correct 5 ms 9840 KB Output is correct
9 Correct 6 ms 9832 KB Output is correct
10 Correct 6 ms 9840 KB Output is correct
11 Correct 6 ms 9940 KB Output is correct
12 Correct 6 ms 9836 KB Output is correct
13 Correct 6 ms 10068 KB Output is correct
14 Correct 6 ms 9840 KB Output is correct
15 Correct 5 ms 9940 KB Output is correct
16 Correct 5 ms 9940 KB Output is correct
17 Correct 5 ms 9940 KB Output is correct
18 Correct 5 ms 9888 KB Output is correct
19 Correct 238 ms 52060 KB Output is correct
20 Correct 247 ms 52040 KB Output is correct
21 Correct 245 ms 52300 KB Output is correct
22 Correct 229 ms 51972 KB Output is correct
23 Correct 282 ms 52920 KB Output is correct
24 Correct 214 ms 53324 KB Output is correct
25 Correct 165 ms 55984 KB Output is correct
26 Correct 74 ms 62276 KB Output is correct
27 Correct 257 ms 91788 KB Output is correct
28 Correct 417 ms 126880 KB Output is correct
29 Correct 421 ms 124852 KB Output is correct
30 Correct 252 ms 91884 KB Output is correct
31 Correct 262 ms 91868 KB Output is correct
32 Correct 392 ms 91892 KB Output is correct
33 Correct 446 ms 89608 KB Output is correct
34 Correct 554 ms 101944 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9940 KB Output is correct
2 Correct 5 ms 9828 KB Output is correct
3 Correct 5 ms 9940 KB Output is correct
4 Correct 5 ms 9844 KB Output is correct
5 Correct 5 ms 9848 KB Output is correct
6 Correct 5 ms 9836 KB Output is correct
7 Correct 5 ms 9940 KB Output is correct
8 Correct 5 ms 9840 KB Output is correct
9 Correct 6 ms 9832 KB Output is correct
10 Correct 6 ms 9840 KB Output is correct
11 Correct 6 ms 9940 KB Output is correct
12 Correct 6 ms 9836 KB Output is correct
13 Correct 6 ms 10068 KB Output is correct
14 Correct 6 ms 9840 KB Output is correct
15 Correct 5 ms 9940 KB Output is correct
16 Correct 5 ms 9940 KB Output is correct
17 Correct 5 ms 9940 KB Output is correct
18 Correct 5 ms 9888 KB Output is correct
19 Correct 5 ms 9836 KB Output is correct
20 Correct 5 ms 9812 KB Output is correct
21 Correct 6 ms 10196 KB Output is correct
22 Correct 7 ms 10324 KB Output is correct
23 Correct 7 ms 10360 KB Output is correct
24 Correct 7 ms 10240 KB Output is correct
25 Correct 7 ms 10364 KB Output is correct
26 Correct 7 ms 10312 KB Output is correct
27 Correct 6 ms 10196 KB Output is correct
28 Correct 7 ms 10348 KB Output is correct
29 Correct 8 ms 10324 KB Output is correct
30 Correct 7 ms 10352 KB Output is correct
31 Correct 7 ms 10452 KB Output is correct
32 Correct 8 ms 10324 KB Output is correct
33 Correct 7 ms 10360 KB Output is correct
34 Correct 6 ms 10196 KB Output is correct
35 Correct 7 ms 10252 KB Output is correct
36 Correct 6 ms 10232 KB Output is correct
37 Correct 6 ms 10228 KB Output is correct
38 Correct 7 ms 10236 KB Output is correct
39 Correct 238 ms 52060 KB Output is correct
40 Correct 247 ms 52040 KB Output is correct
41 Correct 245 ms 52300 KB Output is correct
42 Correct 229 ms 51972 KB Output is correct
43 Correct 282 ms 52920 KB Output is correct
44 Correct 214 ms 53324 KB Output is correct
45 Correct 165 ms 55984 KB Output is correct
46 Correct 74 ms 62276 KB Output is correct
47 Correct 257 ms 91788 KB Output is correct
48 Correct 417 ms 126880 KB Output is correct
49 Correct 421 ms 124852 KB Output is correct
50 Correct 252 ms 91884 KB Output is correct
51 Correct 262 ms 91868 KB Output is correct
52 Correct 392 ms 91892 KB Output is correct
53 Correct 446 ms 89608 KB Output is correct
54 Correct 554 ms 101944 KB Output is correct
55 Correct 33 ms 14376 KB Output is correct
56 Correct 17 ms 13944 KB Output is correct
57 Correct 146 ms 52980 KB Output is correct
58 Correct 84 ms 52016 KB Output is correct
59 Correct 93 ms 68328 KB Output is correct
60 Correct 410 ms 125376 KB Output is correct
61 Correct 274 ms 93508 KB Output is correct
62 Correct 249 ms 91820 KB Output is correct
63 Correct 392 ms 91956 KB Output is correct
64 Correct 682 ms 100972 KB Output is correct
65 Correct 693 ms 107396 KB Output is correct
66 Correct 420 ms 120500 KB Output is correct
67 Correct 350 ms 95388 KB Output is correct
68 Correct 521 ms 102824 KB Output is correct
69 Correct 490 ms 103968 KB Output is correct
70 Correct 461 ms 98748 KB Output is correct