oj.uz

Submission #387194

# Submission time Handle Problem Language Result Execution time Memory
387194 2021-04-08T06:13:06 Z galen_colin Factories (JOI14_factories) C++14
15 / 100
 8000 ms 407712 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;	

map<ll, 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][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[]) {
	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();
}

void reset(ll v) {
	ll c = v;
	do {
		best[c] = 1e17;
		c = cd.par[c];
	} while (c != -1);
}

void push(ll v) {
	ll c = v;
	do {
		best[c] = min(best[c], dist[c][v]);
		c = cd.par[c];
	} while (c != -1);
}

void pull(ll v) {
	ll c = v;
	do {
		ans = min(ans, best[c] + dist[c][v]);
		c = cd.par[c];
	} while (c != -1);
}

ll Query(int s, int x[], int t, int y[]) {
	// cout << s << " " << t << endl;
	for (ll i = 0; i < s; i++) reset(x[i]);
	for (ll i = 0; i < t; i++) reset(y[i]);
	for (ll i = 0; i < s; i++) push(x[i]);
	ans = 1e17;
	for (ll i = 0; i < t; i++) pull(y[i]);
	return ans;
}

#ifdef galen_colin_local
	void solve(int tc = 0) {
		cin >> n >> q;
		
		for (ll i = 0; i < n - 1; i++) {
			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;
			for (ll j = 0; j < s; j++) cin >> a[j];
			for (ll j = 0; j < t; j++) cin >> b[j];
			cout << Query(s, a, t, b) << '\n';
		}
	}

	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);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 28396 KB Output is correct
2 Correct 1801 ms 47868 KB Output is correct
3 Correct 2809 ms 48916 KB Output is correct
4 Correct 2692 ms 48580 KB Output is correct
5 Correct 3465 ms 49628 KB Output is correct
6 Correct 551 ms 46376 KB Output is correct
7 Correct 2888 ms 48804 KB Output is correct
8 Correct 2829 ms 48836 KB Output is correct
9 Correct 3436 ms 49644 KB Output is correct
10 Correct 546 ms 46444 KB Output is correct
11 Correct 2851 ms 48664 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 28140 KB Output is correct
2 Execution timed out 8116 ms 407712 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 28396 KB Output is correct
2 Correct 1801 ms 47868 KB Output is correct
3 Correct 2809 ms 48916 KB Output is correct
4 Correct 2692 ms 48580 KB Output is correct
5 Correct 3465 ms 49628 KB Output is correct
6 Correct 551 ms 46376 KB Output is correct
7 Correct 2888 ms 48804 KB Output is correct
8 Correct 2829 ms 48836 KB Output is correct
9 Correct 3436 ms 49644 KB Output is correct
10 Correct 546 ms 46444 KB Output is correct
11 Correct 2851 ms 48664 KB Output is correct
12 Correct 22 ms 28140 KB Output is correct
13 Execution timed out 8116 ms 407712 KB Time limit exceeded
14 Halted 0 ms 0 KB -