제출 #433294

#제출 시각아이디문제언어결과실행 시간메모리
433294codebuster_10공장들 (JOI14_factories)C++17
15 / 100
8060 ms339564 KiB
#include <bits/stdc++.h> using namespace std; #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; #define int int64_t //be careful about this #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); } } struct LCA { int N, timer, LOG; vector< vector<int> > up, dis; vector< vector<array<int,2> > > adj; vector<int> tin, tout, depth; void init(int _N) { N = _N ; LOG = log2(N) + 5; adj.resize(N); up.resize(N, vector<int> (LOG)); dis.resize(N, vector<int> (LOG)); tin = tout = depth = vector<int> (N); } void ae(int x, int y,int w = 1) { // add edge adj[x].push_back({y,w}), adj[y].push_back({x,w}); } void dfs(int v, int p, int w){ tin[v] = ++timer; up[v][0] = p; dis[v][0] = w; for(int i = 1; i < LOG; i++){ up[v][i] = up[up[v][i-1]][i-1]; dis[v][i] = dis[v][i-1] + dis[up[v][i-1]][i-1]; } for(auto [u,w] : adj[v]) if(u != p){ depth[u] = depth[v] + 1; dfs(u,v,w); } tout[v] = ++timer; } void gen(int R = 0) { depth[R] = timer = 0; dfs(R,R,0); } bool is_ancestor(int u, int v){ return tin[u] <= tin[v] && tout[u] >= tout[v]; } int lca(int u, int v){ if(is_ancestor(u,v)) return u; if(is_ancestor(v,u)) return v; for(int i = LOG - 1; i >= 0; --i) { if(!is_ancestor(up[u][i],v)){ u = up[u][i] ; } } return up[u][0]; } int weighted_dist(int u,int v){ int temp = lca(u,v); int x1 = kth_ancestor_weighted_dist(u,depth[u] - depth[temp]); int x2 = kth_ancestor_weighted_dist(v,depth[v] - depth[temp]); return x1 + x2 ; } int kth_ancestor_weighted_dist(int i,int k){ if(depth[i] < k) return int(-1); int ans = 0; for(int j = LOG - 1; j >= 0; --j){ if( (int(1) << j) <= k ){ k -= (int(1) << j); ans += dis[i][j]; i = up[i][j]; } } return ans ; } }lca; mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); const long double PI = acos((long double)-1); struct custom_hash { /// use most bits rather than just the lowest ones const uint64_t C = (long long)(2e18 * PI) + 71; // large odd number const int RANDOM = rng(); long long operator()(long long x) const { /// https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html return __builtin_bswap64((x^RANDOM)*C); } }; template<class K,class V> using hash_table = gp_hash_table<K,V,custom_hash>; const int INF = 1e16; struct edge { int node, weight; edge(int _node, int _weight) : node(_node), weight(_weight) {} }; struct centroid_decomposition { #undef int int N; vector<vector<edge>> adj; vector<int> subtree_size; // parent of a node in centroid tree. vector<int> centroid_parent; vector<int> node_list; #define int int64_t void init(int _N) { N = _N; adj.assign(N, {}); subtree_size.resize(N); centroid_parent.assign(N, -1); } 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, int weight = -1, int parent = -1, int root = -1) { if(parent < 0) { root = node; node_list.clear(); } 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, 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) { root = centroid(root); 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); } } void clear(){ adj.clear(); subtree_size.clear(); } }cd; vt<int> ans; void turn_on(int _i){ for(int i = _i; i >= 0; i = cd.centroid_parent[i]){ ckmin(ans[i],lca.weighted_dist(i,_i)); } } void turn_off(int _i){ for(int i = _i; i >= 0; i = cd.centroid_parent[i]){ ans[i] = INF; } } #undef int void Init(int N, int A[], int B[], int D[]) { #define int int64_t lca.init(N); f(e,0,N-1){ lca.ae(A[e],B[e],D[e]); } lca.gen(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); cd.clear(); return; } #undef int long long Query(int S, int X[], int T, int Y[]) { #define int int64_t f(i,0,S) turn_on(X[i]); int res = INF; f(i,0,T){ for(int j = Y[i]; j >= 0; j = cd.centroid_parent[j]){ ckmin(res, lca.weighted_dist(j,Y[i]) + ans[j]); } } f(i,0,S) turn_off(X[i]); return res; } #undef int

컴파일 시 표준 에러 (stderr) 메시지

factories.cpp: In function 'void setIO(std::string)':
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+".in").c_str(),"r",stdin);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
factories.cpp:86:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |    freopen((s+".out").c_str(),"w",stdout);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...