oj.uz

답안 #433318

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
433318 2021-06-19T14:29:33 Z codebuster_10 공장들 (JOI14_factories) C++17
100 / 100
 6069 ms 233380 KB 
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
 
#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 A> void rd(vt<A>& v);
template<class T> void rd(T& x){ cin >> x; }
template<class H, class... T> void rd(H& h, T&... t) { rd(h) ; rd(t...) ;}
template<class A> void rd(vt<A>& x) { for(auto& a : x) rd(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; }
 
template<typename T>
void __p(T a) {
  cout<<a; 
}
template<typename T, typename F>
void __p(pair<T, F> a) {
  cout<<"{";
  __p(a.first);
  cout<<",";
  __p(a.second);
  cout<<"}\n"; 
}
template<typename T>
void __p(std::vector<T> a) {
  cout<<"{";
  for(auto it=a.begin(); it<a.end(); it++)
    __p(*it),cout<<",}\n"[it+1==a.end()]; 
}
template<typename T, typename ...Arg>
void __p(T a1, Arg ...a) {
  __p(a1);
  __p(a...);
}
template<typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
  cout<<name<<" : ";
  __p(arg1);
  cout<<endl;
}
template<typename Arg1, typename ... Args>
void __f(const char *names, Arg1 &&arg1, Args &&... args) {
  int bracket=0,i=0;
  for(;; i++)
    if(names[i]==','&&bracket==0)
      break;
    else if(names[i]=='(')
      bracket++;
    else if(names[i]==')')
      bracket--;
  const char *comma=names+i;
  cout.write(names,comma-names)<<" : ";
  __p(arg1);
  cout<<" | ";
  __f(comma+1,args...);
}
 
void setIO(string s = "") {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
  cin.exceptions(cin.failbit); 
	cout.precision(15);	cout << fixed;
  if(SZ(s)){
  	freopen((s+".in").c_str(),"r",stdin);
  	freopen((s+".out").c_str(),"w",stdout);
  }
}
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 
 
 
 
 
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[]) {
	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) __f("i,p",i,cd.centroid_parent[i]);
	
	f(i,0,N) reverse(all(cd.dis[i]));
	
	// f(i,0,N){
		// __f("i,dis",i,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;
}
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 /*

 
 
 
#include <stdio.h>
#include <stdlib.h>
 
#define MAX_N          500000
#define MAX_Q          100000
#define MAX_SUM_ST    1000000
#define MAX_VALUE  1000000000
 
static int N, Q;
static int A[MAX_N], B[MAX_N], D[MAX_N];
static int S[MAX_N];
static int T[MAX_N];
static int X[MAX_SUM_ST];
static int Y[MAX_SUM_ST];
 
static int Qx[MAX_N];
static int Qy[MAX_N];
 
int main() {
 
  int i, j, k;
  int STop, TTop;
 
  if (2 != scanf("%d%d", &N, &Q)) {
    fprintf(stderr, "error: cannot read N and Q.\n");
    exit(1);
  }
  if (!(2 <= N && N <= MAX_N)) {
    fprintf(stderr, "error: N is out of bounds.\n");
    exit(1);
  }
  if (!(1 <= Q && Q <= MAX_Q)) {
    fprintf(stderr, "error: Q is out of bounds.\n");
    exit(1);
  }
  for (i = 0; i < N - 1; ++i) {
    if (1 != scanf("%d", &A[i])) {
      fprintf(stderr, "error: cannot read A[%d].\n", i);
      exit(1);
    }
    if (!(0 <= A[i] && A[i] <= N - 1)) {
      fprintf(stderr, "error: A[%d] is out of bounds.\n", i);
      exit(1);
    }
    if (1 != scanf("%d", &B[i])) {
      fprintf(stderr, "error: cannot read B[%d].\n", i);
      exit(1);
    }
    if (!(0 <= B[i] && B[i] <= N - 1)) {
      fprintf(stderr, "error: B[%d] is out of bounds.\n", i);
      exit(1);
    }
    if (A[i] == B[i]) {
      fprintf(stderr, "error: B[%d] is equal to A[%d].\n", i, i);
      exit(1);
    }
    if (1 != scanf("%d", &D[i])) {
      fprintf(stderr, "error: cannot read D[%d].\n", i);
      exit(1);
    }
    if (!(1 <= D[i] && D[i] <= MAX_VALUE)) {
      fprintf(stderr, "error: D[%d] is out of bounds.\n", i);
      exit(1);
    }
  }
 
  STop = 0;
  TTop = 0;
 
  for (j = 0; j < Q; ++j) {
    if (2 != scanf("%d%d", &S[j], &T[j])) {
      fprintf(stderr, "error: cannot read L[%d] and R[%d].\n", j, j);
      exit(1);
    }
 
    if(STop + S[j] > MAX_SUM_ST) {
      fprintf(stderr, "error: S[0] + S[1] + ... + S[%d] is out of bounds.\n", j);
      exit(1);
    }
 
    if(TTop + T[j] > MAX_SUM_ST) {
      fprintf(stderr, "error: T[0] + T[1] + ... + T[%d] is out of bounds.\n", j);
      exit(1);
    }
 
    for (k = 0; k < S[j]; ++k, ++STop) {
      if (1 != scanf("%d", &X[STop])) {
        fprintf(stderr, "error: cannot read X[%d][%d].\n", j, k);
        exit(1);
      }
 
      if (!(0 <= X[STop] && X[STop] <= N - 1)) {
        fprintf(stderr, "error: cannot read X[%d][%d].\n", j, k);
        exit(1);
      }
    }
 
    for (k = 0; k < T[j]; ++k, ++TTop) {
      if (1 != scanf("%d", &Y[TTop])) {
        fprintf(stderr, "error: cannot read Y[%d][%d].\n", j, k);
        exit(1);
      }
 
      if (!(0 <= Y[TTop] && Y[TTop] <= N - 1)) {
        fprintf(stderr, "error: cannot read Y[%d][%d].\n", j, k);
        exit(1);
      }
    }
  }
 
  STop = 0;
  TTop = 0;
  Init(N, A, B, D);
 
  for (j = 0; j < Q; ++j) {
    for (k = 0; k < S[j]; k++) {
        Qx[k] = X[STop++];
    }
    for (k = 0; k < T[j]; k++) {
        Qy[k] = Y[TTop++];
    }
 
    printf("%lld\n", Query(S[j], Qx, T[j], Qy));
  }
 
 
  return 0;
}
 
 
 
 */

