Submission #388752

#	Time	Username	Problem	Language	Result	Execution time	Memory
388752		SavicS	Race (IOI11_race)	C++14	43 / 100	3097 ms	36300 KiB

race

#include "race.h"

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

#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ff(i,a,b) for(int i=a;i<=b;i++)
#define fb(i,b,a) for(int i=b;i>=a;i--)

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<ll,int> pii;
const int maxn = 200005;
const int inf = 1e9 + 5;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// os.order_of_key(k) the number of elements in the os less than k
// *os.find_by_order(k)  print the k-th smallest number in os(0-based)

int n, K;

vector<pii> g[maxn];

int cnt[maxn];
bool bio[maxn];
void dfs_sz(int v, int p) {
	cnt[v] = 1;
	for(auto c : g[v]) {
		int u = c.fi;
		int w = c.se;
		if(u == p || bio[u])continue;
		dfs_sz(u, v);
		cnt[v] += cnt[u];
	}
}

int centroid(int v, int p, int vel) {
	for(auto c : g[v]) {
		int u = c.fi;
		int w = c.se;
		if(u == p || bio[u])continue;
		if(cnt[u] > vel / 2)return centroid(u, v, vel);
	}
	return v;
}

int rez = inf;

map<ll,int> kol;

vector<pii> cuvaj;
void dfs_calc(int v, int p, ll W, int duz) {
	if(W > K)return;

	cuvaj.pb({W, duz});
	if(kol.count(K - W))rez = min(rez, kol[K - W] + duz);
	
	for(auto c : g[v]) {
		int u = c.fi;
		int w = c.se;
		if(u == p || bio[u])continue;
		
		dfs_calc(u, v, W + w, duz + 1);
	
	}

}

void decompose(int v, int p) {
	dfs_sz(v, p);
	int cen = centroid(v, p, cnt[v]);
	bio[cen] = 1;

	kol.clear();
	cuvaj.clear();
	
	kol[0] = 0;
	for(auto c : g[cen]) {
		int u = c.fi;
		int w = c.se;
		if(u == p || bio[u])continue;
		dfs_calc(u, cen, w, 1);

		for(auto c : cuvaj) {
			if(kol.count(c.fi))kol[c.fi] = min(kol[c.fi], c.se);
			else kol[c.fi] = c.se;
		}

	}

	for(auto c : g[cen]) {
		int u = c.fi;
		int w = c.se;
		if(u == p || bio[u])continue;
		decompose(u, cen);
	}


}

int best_path(int N, int k, int H[][2], int L[]) {
	n = N;
	K = k;
	ff(i,0,n - 2) {
		int u = H[i][0] + 1;
		int v = H[i][1] + 1;
		int w = L[i];
		g[u].pb({v, w});
		g[v].pb({u, w});
	}

	decompose(1, -1);

	return (rez == inf ? -1 : rez);

}

//int main() 
//{
//    ios::sync_with_stdio(false);
//    cout.tie(nullptr);
//    cin.tie(nullptr);
//	cin >> n >> K;
//	ff(i,1,n - 1){
//		int u, v, w;
//		cin >> u >> v >> w;
//		g[u].pb({v, w});
//		g[v].pb({u, w});
//	}
//
//	decompose(1, -1);
//
//	cout << (rez == inf ? -1 : rez) << endl;
//
//	return 0;
//}
/**

3 3
1 2 1
2 3 1

11 12
1 2 3
1 3 4
3 4 5
4 5 4
5 6 6
1 7 3
7 8 2
7 9 5
9 10 6
9 11 7

// probati bojenje sahovski ili slicno

**/

Compilation message (stderr)

race.cpp: In function 'void dfs_sz(int, int)':
race.cpp:39:7: warning: unused variable 'w' [-Wunused-variable]
   39 |   int w = c.se;
      |       ^
race.cpp: In function 'int centroid(int, int, int)':
race.cpp:49:7: warning: unused variable 'w' [-Wunused-variable]
   49 |   int w = c.se;
      |       ^
race.cpp: In function 'void decompose(int, int)':
race.cpp:102:7: warning: unused variable 'w' [-Wunused-variable]
  102 |   int w = c.se;
      |       ^

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