oj.uz

Submission #706191

# Submission time Handle Problem Language Result Execution time Memory
706191 2023-03-06T04:23:12 Z bLIC Factories (JOI14_factories) C++17
100 / 100
 4709 ms 209128 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 7 ms 708 KB Output is correct
2 Correct 263 ms 9328 KB Output is correct
3 Correct 300 ms 9544 KB Output is correct
4 Correct 279 ms 9520 KB Output is correct
5 Correct 313 ms 9688 KB Output is correct
6 Correct 177 ms 9036 KB Output is correct
7 Correct 314 ms 9548 KB Output is correct
8 Correct 276 ms 9696 KB Output is correct
9 Correct 372 ms 9772 KB Output is correct
10 Correct 175 ms 8976 KB Output is correct
11 Correct 292 ms 9528 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 568 KB Output is correct
2 Correct 2231 ms 133572 KB Output is correct
3 Correct 3450 ms 167900 KB Output is correct
4 Correct 891 ms 83384 KB Output is correct
5 Correct 4156 ms 208784 KB Output is correct
6 Correct 3670 ms 169036 KB Output is correct
7 Correct 1000 ms 36332 KB Output is correct
8 Correct 360 ms 26136 KB Output is correct
9 Correct 1149 ms 43156 KB Output is correct
10 Correct 1022 ms 37624 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 708 KB Output is correct
2 Correct 263 ms 9328 KB Output is correct
3 Correct 300 ms 9544 KB Output is correct
4 Correct 279 ms 9520 KB Output is correct
5 Correct 313 ms 9688 KB Output is correct
6 Correct 177 ms 9036 KB Output is correct
7 Correct 314 ms 9548 KB Output is correct
8 Correct 276 ms 9696 KB Output is correct
9 Correct 372 ms 9772 KB Output is correct
10 Correct 175 ms 8976 KB Output is correct
11 Correct 292 ms 9528 KB Output is correct
12 Correct 2 ms 568 KB Output is correct
13 Correct 2231 ms 133572 KB Output is correct
14 Correct 3450 ms 167900 KB Output is correct
15 Correct 891 ms 83384 KB Output is correct
16 Correct 4156 ms 208784 KB Output is correct
17 Correct 3670 ms 169036 KB Output is correct
18 Correct 1000 ms 36332 KB Output is correct
19 Correct 360 ms 26136 KB Output is correct
20 Correct 1149 ms 43156 KB Output is correct
21 Correct 1022 ms 37624 KB Output is correct
22 Correct 2754 ms 134488 KB Output is correct
23 Correct 2745 ms 137896 KB Output is correct
24 Correct 3988 ms 170400 KB Output is correct
25 Correct 3989 ms 173720 KB Output is correct
26 Correct 3895 ms 170712 KB Output is correct
27 Correct 4709 ms 209128 KB Output is correct
28 Correct 909 ms 87588 KB Output is correct
29 Correct 3825 ms 169920 KB Output is correct
30 Correct 3984 ms 170160 KB Output is correct
31 Correct 3825 ms 170052 KB Output is correct
32 Correct 1046 ms 43976 KB Output is correct
33 Correct 329 ms 26528 KB Output is correct
34 Correct 663 ms 32464 KB Output is correct
35 Correct 694 ms 32880 KB Output is correct
36 Correct 950 ms 35072 KB Output is correct
37 Correct 918 ms 35192 KB Output is correct