Submission #387256

#	Time	Username	Problem	Language	Result	Execution time	Memory
387256		galen_colin	Factories (JOI14_factories)	C++17	15 / 100	2375 ms	175636 KiB

factories

#include "bits/stdc++.h"
#ifndef galen_colin_local
	
#include "factories.h"
 
#endif
using namespace std;
 
/* 
find my code templates at https://github.com/galencolin/cp-templates
also maybe subscribe please thanks 
*/
 
#define send {ios_base::sync_with_stdio(false);}
#define help {cin.tie(NULL);}
#define f first
#define s second
#define getunique(v) {sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());}
typedef long long ll;
typedef long double lld;
typedef unsigned long long ull;
 
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) {
	cout << "["; for(int i = 0; i < v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";
}
template<typename A, typename B> istream& operator>>(istream& cin, pair<A, B> &p) {
	cin >> p.first;
	return cin >> p.second;
}
 
mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
// mt19937_64 rng(61378913);
/* usage - just do rng() */
 
void usaco(string filename) {
  // #pragma message("be careful, freopen may be wrong")
	freopen((filename + ".in").c_str(), "r", stdin);
	freopen((filename + ".out").c_str(), "w", stdout);
}
 
// #include <atcoder/all>
// using namespace atcoder;
 
const lld pi = 3.14159265358979323846;
const ll mod = 1000000007;
// const ll mod = 998244353;
// ll mod;
 
 
 
ll n, m, q, k, l, r, x, y, z;
const ll template_array_size = 1e6 + 14742;
int a[template_array_size];
int b[template_array_size];
int c[template_array_size];
string s, t;
ll ans = 0;	
 
vector<pair<int, ll>> dist[500005];
ll best[500005];
 
struct centroid {
  vector<vector<pair<ll, ll>> > edges;
  vector<bool> vis;
  vector<int> par;
  vector<int> sz;
  int n;
 
  void init(int s) {
    n = s;
    edges = vector<vector<pair<ll, ll>> >(n, vector<pair<ll, ll>>());
    vis = vector<bool>(n, 0);
    par = vector<int>(n);
    sz = vector<int>(n);
  }
 
  void edge(ll a, ll b, ll c) {
    edges[a].push_back({b, c});
    edges[b].push_back({a, c});
  }
 
  int find_size(int v, int p = -1) {
    if (vis[v]) return 0;
    sz[v] = 1;
 
    for (pair<ll, ll> x: edges[v]) {
      if (x.f != p) {
        sz[v] += find_size(x.f, v);
      }
    }
 
    return sz[v];
  }
 
  int find_centroid(int v, int p, int n) {
    for (pair<ll, ll> x: edges[v]) {
      if (x.f != p) {
        if (!vis[x.f] && sz[x.f] > n / 2) {
          return find_centroid(x.f, v, n);
        }
      }
    }
 
    return v;
  }
  
  void set_dists(ll v, ll p, ll d, ll c) {
	  dist[c].push_back({v, d});
	  
	  for (pair<ll, ll> x: edges[v]) {
		  if (x.f != p && !vis[x.f]) {
			  set_dists(x.f, v, d + x.s, c);
		  }
	  }
  }
 
  void init_centroid(int v = 0, int p = -1) {
    find_size(v);
 
    int c = find_centroid(v, -1, sz[v]);
	set_dists(c, -1, 0, c);
    vis[c] = true;
    par[c] = p;
 
    for (pair<ll, ll> x: edges[c]) {
      if (!vis[x.f]) {
        init_centroid(x.f, c);
      }
    }
  }
};
 
centroid cd;
 
void Init(int _n, int aa[], int bb[], int dd[]) {
	n = _n;
	cd.init(n);
	memset(best, 1, sizeof(best));
	
	for (ll i = 0; i < n - 1; i++) {
		cd.edge(aa[i], bb[i], dd[i]);
	}
	
	cd.init_centroid();
	for (ll i = 0; i < n; i++) sort(dist[i].begin(), dist[i].end());
}

ll dists(int c, int v) {
	int l = 0, r = dist[c].size();
	while (l < r) {
		int m = (l + r) / 2;
		
		if (dist[c][m].f >= v) r = m;
		else l = m + 1;
	}
	return dist[c][l].s;
}
 
void reset(int v) {
	int c = v;
	do {
		best[c] = 1e17;
		c = cd.par[c];
	} while (c != -1);
}
 
void push(int v) {
	int c = v;
	do {
		best[c] = min(best[c], dists(c, v));
		c = cd.par[c];
	} while (c != -1);
}
 
void pull(int v) {
	int c = v;
	do {
		ans = min(ans, best[c] + dists(c, v));
		c = cd.par[c];
	} while (c != -1);
}
 
ll Query(int s, int x[], int t, int y[]) {
	// cout << s << " " << t << endl;
	if (n <= 5000) {
		for (int i = 0; i < s; i++) reset(x[i]);
		for (int i = 0; i < t; i++) reset(y[i]);
		for (int i = 0; i < s; i++) push(x[i]);
		ans = 1e17;
		for (int i = 0; i < t; i++) pull(y[i]);
	}
	return ans;
}
 
#ifdef galen_colin_local
	void solve(int tc = 0) {
		// cin >> n >> q;
		ll n = 500000, q = 10000;
		
		for (ll i = 0; i < n - 1; i++) {
			a[i] = i, b[i] = i + 1, c[i] = rng() % 1000000000;
			// cin >> a[i] >> b[i] >> c[i];
		}
		
		Init(n, a, b, c);
		
		for (ll i = 0; i < q; i++) {
			// ll s, t;
			// cin >> s >> t;
			ll s = 10, t = 10;
			// for (ll j = 0; j < s; j++) cin >> a[j];
			// for (ll j = 0; j < t; j++) cin >> b[j];
			for (ll j = 0; j < s; j++) a[j] = rng() % n;
			for (ll j = 0; j < t; j++) b[j] = rng() % n;
			// cout << Query(s, a, t, b) << '\n';
			Query(s, a, t, b);
		}
	}
 
	int main() {
		#ifdef galen_colin_local
			auto begin = std::chrono::high_resolution_clock::now();
		#endif
		
		send help
	 
		#ifndef galen_colin_local
			// usaco("code");
		#endif
		
		// usaco("cowland");
		
		// freopen("tc.cpp", "r", stdin);
		// freopen("tc2.cpp", "w", stdout);
			
		cout << setprecision(15) << fixed;
									
		int tc = 1;
		// cin >> tc;
		for (int t = 0; t < tc; t++) solve(t);
		
		#ifdef galen_colin_local
			auto end = std::chrono::high_resolution_clock::now();
			cerr << setprecision(4) << fixed;
			cerr << "Execution time: " << std::chrono::duration_cast<std::chrono::duration<double>>(end - begin).count() << " seconds" << endl;
		#endif
	} 
#endif

Compilation message (stderr)

factories.cpp: In function 'void usaco(std::string)':
factories.cpp:39:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   39 |  freopen((filename + ".in").c_str(), "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
factories.cpp:40:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   40 |  freopen((filename + ".out").c_str(), "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67