oj.uz

Submission #767580

# Submission time Handle Problem Language Result Execution time Memory
767580 2023-06-26T21:10:38 Z bLIC Museum (CEOI17_museum) C++17
100 / 100
 404 ms 784288 KB 
/**
 *  Author: Anil Byar
**/
 
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
 
// using namespace __gnu_pbds;
using namespace std;
 
// template<class T>
// using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
 
 
 
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)(x).size()
#define uniq(v) v.erase(unique(all(v)), v.end())
#define ft first
#define sd second
#define pb push_back
#define eb emplace_back
 
// Source: https://codeforces.com/blog/entry/68809
// { start
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
// } end
 
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<pll> vll;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
typedef vector<vl> vvl;
 
#define dbg if(0)
 
const ll MOD = 1e9+7;
const ll MOD9 = 998244353;
const ll INFLL = 1e18+5;
const int INF = 1e9;
 
void printbit(int x, int len) {string s="\n";while(len--){s=((x%2)?'1':'0')+s;x/=2;} cout<<s;}
ll power(ll x, ll y, ll mod){if (y==0) return 1;ll ret = power(x, y/2, mod);ret *= ret;ret%=mod;if (y&1) ret *= x;return ret%mod;}
ll modinv(ll x, ll mod = MOD) {return power(x, mod-2, mod);}
 

template<class T> bool chmin(T& a, T b){return (a>b?a=b,1:0);}
template<class T> bool chmax(T& a, T b){return (a<b?a=b,1:0);}
template<class T>
istream& operator>>(istream&in, vector<T>&v){
	for (T& x:v) in>>x;
	return in;
}
template<class T>
ostream& operator<<(ostream&out, vector<T>&v){
	for (T& x:v) out<<x<<' ';
	cout<<'\n';
	return out;
}
// use ?: with brackets (?:)
// check for overflow
// think about dp
// Read the statement carefully
 
const int N = 10001;
 
vii adj[N];
int n, k, x;
int dp[N][2][N];
int stree[N];
 
void dfs(int node, int par){
	dp[node][0][0] = dp[node][1][0] = 0;
	dp[node][0][1] = dp[node][1][1] = 0;
	stree[node] = 1;
 
	for (int i = 0;i<sz(adj[node]);i++){
		auto z = adj[node][i];
		adj[z.ft].erase(find(all(adj[z.ft]), make_pair(node, z.sd)));
		dfs(z.ft, node);
 
		for (int j = stree[node];j>=0;j--){
			for (int l = stree[z.ft];l>=0;l--){
				chmin(dp[node][0][j+l], min(dp[node][0][j]+dp[z.ft][1][l] + 2*z.sd, dp[node][1][j]+dp[z.ft][0][l]+z.sd));
				chmin(dp[node][1][j+l], dp[node][1][j]+dp[z.ft][1][l]+2*z.sd);
			}
		}
		stree[node] += stree[z.ft];
	}
}
 
void solve(){
	cin>>n>>k>>x;
	for (int i = 0;i<n-1;i++){
		int u, v, w;cin>>u>>v>>w;
		adj[u].eb(v, w);
		adj[v].eb(u, w);
	}
	memset(dp, 63, sizeof(dp));
	dfs(x, -1);
	cout<<dp[x][0][k];
}
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
 
 
#define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
	freopen("input.in", "r", stdin);
	freopen("output.out", "w", stdout);
	freopen("debug.dbg", "w", stderr);
	int tt = clock();
#endif
 
	int t=1, i = 1;
	// cin>>t;
	while(t--){
		// cout<<"Case #"<<i++<<": ";
		solve();
		cout<<'\n';
	}
#ifndef ONLINE_JUDGE
	cerr << "TIME = " << (float)(clock() - tt)/CLOCKS_PER_SEC << endl;
	tt = clock();
#endif
}

Compilation message

museum.cpp: In function 'int main()':
museum.cpp:151:11: warning: unused variable 'i' [-Wunused-variable]
  151 |  int t=1, i = 1;
      |           ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 783456 KB Output is correct
2 Correct 232 ms 783396 KB Output is correct
3 Correct 237 ms 783420 KB Output is correct
4 Correct 230 ms 783524 KB Output is correct
5 Correct 230 ms 783436 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 783848 KB Output is correct
2 Correct 309 ms 783908 KB Output is correct
3 Correct 341 ms 784192 KB Output is correct
4 Correct 342 ms 784084 KB Output is correct
5 Correct 315 ms 783800 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 783848 KB Output is correct
2 Correct 309 ms 783908 KB Output is correct
3 Correct 341 ms 784192 KB Output is correct
4 Correct 342 ms 784084 KB Output is correct
5 Correct 315 ms 783800 KB Output is correct
6 Correct 315 ms 784044 KB Output is correct
7 Correct 331 ms 784036 KB Output is correct
8 Correct 404 ms 783824 KB Output is correct
9 Correct 367 ms 783912 KB Output is correct
10 Correct 378 ms 783936 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 783456 KB Output is correct
2 Correct 232 ms 783396 KB Output is correct
3 Correct 237 ms 783420 KB Output is correct
4 Correct 230 ms 783524 KB Output is correct
5 Correct 230 ms 783436 KB Output is correct
6 Correct 305 ms 783848 KB Output is correct
7 Correct 309 ms 783908 KB Output is correct
8 Correct 341 ms 784192 KB Output is correct
9 Correct 342 ms 784084 KB Output is correct
10 Correct 315 ms 783800 KB Output is correct
11 Correct 315 ms 784044 KB Output is correct
12 Correct 331 ms 784036 KB Output is correct
13 Correct 404 ms 783824 KB Output is correct
14 Correct 367 ms 783912 KB Output is correct
15 Correct 378 ms 783936 KB Output is correct
16 Correct 312 ms 783912 KB Output is correct
17 Correct 310 ms 783880 KB Output is correct
18 Correct 336 ms 784128 KB Output is correct
19 Correct 376 ms 783912 KB Output is correct
20 Correct 326 ms 783964 KB Output is correct
21 Correct 331 ms 784036 KB Output is correct
22 Correct 318 ms 783820 KB Output is correct
23 Correct 400 ms 783924 KB Output is correct
24 Correct 337 ms 783836 KB Output is correct
25 Correct 360 ms 784288 KB Output is correct