Compilation message

factories.cpp: In function 'void setIO(std::string)':
factories.cpp:84:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |    freopen((s+".in").c_str(),"r",stdin);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
factories.cpp:85:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |    freopen((s+".out").c_str(),"w",stdout);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 588 KB Output is correct
2 Correct 351 ms 9232 KB Output is correct
3 Correct 388 ms 9580 KB Output is correct
4 Correct 386 ms 9640 KB Output is correct
5 Correct 408 ms 9712 KB Output is correct
6 Correct 262 ms 9040 KB Output is correct
7 Correct 392 ms 9484 KB Output is correct
8 Correct 390 ms 9536 KB Output is correct
9 Correct 408 ms 9688 KB Output is correct
10 Correct 257 ms 8996 KB Output is correct
11 Correct 382 ms 9540 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 3150 ms 133616 KB Output is correct
3 Correct 4786 ms 167900 KB Output is correct
4 Correct 1188 ms 101856 KB Output is correct
5 Correct 6069 ms 227472 KB Output is correct
6 Correct 4981 ms 187624 KB Output is correct
7 Correct 1350 ms 49796 KB Output is correct
8 Correct 488 ms 39860 KB Output is correct
9 Correct 1473 ms 56952 KB Output is correct
10 Correct 1348 ms 51604 KB Output is correct

Subtask #3
67.0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 588 KB Output is correct
2 Correct 351 ms 9232 KB Output is correct
3 Correct 388 ms 9580 KB Output is correct
4 Correct 386 ms 9640 KB Output is correct
5 Correct 408 ms 9712 KB Output is correct
6 Correct 262 ms 9040 KB Output is correct
7 Correct 392 ms 9484 KB Output is correct
8 Correct 390 ms 9536 KB Output is correct
9 Correct 408 ms 9688 KB Output is correct
10 Correct 257 ms 8996 KB Output is correct
11 Correct 382 ms 9540 KB Output is correct
12 Correct 2 ms 460 KB Output is correct
13 Correct 3150 ms 133616 KB Output is correct
14 Correct 4786 ms 167900 KB Output is correct
15 Correct 1188 ms 101856 KB Output is correct
16 Correct 6069 ms 227472 KB Output is correct
17 Correct 4981 ms 187624 KB Output is correct
18 Correct 1350 ms 49796 KB Output is correct
19 Correct 488 ms 39860 KB Output is correct
20 Correct 1473 ms 56952 KB Output is correct
21 Correct 1348 ms 51604 KB Output is correct
22 Correct 3317 ms 158568 KB Output is correct
23 Correct 3365 ms 162224 KB Output is correct
24 Correct 5100 ms 194108 KB Output is correct
25 Correct 5151 ms 197956 KB Output is correct
26 Correct 5024 ms 194468 KB Output is correct
27 Correct 6012 ms 233380 KB Output is correct
28 Correct 1242 ms 112072 KB Output is correct
29 Correct 4995 ms 194096 KB Output is correct
30 Correct 4941 ms 193896 KB Output is correct
31 Correct 4939 ms 194156 KB Output is correct
32 Correct 1374 ms 57616 KB Output is correct
33 Correct 499 ms 40168 KB Output is correct
34 Correct 969 ms 45540 KB Output is correct
35 Correct 964 ms 45920 KB Output is correct
36 Correct 1285 ms 48356 KB Output is correct
37 Correct 1293 ms 48408 KB Output is correct