Submission #464203

#	Time	Username	Problem	Language	Result	Execution time	Memory
464203		ezdp	Race (IOI11_race)	C++14	21 / 100	3069 ms	20932 KiB

race

#pragma GCC target ("sse4")
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>

#define endl '\n'
#define pb push_back
#define fr first
#define sc second
#define ll long long int
#define ld long double
#define bit(idx) idx&(-idx)
#define bin(x) bitset<32>(x).to_string()
#define all(A) A.begin(), A.end()
#define de(x) cout << #x << " = " << x << endl;

using namespace std;
using namespace __gnu_pbds;

template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> using matrix = vector<vector<T>>;
/// find_by_order(x) -> x-th element in the set
/// order_of_key(x)  -> how many elements are smaller than x
/// insert(x)		 -> inserts x into the set

const ll MAXN = 2e5 + 5;
const ll MAXK = 1e6 + 6;
const ll INF = 1e16 + 16;

ll n, k, ans = INF, used[MAXN], sz[MAXN], mn[MAXK];
matrix<pair<ll, ll>> G;

void dfs_ans(ll u, ll p, ll len, ll depth){
	if(len > k) return;
	
	ans = min(ans, mn[k - len] + depth);
	
	for(auto [v, l] : G[u]){
		if(!used[v] && v != p){
			dfs_ans(v, u, len + l, depth + 1);
		}
	}
}


void dfs_add(ll u, ll p, ll len, ll depth){
	if(len > k) return;
	
	mn[len] = min(mn[len], depth);
	
	for(auto [v, l] : G[u]){
		if(!used[v] && v != p){
			dfs_add(v, u, len + l, depth + 1);
		}
	}
}


void dfs_clear(ll u, ll p, ll len, ll depth){
	if(len > k) return;
	
	mn[len] = INF;
	
	for(auto [v, l] : G[u]){
		if(!used[v] && v != p){
			dfs_clear(v, u, len + l, depth + 1);
		}
	}
}

ll find_size(ll u, ll p = -1){
	if(!used[u]) return 0;
	sz[u] = 1;
	for(auto [v, l] : G[u]){
		if(v != p && !used[v]){
			sz[u] += find_size(v, u);
		}
	}
	return sz[u];
}

ll find_centroid(ll u, ll p, ll cn){
	for(auto [v, l] : G[u]){
		if(sz[v] > cn / 2 && v != p && !used[v]){
			return find_centroid(v, u, cn);
		}
	}
	return u;
}

void init_centroid(ll u = 1, ll p = -1){
	find_size(u);
	ll c = find_centroid(u, -1, sz[u]);
	mn[0] = 0;
	for(auto [v, l] : G[c]){
		if(!used[v]){
			dfs_ans(v, c, l, 1);
			dfs_add(v, c, l, 1);
		}
	}
	
	dfs_clear(c, c, 0, 0);
	used[c] = true;
	for(auto [v, l] : G[c]){
		if(!used[v]){
			init_centroid(v, c);
		}
	}
}

int best_path(int N, int K, int h[][2], int L[]){
	n = N; k = K;
	G = matrix<pair<ll, ll>>(n + 1);
	for(int i = 0; i < n - 1; i ++){ G[h[i][0]].pb({h[i][1], L[i]}); G[h[i][1]].pb({h[i][0], L[i]}); }
	for(int i = 0; i < MAXK; i ++) mn[i] = INF;
	
	init_centroid();
	
	return (ans == INF ? -1 : ans);
}


/**
int main(){
	int N, K; cin >> N >> K;
	int h[N][2], L[N];
	for(int i = 0; i < N - 1; i ++) cin >> h[i][0] >> h[i][1] >> L[i];
	cout << best_path(N, K, h, L) << endl;
}



*/

Compilation message (stderr)

race.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("O3")
      | 
race.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("unroll-loops")
      | 
race.cpp: In function 'void dfs_ans(long long int, long long int, long long int, long long int)':
race.cpp:41:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |  for(auto [v, l] : G[u]){
      |           ^
race.cpp: In function 'void dfs_add(long long int, long long int, long long int, long long int)':
race.cpp:54:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   54 |  for(auto [v, l] : G[u]){
      |           ^
race.cpp: In function 'void dfs_clear(long long int, long long int, long long int, long long int)':
race.cpp:67:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   67 |  for(auto [v, l] : G[u]){
      |           ^
race.cpp: In function 'long long int find_size(long long int, long long int)':
race.cpp:77:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   77 |  for(auto [v, l] : G[u]){
      |           ^
race.cpp: In function 'long long int find_centroid(long long int, long long int, long long int)':
race.cpp:86:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   86 |  for(auto [v, l] : G[u]){
      |           ^
race.cpp: In function 'void init_centroid(long long int, long long int)':
race.cpp:98:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   98 |  for(auto [v, l] : G[c]){
      |           ^
race.cpp:107:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  107 |  for(auto [v, l] : G[c]){
      |           ^

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