Submission #874963

#	Time	Username	Problem	Language	Result	Execution time	Memory
874963		YassirSalama	Factories (JOI14_factories)	C++17	33 / 100	8090 ms	195604 KiB

factories

#include"factories.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <iomanip>
#include <cmath>
#include <limits>
#include <map>
#include <utility>
#include <cctype>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include <functional>
#include <iterator>
#include<assert.h>
using namespace std;
#define OVL(x,s) for(auto y:x) cout<<y<<s; cout<<"\n";
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);
#define endl "\n"
#define pb push_back
#define F first
#define S second
#define ll long long
#define mod 1000000007
#define all(v) v.begin(),v.end()
const int MAXN=5e5+100;
const int LOGN=21;
int up[MAXN][LOGN];
set<pair<int,int>> v[MAXN];
ll depth[MAXN];
int depth1[MAXN];
int par[MAXN];
int sub[MAXN];
bool visited[MAXN];
ll ans[MAXN];
void dfs(int node,int par){
	depth1[node]=depth1[par]+1;
	up[node][0]=par;
	for(int i=1;i<LOGN;i++){
		up[node][i]=up[up[node][i-1]][i-1];
	}
	for(auto x:v[node]){
		if(x.F==par) continue;
		depth[x.F]=depth[node]+x.S;
		dfs(x.F,node);
	}
}
int LCA(int a,int b){
	if(depth1[a]<depth1[b]) swap(a,b);
	ll d=depth1[a]-depth1[b];
	for(ll i=LOGN-1;i>=0;i--){
		if(d&(1<<i)) a=up[a][i]; 
	}
	if(a==b) return a;
	for(ll i=LOGN-1;i>=0;i--){
		if(up[a][i]==up[b][i]) continue;
		a=up[a][i];
		b=up[b][i];
	}
	return up[a][0];
}
ll dist(int a,int b){
	return depth[a]+depth[b]-2*depth[LCA(a,b)];
}
int dfs1(int node,int par){
	sub[node]=1;
	for(auto x:v[node]) {
	    if(x.F==par) continue;
	    sub[node]+=dfs1(x.F,node);
	}
	return sub[node];
}
int dfs2(int node,int par,int n){
	for(auto x:v[node]){
		if(x.F!=par&&sub[x.F]>n/2)
			return dfs2(x.F,node,n);
	}
	return node;
}
void build(int u, int p) {
  int n = dfs1(u, p);
  int c = dfs2(u, p, n);
  par[c] = p;

  // vector<pair<int,int>> tmp(v[c].begin(), v[c].end());
  for(auto x : v[c]) {
  	if(x.F==p) continue;
    // v[c].erase({x.F,x.S}); 
    v[x.F].erase({c,x.S});
    build(x.F, c);
  }
}
void Init(int N, int A[], int B[], int D[]){
	for(int i=0;i<N-1;i++){
		v[A[i]].insert({B[i],D[i]});
		v[B[i]].insert({A[i],D[i]});
	}
	dfs(0,0);
	build(0,-1);
	for(int i=0;i<=N;i++) ans[i]=1e18;
}
long long Query(int S, int X[], int T, int Y[]){
	ll anss=1e18;
	for(int i=0;i<T;i++){
		int node=Y[i];
		while(node!=-1){
			ans[node]=min(ans[node],dist(Y[i],node));
			node=par[node];
		}
	}
	for(int i=0;i<S;i++) {
		int node=X[i];
		while(node!=-1){
			anss=min(anss,ans[node]+dist(X[i],node));
			node=par[node];
		}
	}
	for(int i=0;i<T;i++){
		int node=Y[i];
		while(node!=-1){
			if(ans[node]==(int)1e18) break;
			ans[node]=1e18;
			node=par[node];
		}
	}	return anss;
}

#ifdef IOI


int main(){
	// Init(7, {0, 1, 2, 2, 4, 1}, {1, 2, 3, 4, 5, 6}, {4, 4, 5, 6, 5, 3});
	// cout<<Query(2, 2, {0, 6}, {3, 4}); //returns 12.
	// cout<<endl<<Query(3, 2, {0, 1, 3}, {4, 6}); //returns 3.
	// cout<<endl<<Query(1, 1, {2}, {5}); //returns 11.
	// return 0;
    int N, Q;
    assert(scanf("%i %i", &N, &Q) == 2);
    int *A = (int*)malloc(sizeof(int) * (N - 1));
    int *B = (int*)malloc(sizeof(int) * (N - 1));
    int *D = (int*)malloc(sizeof(int) * (N - 1));
    for(int a = 0; a < N - 1; a++){
        assert(scanf("%i %i %i", A + a, B + a, D + a) == 3);
    }
    Init(N, A, B, D);
    for(int a = 0; a < Q; a++){
        int S, T;
        assert(scanf("%i %i", &S, &T) == 2);
        int *X = (int*)malloc(sizeof(int) * S);
        int *Y = (int*)malloc(sizeof(int) * T);
        for(int b = 0; b < S; b++){
            assert(scanf("%i", X + b) == 1);
        }
        for(int b = 0; b < T; b++){
            assert(scanf("%i", Y + b) == 1);
        }
        printf("%i\n", Query(S, X, T, Y));
        free(X);
        free(Y);
    }
    free(A);
    free(B);
    free(D);
}
#endif

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