답안 #387256

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
387256 2021-04-08T07:40:49 Z galen_colin 공장들 (JOI14_factories) C++17
15 / 100
2375 ms 175636 KB
#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

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);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 16364 KB Output is correct
2 Correct 1208 ms 25200 KB Output is correct
3 Correct 1691 ms 25708 KB Output is correct
4 Correct 1676 ms 25892 KB Output is correct
5 Correct 1979 ms 26476 KB Output is correct
6 Correct 480 ms 24812 KB Output is correct
7 Correct 1674 ms 25900 KB Output is correct
8 Correct 1752 ms 25836 KB Output is correct
9 Correct 1980 ms 26376 KB Output is correct
10 Correct 478 ms 24812 KB Output is correct
11 Correct 1667 ms 25716 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 16236 KB Output is correct
2 Incorrect 2375 ms 175636 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 16364 KB Output is correct
2 Correct 1208 ms 25200 KB Output is correct
3 Correct 1691 ms 25708 KB Output is correct
4 Correct 1676 ms 25892 KB Output is correct
5 Correct 1979 ms 26476 KB Output is correct
6 Correct 480 ms 24812 KB Output is correct
7 Correct 1674 ms 25900 KB Output is correct
8 Correct 1752 ms 25836 KB Output is correct
9 Correct 1980 ms 26376 KB Output is correct
10 Correct 478 ms 24812 KB Output is correct
11 Correct 1667 ms 25716 KB Output is correct
12 Correct 14 ms 16236 KB Output is correct
13 Incorrect 2375 ms 175636 KB Output isn't correct
14 Halted 0 ms 0 KB -