oj.uz

Submission #433320

# Submission time Handle Problem Language Result Execution time Memory
433320 2021-06-19T14:34:04 Z codebuster_10 Factories (JOI14_factories) C++17
100 / 100
 7069 ms 208760 KB 
#include <bits/stdc++.h>
using namespace std;

#define endl "\n"
#define f(i,a,b) for(int i=int(a);i<int(b);++i)
 
#define pr pair
#define ar array
#define fr first
#define sc second
#define vt vector
#define pb push_back
#define eb emplace_back
#define LB lower_bound  
#define UB upper_bound
#define PQ priority_queue
 
#define SZ(x) ((int)(x).size())
#define all(a) (a).begin(),(a).end()
#define allr(a) (a).rbegin(),(a).rend()
#define mem(a,b) memset(a, b, sizeof(a))
 

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
const long long INF = 1e16;
 
struct edge {
  int node, weight;
  edge(int _node, int _weight) : node(_node), weight(_weight)  {}
};
 
struct centroid_decomposition {
  int N;
  vector<vector<edge>> adj;
  vector<int> depth;
  vector<int> subtree_size;
  // parent of a node in centroid tree.
  vector<int> centroid_parent;
  vector<int> node_list;
  // gives the distance of each node to its descendants in centroid tree.
  vector<vector<long long>> dis; // from node to its ancestors.
 	bool found_centroid;
	
  void init(int _N) {
    N = _N;
    adj.assign(N, {});
    depth.resize(N);
    subtree_size.resize(N);
    centroid_parent.assign(N, -1);
    dis.resize(N,{});
  }
	
	
  void add_edge(int u, int v, int w) {
    assert(u != v);
    adj[u].emplace_back(edge(v,w));
    adj[v].emplace_back(edge(u,w));
  }
  
  // Erasing edges is O(number of nodes remaining) which is fine within our decomposition.
	void erase_edge(int from, int to) {
		for(edge &e : adj[from]) {
      if(e.node == to) {
        swap(e, adj[from].back());
        adj[from].pop_back();
        return;
      }
    }
    assert(false);
  }
 
  int dfs(int node, long long weight = 0, int parent = -1, int root = -1) {
  	if(parent < 0) {
    	root = node;
      node_list.clear();
    }
 
  	if(found_centroid){
  		dis[node].pb(weight);
  	}
  	
    subtree_size[node] = 1;
    node_list.push_back(node);
 
    for(edge &e : adj[node]) {
    	if(e.node != parent) {
      	subtree_size[node] += dfs(e.node, e.weight + weight, node, parent < 0 ? node : root);
      }
    }
 
    return subtree_size[node];
  }
 
  int centroid(int root) {
  	int n = dfs(root);
    bool found;
 
    // Repeatedly move to the subtree that is at least half of the tree, if such a subtree exists.
    do {
      found = false;
 
      for(edge &e : adj[root]){
        if(subtree_size[e.node] < subtree_size[root] && 2 * subtree_size[e.node] >= n) {
          root = e.node;
          found = true;
          break;
      	}
      }
    } while(found);
 
    return root;
  }
 
	// centroid parent of root of centroid tree is -1
  void solve(int root) {
  	found_centroid = false;
  	root = centroid(root);
  	found_centroid = true;
    dfs(root);
 
    for(int node : node_list){
      if(node != root){
         centroid_parent[node] = root;
			}
    }
 
  	for(edge &e : adj[root]){
    	erase_edge(e.node, root);
    }
 
  	// Recurse after solving root, so that edge erasures don't cause incorrect results.
    for(edge &e : adj[root]){
      solve(e.node);
    }
  }
}cd;
 
 
vt<long long> ans;
 
 
void turn_on(int _i){
	for(int i = _i, cnt = 0; ~i; i = cd.centroid_parent[i], ++cnt){
		ckmin(ans[i],cd.dis[_i][cnt]);
	}
}
 
