Submission #438980

#	Time	Username	Problem	Language	Result	Execution time	Memory
438980		HunterXD	Factories (JOI14_factories)	C++17	15 / 100	1992 ms	524288 KiB

factories

#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<ll,ll> pll;
typedef double long dl;
typedef vector<ll> row;
typedef vector< pair<ll,ll> > rowp;
typedef vector<row> grid;


#define F first 
#define S second 
#define PB push_back 
#define MP make_pair
#define rep(i,a,b) for (ll i = a; i < b; i++)
#define pmod 1000000007
#define INF 100000000000000000
#define pi atan(1)*4
#define modi 1000000
#define nmod 998244353
#define salto '\n'

struct Tree{

	private:
		vector<rowp> tree;
		vector<row> centroids;
		ll n, root, rootc, ntemp;
		vector<ll> siz;
		bitset<200010> seen;
		vector<rowp> sparse;
		row rank;

        ll ans = INF;
        vector<ll> eliminar;
        vector<ll> fatherc;
        vector<ll> ramas[2];

		ll actual;
		rowp temp;
		map<ll,ll> mini;

	public:

		//basic

		void create(ll m){

			n = m+1;
			tree.assign(n, rowp());
			centroids.assign(n, row());
			siz.assign(n, 0);
			sparse.assign(n, rowp(20, pll( {0,0} ) ));
			rank.assign(n, 0);
            fatherc.assign(n, 0);

            ramas[0].assign(n, INF);
            ramas[1].assign(n, INF);

            for(ll i = 0; i < n; i++){
                ramas[0][i] = INF;
                ramas[1][i] = INF;
            }
		} 

		void add(ll u, ll v, ll w){
			tree[u].PB({v, w});
			tree[v].PB({u, w});
		}

		void addc(ll u, ll v){
			centroids[u].PB(v);
			centroids[v].PB(u);
		}


		//centroide

		ll calc_size(ll u,ll p){
			siz[u] = 1;
			for(auto v : tree[u]){
				if(v.F != p && !seen[v.F]) {
					siz[u] += calc_size(v.F,u);
				}
			}
			return siz[u];
		}

		ll disc_centroid(ll u,ll p){

            for(auto v : tree[u]){
				if(v.F == p || seen[v.F]) continue;
				if(siz[v.F] > ntemp/2) return disc_centroid(v.F,u);
			}

			return u;
		}

		ll find_centroid(ll root, ll p){
			
			ntemp = calc_size(root,p);
			
			ll c = disc_centroid(root,p);
			seen[c] = 1;
			
			for(auto v : tree[c]){
				if(seen[v.F]) continue;
                ll temporal = find_centroid(v.F,c);
				addc(c, temporal);
                fatherc[temporal] = c;            
			}

			return c;

		}

		//lca

		void dfs(ll u, ll p, ll rango){
			sparse[u][0].F = p;
			rank[u] = rango;
			for(auto v : tree[u]){
				if(v.F == p) continue;
				sparse[v.F][0].S = v.S;
				dfs(v.F, u, rango+1);
			}
		}

		void sparse_fill(){
			for(ll i = 1; i < 20; i++){
				for(ll j = 0; j < n; j++){
					sparse[j][i].F = sparse[sparse[j][i-1].F][i-1].F;
					sparse[j][i].S = sparse[j][i-1].S + sparse[sparse[j][i-1].F][i-1].S;
				}
			}
		}

		pll lca_calc(ll a, ll b){

			if(rank[a] > rank[b]) swap(a,b);

			pll ret = {0, 0};

			ll dif = rank[b] - rank[a];
			ll temp = 0, llevo = 1;

			while(dif){

				if(dif&1){
					ret.F += llevo;
					ret.S += sparse[b][temp].S;
					b = sparse[b][temp].F;
				}

				llevo*= 2;
				temp++;
				dif = dif >> 1;
			}

			if(a == b) return ret;

			llevo = (1 << 19);

			for(ll i = 19; i >= 0; i--){

				if(sparse[a][i].F != sparse[b][i].F){
					ret.F += 2*llevo;
					ret.S += sparse[a][i].S + sparse[b][i].S;
					a = sparse[a][i].F;
					b = sparse[b][i].F;
				}

				llevo/= 2;
			}

			ret.F+= 2;
			ret.S += sparse[a][0].S + sparse[b][0].S;

			return ret;
		}

		//procesos

		void pre_calcular(){
			//lca
			dfs(1, 0, 0);
			sparse_fill();

	        //centroids
			rootc = find_centroid(1, 0);
            fatherc[rootc] = 0;
		}

        void delet(){
            ans = INF;
            ll tempo;
            while(eliminar.size()){
                tempo = eliminar.back(); eliminar.pop_back();
                ramas[0][tempo] = INF;
                ramas[1][tempo] = INF;
            }
        }

        void evaluate(ll fact, ll type){
			
            pll me;
            ll ori = fact;

            while(fact != 0){
                eliminar.PB(fact);
                me = lca_calc(ori, fact);

				ramas[type][fact] = min(ramas[type][fact], me.S);
				
				if(ramas[ (type+1)%2 ][fact] != INF){
					ans = min(ans, ramas[0][fact] + ramas[1][fact]);
				}
				
                fact = fatherc[fact];
            }           
        }

		ll answer(){
			return ans;
		}

};

Tree arbol;

void Init(int N, int A[], int B[], int D[]){
	
	arbol.create(N);

	for(ll i = 0; i+1 < N; i++){
		arbol.add(A[i]+1, B[i]+1, D[i]);
	}

	arbol.pre_calcular();
}

ll Query(int S, int X[], int T, int Y[]){

	arbol.delet();

	for(ll i = 0; i < S; i++){
		arbol.evaluate(X[i]+1, 0);
	}

	for(ll i = 0; i < T; i++){
		arbol.evaluate(Y[i]+1, 1);
	}

	return arbol.answer();

}


void solve(){

	ll n, q;
	cin >> n >> q;

	Tree arbol;
	arbol.create(n+1);

	ll u, v, w;

	for(ll i = 1; i < n; i++){
		cin >> u >> v >> w;
		u++; v++;
		arbol.add(u,v,w);
	}

	arbol.pre_calcular();
	ll s, t, temp;

	for(ll i = 0; i < q; i++){
		arbol.delet();
		cin >> s >> t;

		for(ll i2 = 0; i2 < s; i2++){
			cin >> temp;
			temp++;
			arbol.evaluate(temp, 0);
		}

		for(ll i2 = 0; i2 < t; i2++){
			cin >> temp;
			temp++;
			arbol.evaluate(temp, 1);
		}

		cout << arbol.answer() << endl;
	}

}

/*
int main(){ 
		
	//ifstream fin ("text.in");
	//ofstream fout ("text.out"); 

	ll t = 1;
	while(t--) solve();

	return 0;
}
*/

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