oj.uz

Submission #1108930

# Submission time Handle Problem Language Result Execution time Memory
1108930 2024-11-05T17:10:04 Z doducanh Factories (JOI14_factories) C++14
100 / 100
 3065 ms 240124 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 16976 KB Output is correct
2 Correct 222 ms 31428 KB Output is correct
3 Correct 240 ms 31680 KB Output is correct
4 Correct 239 ms 31540 KB Output is correct
5 Correct 244 ms 31816 KB Output is correct
6 Correct 140 ms 31164 KB Output is correct
7 Correct 222 ms 31672 KB Output is correct
8 Correct 232 ms 31676 KB Output is correct
9 Correct 285 ms 31816 KB Output is correct
10 Correct 146 ms 31048 KB Output is correct
11 Correct 225 ms 31560 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16976 KB Output is correct
2 Correct 1616 ms 162872 KB Output is correct
3 Correct 2420 ms 197692 KB Output is correct
4 Correct 467 ms 112540 KB Output is correct
5 Correct 2568 ms 238060 KB Output is correct
6 Correct 2133 ms 198348 KB Output is correct
7 Correct 568 ms 60848 KB Output is correct
8 Correct 221 ms 50108 KB Output is correct
9 Correct 700 ms 67020 KB Output is correct
10 Correct 557 ms 61488 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16976 KB Output is correct
2 Correct 222 ms 31428 KB Output is correct
3 Correct 240 ms 31680 KB Output is correct
4 Correct 239 ms 31540 KB Output is correct
5 Correct 244 ms 31816 KB Output is correct
6 Correct 140 ms 31164 KB Output is correct
7 Correct 222 ms 31672 KB Output is correct
8 Correct 232 ms 31676 KB Output is correct
9 Correct 285 ms 31816 KB Output is correct
10 Correct 146 ms 31048 KB Output is correct
11 Correct 225 ms 31560 KB Output is correct
12 Correct 4 ms 16976 KB Output is correct
13 Correct 1616 ms 162872 KB Output is correct
14 Correct 2420 ms 197692 KB Output is correct
15 Correct 467 ms 112540 KB Output is correct
16 Correct 2568 ms 238060 KB Output is correct
17 Correct 2133 ms 198348 KB Output is correct
18 Correct 568 ms 60848 KB Output is correct
19 Correct 221 ms 50108 KB Output is correct
20 Correct 700 ms 67020 KB Output is correct
21 Correct 557 ms 61488 KB Output is correct
22 Correct 1719 ms 166652 KB Output is correct
23 Correct 1967 ms 168916 KB Output is correct
24 Correct 2620 ms 202172 KB Output is correct
25 Correct 2640 ms 204668 KB Output is correct
26 Correct 2693 ms 202940 KB Output is correct
27 Correct 2954 ms 240124 KB Output is correct
28 Correct 598 ms 118960 KB Output is correct
29 Correct 2774 ms 202532 KB Output is correct
30 Correct 2796 ms 202416 KB Output is correct
31 Correct 3065 ms 202764 KB Output is correct
32 Correct 819 ms 67564 KB Output is correct
33 Correct 236 ms 50108 KB Output is correct
34 Correct 442 ms 57124 KB Output is correct
35 Correct 441 ms 57456 KB Output is correct
36 Correct 583 ms 59956 KB Output is correct
37 Correct 607 ms 59840 KB Output is correct