Submission #1134892

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134892		Wendidiask	Factories (JOI14_factories)	C++20	100 / 100	5844 ms	127328 KiB

factories

/*
                                     :---:--:--::::::--:-:----:                                     
                               ::-:::.                         ::-:::                               
                       .*  -===..                                    :---                           
                     .-+*##=-------====-:                                :--:                       
                  :+##=.* -=            :=+-                                .-=:                    
               .+++-.  :-   -=.            .=+-                                .--.                 
             .++=-     +      -=              :*-                                 :-.               
            +*+-      :-        -=.             -*:                                 :=:             
           #*:        *           -=.             +-                                  .=            
        =:%+         -:             -=.            +-                                   --          
        -%:          *                -=.           *:                                    +.        
       :%-..        =.                  -=.          #                                     -:       
      :=#   ..      +                     -=.        ==                                     -=      
     ---+     .    =                        -=.      .#                                      .+     
    -: ==       .  =         :------::------:.-=.     %                                       .=    
   :-  ==        .=.     ---:.               :--#+.  .%                                        :-   
   =   .*        .+.. :=-                        :++ -+                                         =:  
  +     #.       +  -=:                            :*%-*:                                        *  
 :=     :#      :=:=   .                    :-----: =+-+                                         .+ 
 *       -*     *=-     . .-        :::::::.       :*  .#+.                                       + 
:-        -+   :#.        --::-----:              :*     ++=                                      .-
+          :*. *.    .:::::*%:                   ++       +.-=.                                    +
+           -#**----:       .=                 -*.         +  -=                                   =
*           +.#=+:           +  .           .=+:           =.   -=.                                =
=            -+  :++:         +   ..     .=+=              .=     -=.                              -
=            %-     :====-:.  =.  .:--===-                  *       -=.                            -
+           +--          .:--==#==-:.=                      +         -=.                          =
*           + *                =.    :                     .=           -=.                        =
+          =  *                 +                          =              -=.                      +
:-         =  .=                =:                         =                -=.                   .-
 *        +    =:                *                        *                   -=.                 + 
 :-      .+     =-               :-                     .+                      -=.              .+ 
  *      *       :=               *                    :=                         -=             *  
   =    :-         =:             .-                 .=:                            -=.         =:  
   -:   *           .=-            +               .=-                                -=       :-   
    =: -:              --:         :-           :--:                                    -=.   .=    
     =:+                  ----.     *       :---.                                         -= .+     
    --=*----------------------=*+=--=+--=+*+------------------------------------------------%+:.    
    :: :=                           +:-                                                    -- :.    
        .=.                                                                               =.        
          -=                                                                            -=          
           .=:                                                                        .=.           
             .=:                                                                    .+:             
               :--                                                                :-:               
                  --                                                            -=.                 
                    :--.                                                     --:                    
                       :--:                                              .--:                       
                          .-:-:                                      ::--.                          
                               :----.                          .:----                               
                                    .:::::::::-::::::--::::::::.                             
 */
 // Hello this is Tyx2019's clone
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define debug(x) cerr << #x << " is " << x << "\n"
#define hehe ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define repb(i, a, b) for (int i = b; i >= a; i--)
#define pii pair<int, int>
#define linebreak cout << "---------------------------------------------------------\n"
#define f first
#define s second
#define pb push_back
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// good luck
const ll MS = 5e5+5, mod = 1e9+9, INF = 3e18, blk = 400;
int parent[MS], depth[MS], s[MS], twok[MS][20];
ll dis[MS], m[MS]; 
vector<pii> adj[MS];
int dfs1(int x, int par, int dep) { 
	// returns size of subtree of x
	s[x] = 1;
	for (auto v : adj[x]) {
		if (v.f == par) continue;
		if (depth[v.f] != -1) continue;
		s[x] += dfs1(v.f, x, dep);
	}
	return s[x];
} 
int dfs2(int x, int par, int m) {
	// return centroid of the subtree
	for (auto v : adj[x]) {
		if (v.f == par) continue;
		if (depth[v.f] != -1) continue;
		if (s[v.f] > m/2) return dfs2(v.f, x, m);
	}
	return x;
}
void build(int x, int par, int dep) {
	int m = dfs1(x, par, dep);
	int centroid = dfs2(x, par, m);
	if (par == -1) par = centroid;
	parent[centroid] = par;
	depth[centroid] = dep;
	for (auto v : adj[centroid]) {
		if (depth[v.f] != -1) continue;
		build(v.f, centroid, dep+1);
	}
}
void init(int x, int par) {
	for (int k = 0; k < 20; k++) {
		if (twok[x][k] == -1) break;
		twok[x][k+1] = twok[twok[x][k]][k];
	}
	for (auto v : adj[x]) {
		if (v.f == par) continue;
		twok[v.f][0] = x;
		depth[v.f] = depth[x]+1;
		dis[v.f] = dis[x]+v.s;
		init(v.f, x);
	}
}
int kpar(int x, int k) {
	for (int j = 0; j < 20; j++) {
		if (x == -1) break;
		if (k&(1<<j)) x = twok[x][j];
	} 
	return x;
} 
int lca(int a, int b) {
	if (depth[a] < depth[b]) swap(a, b);
	a = kpar(a, depth[a]-depth[b]);
	if (a == b) return a;
	for (int k = 19; k >= 0; k--) {
		if (twok[a][k] != twok[b][k]) {
			a = twok[a][k]; b = twok[b][k];
		}
	} 
	return twok[a][0];
}
void Init(int n, int a[], int b[], int d[]) {
	memset(depth, -1, sizeof(depth));
	for (int i = 0; i < n-1; i++) {
		adj[a[i]].pb({b[i], d[i]});
		adj[b[i]].pb({a[i], d[i]});	
	}
	build(0, -1, 0);
	for (int i = 0; i < n; i++) if (depth[i] == 0) parent[i] = -1;
	depth[0] = 0; dis[0] = 0; memset(twok, -1, sizeof(twok));
	init(0, -1);
	for (int i = 0; i < n; i++) m[i] = INF;
}

void update(int x) {
	int u = x;
	while (u != -1) {
		m[u] = min(m[u], dis[u]+dis[x]-2*dis[lca(u,x)]);
		u = parent[u];
	}
}
void undo(int x) {
	int u = x;
	while (u != -1) {
		m[u] = INF;
		u = parent[u];
	}
}
ll ask(int x) {
	int u = x; ll res = INF;
	while (u != -1) {
		res = min(res, m[u]+dis[u]+dis[x]-2*dis[lca(u,x)]);
		u = parent[u];
	}
	return res;
}
ll Query(int s, int x[], int t, int y[]) {
	ll ans = INF;
	if (2*s+t < 2*t+s) {
		for (int i = 0; i < s; i++) update(x[i]);
		for (int i = 0; i < t; i++) ans = min(ans, ask(y[i]));	
		for (int i = 0; i < s; i++) undo(x[i]);
	}
	else {
		for (int i = 0; i < t; i++) update(y[i]);
		for (int i = 0; i < s; i++) ans = min(ans, ask(x[i]));	
		for (int i = 0; i < t; i++) undo(y[i]);
	}
	return ans;
}

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67