Submission #959005

#	Time	Username	Problem	Language	Result	Execution time	Memory
959005		YassirSalama	Factories (JOI14_factories)	C++17	0 / 100	8063 ms	161104 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];
}
bool vis[MAXN];

int dfs2(int node, int p, int n) {
  for (auto x: v[node]) {
    if (x.F != p) {
      if (!vis[x.F] && sub[x.F] > n / 2) {
        return dfs2(x.F, node, n);
      }
    }
  }

  return node;
}
void build(int node = 0, int p = -1) {
  dfs1(node,node);

  int c = dfs2(node, -1, sub[node]);
  vis[c] = true;
  par[c] = p;

  for (auto x: v[c]) {
    if (!vis[x.F]) {
      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;
}
void clear(int x){
    int node=x;
    while(node!=-1){
        ans[node]=1e18;
        node=par[node];
    }
}
// void update(int x){
//     int node=x;
//     while(node!=-1){
//         ans[node]=min(ans[node],dist(x,node));
//         node=par[node];
//     }
// }
// ll query(int x){
//     ll anss=1e18;
//     int node=x;
//     while(node!=-1){
//         anss=min(anss,ans[node]+dist(x,node));
//         node=par[node];
//     }
//     return anss;
// }
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]==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: 0 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67