oj.uz

답안 #387241

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
387241 2021-04-08T07:13:21 Z galen_colin 공장들 (JOI14_factories) C++14
15 / 100
 8000 ms 333100 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;

struct lca_lift {
  const int lg = 21;
  int n;
  vector<int> depth;
  vector<vector<int> > edges;
  int lift[500000][22];
  
  void init(int sz) {
    n = sz;
    depth = vector<int>(n);
    edges = vector<vector<int> >(n, vector<int>());
  }

  void edge(int a, int b) {
    edges[a].push_back(b);
    edges[b].push_back(a);
  }

  void attach(int node_to_attach, int node_to_attach_to) {
    int a = node_to_attach, b = node_to_attach_to;
    edge(a, b);

    lift[a][0] = b;

    for (int i = 1; i < lg; i++) {
      if (lift[a][i - 1] == -1) lift[a][i] = -1;
      else lift[a][i] = lift[lift[a][i - 1]][i - 1];
    }

    depth[a] = depth[b] + 1;
  }

  void init_lift(int v = 0) {
    depth[v] = 0;
    dfs(v, -1);
  }

  void dfs(int v, int par) {
    lift[v][0] = par;

    for (int i = 1; i < lg; i++) {
      if (lift[v][i - 1] == -1) lift[v][i] = -1;
      else lift[v][i] = lift[lift[v][i - 1]][i - 1];
    }

    for (int x: edges[v]) {
      if (x != par) {
        depth[x] = depth[v] + 1;
        dfs(x, v);
      }
    }
  }

  int get(int v, int k) {
    for (int i = lg - 1; i >= 0; i--) {
	  if (v == -1) return v;
      if ((1 << i) <= k) {
        v = lift[v][i];
        k -= (1 << i);
      }
    }
    return v;
  }

  int get_lca(int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);
    int d = depth[a] - depth[b];
    int v = get(a, d);
    if (v == b) {
      return v;
    } else {
      for (int i = lg - 1; i >= 0; i--) {
        if (lift[v][i] != lift[b][i]) {
          v = lift[v][i];
          b = lift[b][i];
        }
      }
      return lift[b][0];
    }
  }
};

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;	

ll best[500005];
lca_lift lca;
ll dep[500005];

ll dist(int a, int b) {
    int v = lca.get_lca(a, b);
    return dep[a] + dep[b] - 2 * dep[v];
}

struct centroid {
  vector<vector<int> > edges;
  vector<bool> vis;
  vector<int> par;
  vector<int> sz;
  int n;

  void init(int s) {
    n = s;
    edges = vector<vector<int> >(n, vector<int>());
    vis = vector<bool>(n, 0);
    par = vector<int>(n);
    sz = vector<int>(n);
  }

  void edge(int a, int b) {
    edges[a].push_back(b);
    edges[b].push_back(a);
  }

  int find_size(int v, int p = -1) {
    if (vis[v]) return 0;
    sz[v] = 1;

    for (int x: edges[v]) {
      if (x != p) {
        sz[v] += find_size(x, v);
      }
    }

    return sz[v];
  }

  int find_centroid(int v, int p, int n) {
    for (int x: edges[v]) {
      if (x != p) {
        if (!vis[x] && sz[x] > n / 2) {
          return find_centroid(x, v, n);
        }
      }
    }

    return v;
  }

  void init_centroid(int v = 0, int p = -1) {
    find_size(v);

    int c = find_centroid(v, -1, sz[v]);
    vis[c] = true;
    par[c] = p;

    for (int x: edges[c]) {
      if (!vis[x]) {
        init_centroid(x, c);
      }
    }
  }
};

centroid cd;
vector<pair<ll, ll>> edges[500005];

void dfs(ll v, ll p, ll d) {
	dep[v] = d;
	
	for (pair<ll, ll> x: edges[v]) {
		if (x.f != p) {
			dfs(x.f, v, d + x.s);
		}
	}
}

vector<ll> dists[500005];

void gen(ll v) {
	ll c = v;
	do {
		dists[v].push_back(dist(c, v));
		c = cd.par[c];
	} while (c != -1);
}

void Init(int n, int aa[], int bb[], int dd[]) {
	memset(best, 1, sizeof(best));
	lca.init(n);
	cd.init(n);
	
	for (ll i = 0; i < n - 1; i++) {
		cd.edge(aa[i], bb[i]);
		edges[aa[i]].push_back({bb[i], dd[i]});
		edges[bb[i]].push_back({aa[i], dd[i]});
		lca.edge(aa[i], bb[i]);
	}
	
	cd.init_centroid();
	lca.init_lift();
	dfs(0, -1, 0);
	
	for (ll i = 0; i < n; i++) gen(i);
}

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, pt = 0;
	do {
		best[c] = min(best[c], dists[v][pt++]);
		c = cd.par[c];
	} while (c != -1);
}

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

ll Query(int s, int x[], int t, int y[]) {
	if (n > 5000) exit(0);
	// 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;
		// n = 5000, q = 0;
		
		for (ll i = 0; i < n - 1; i++) {
			cin >> a[i] >> b[i] >> c[i];
			// a[i] = rng() % (i + 1), b[i] = i + 1, c[i] = 1e9;
		}
		
		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

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 28140 KB Output is correct
2 Correct 384 ms 37612 KB Output is correct
3 Correct 434 ms 37868 KB Output is correct
4 Correct 420 ms 37996 KB Output is correct
5 Correct 473 ms 38380 KB Output is correct
6 Correct 275 ms 37524 KB Output is correct
7 Correct 429 ms 37740 KB Output is correct
8 Correct 435 ms 38024 KB Output is correct
9 Correct 455 ms 38252 KB Output is correct
10 Correct 274 ms 37392 KB Output is correct
11 Correct 426 ms 37868 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 28012 KB Output is correct
2 Correct 3822 ms 241204 KB Output is correct
3 Correct 6756 ms 275612 KB Output is correct
4 Correct 1554 ms 192372 KB Output is correct
5 Execution timed out 8063 ms 333100 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 28140 KB Output is correct
2 Correct 384 ms 37612 KB Output is correct
3 Correct 434 ms 37868 KB Output is correct
4 Correct 420 ms 37996 KB Output is correct
5 Correct 473 ms 38380 KB Output is correct
6 Correct 275 ms 37524 KB Output is correct
7 Correct 429 ms 37740 KB Output is correct
8 Correct 435 ms 38024 KB Output is correct
9 Correct 455 ms 38252 KB Output is correct
10 Correct 274 ms 37392 KB Output is correct
11 Correct 426 ms 37868 KB Output is correct
12 Correct 21 ms 28012 KB Output is correct
13 Correct 3822 ms 241204 KB Output is correct
14 Correct 6756 ms 275612 KB Output is correct
15 Correct 1554 ms 192372 KB Output is correct
16 Execution timed out 8063 ms 333100 KB Time limit exceeded
17 Halted 0 ms 0 KB -