void turn_off(int _i){
	for(int i = _i; ~i; i = cd.centroid_parent[i]){
		ans[i] = INF;
	}
}
 
 
 
 
 
 
 
 
 
 
void Init(int N, int A[], int B[], int D[]) {
	
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	cd.init(N);
	ans.assign(N,INF);
	f(e,0,N-1){
		cd.add_edge(A[e],B[e],D[e]);
	}
	cd.solve(0);
	
	f(i,0,N) reverse(all(cd.dis[i]));

	return;
}
 
 
long long Query(int S, int X[], int T, int Y[]) {
	
	
	f(i,0,S) turn_on(X[i]);
	
	
	long long res = INF;
	f(i,0,T){
		for(int j = Y[i], cnt = 0; ~j; j = cd.centroid_parent[j], ++cnt){
			ckmin(res, cd.dis[Y[i]][cnt] + ans[j]);
		}
	}
	
	
	
	f(i,0,S) turn_off(X[i]);
	
  return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 588 KB Output is correct
2 Correct 329 ms 9320 KB Output is correct
3 Correct 364 ms 9764 KB Output is correct
4 Correct 388 ms 9732 KB Output is correct
5 Correct 386 ms 9808 KB Output is correct
6 Correct 244 ms 9028 KB Output is correct
7 Correct 369 ms 9524 KB Output is correct
8 Correct 429 ms 9532 KB Output is correct
9 Correct 381 ms 9796 KB Output is correct
10 Correct 235 ms 9044 KB Output is correct
11 Correct 387 ms 9476 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 2963 ms 133544 KB Output is correct
3 Correct 4464 ms 167924 KB Output is correct
4 Correct 1041 ms 83420 KB Output is correct
5 Correct 5627 ms 208708 KB Output is correct
6 Correct 4548 ms 169024 KB Output is correct
7 Correct 1316 ms 36324 KB Output is correct
8 Correct 444 ms 26148 KB Output is correct
9 Correct 1489 ms 43108 KB Output is correct
10 Correct 1204 ms 37552 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 588 KB Output is correct
2 Correct 329 ms 9320 KB Output is correct
3 Correct 364 ms 9764 KB Output is correct
4 Correct 388 ms 9732 KB Output is correct
5 Correct 386 ms 9808 KB Output is correct
6 Correct 244 ms 9028 KB Output is correct
7 Correct 369 ms 9524 KB Output is correct
8 Correct 429 ms 9532 KB Output is correct
9 Correct 381 ms 9796 KB Output is correct
10 Correct 235 ms 9044 KB Output is correct
11 Correct 387 ms 9476 KB Output is correct
12 Correct 2 ms 460 KB Output is correct
13 Correct 2963 ms 133544 KB Output is correct
14 Correct 4464 ms 167924 KB Output is correct
15 Correct 1041 ms 83420 KB Output is correct
16 Correct 5627 ms 208708 KB Output is correct
17 Correct 4548 ms 169024 KB Output is correct
18 Correct 1316 ms 36324 KB Output is correct
19 Correct 444 ms 26148 KB Output is correct
20 Correct 1489 ms 43108 KB Output is correct
21 Correct 1204 ms 37552 KB Output is correct
22 Correct 3550 ms 134228 KB Output is correct
23 Correct 4005 ms 137612 KB Output is correct
24 Correct 5969 ms 169904 KB Output is correct
25 Correct 5844 ms 173372 KB Output is correct
26 Correct 5871 ms 170280 KB Output is correct
27 Correct 7069 ms 208760 KB Output is correct
28 Correct 1327 ms 87572 KB Output is correct
29 Correct 5653 ms 169896 KB Output is correct
30 Correct 5641 ms 169812 KB Output is correct
31 Correct 5600 ms 169952 KB Output is correct
32 Correct 1588 ms 44532 KB Output is correct
33 Correct 472 ms 27132 KB Output is correct
34 Correct 1006 ms 33008 KB Output is correct
35 Correct 1018 ms 33400 KB Output is correct
36 Correct 1341 ms 35516 KB Output is correct
37 Correct 1408 ms 35564 KB Output is correct