Submission #388754

#	Time	Username	Problem	Language	Result	Execution time	Memory
388754		SavicS	Race (IOI11_race)	C++14	100 / 100	1117 ms	48512 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;
		}
 
		cuvaj.clear();      
	}
 
	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:103:7: warning: unused variable 'w' [-Wunused-variable]
  103 |   int w = c.se;
      |       ^

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