Submission #1281883

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281883		LmaoLmao	Factories (JOI14_factories)	C++20	100 / 100	2102 ms	162576 KiB

factories

#include <bits/stdc++.h>
//#define int long long
#define fi first
#define se second
#define name "a"
using namespace std;

using ii = pair<long long,long long>;
using aa = array<int,3>;
const int N=1e6+5;

vector<ii> adj[N];
int in[N],out[N];
int timer=0;
long long h[N],d[N];
int up[N][19];

bool cmp(int a,int b) {
    return in[a]<in[b];
}

void dfs(int u,int p) {
    in[u]=++timer;
    up[u][0]=p;
    for(int i=1;i<=18;i++) {
        up[u][i]=up[up[u][i-1]][i-1];
    }
    for(ii v:adj[u]) {
        if(v.fi==p) continue;
        h[v.fi]=h[u]+v.se;
        dfs(v.fi,u);
    }
    out[u]=timer;
}

bool inside(int u,int v) {
    return(u==0 || (in[u]<=in[v] && out[v]<=out[u]));
}

int lca(int u,int v) {
    if(inside(u,v)) return u;
    if(inside(v,u)) return v;
    for(int i=18;i>=0;i--) {
        if(!inside(up[u][i],v)) {
            u=up[u][i];
        }
    }
    return up[u][0];
}

int mp[N];
vector<ii> g[N];

void Init(int N, int A[], int B[], int D[]) {
    int n = N;
    for (int i = 0; i < N - 1; i++){
        int u = A[i] + 1;
        int v = B[i] + 1;
        int c = D[i];
        adj[u].push_back({v,c});
        adj[v].push_back({u,c});
    }
    dfs(1,0);
}

long long Query(int S, int X[], int T, int Y[]) {
    int n=S,m=T;
    vector<int> a,b,c;
    for(int i=0;i<n;i++) {
        int u=X[i]+1;
        a.push_back(u);
        c.push_back(u);
    }
    for(int i=0;i<m;i++) {
        int u=Y[i]+1;
        b.push_back(u);
        c.push_back(u);
    }
    for(int x:c) mp[x]=1;
    sort(c.begin(),c.end(),cmp);
    for(int i=1;i<a.size()+b.size();i++) {
        int x=lca(c[i],c[i-1]);
        if(!mp[x]) c.push_back(x);
        mp[x]=1;
    }
    sort(c.begin(),c.end(),cmp);
    stack<int> st;
    for(int x:c) {
        g[x].clear();
        d[x]=1e18;
        mp[x]=0;
    }
    for(int u:c) {
        while(!st.empty() && !inside(st.top(),u)) st.pop();
        if(!st.empty()) {
            g[st.top()].push_back({u,-h[st.top()]+h[u]});
            g[u].push_back({st.top(),-h[st.top()]+h[u]});
            //cout << u << ' ' << st.top() << endl;
        }
        st.push(u);
    }
    priority_queue<ii,vector<ii>,greater<ii>> q;
    for(int x:a) {
        d[x]=0;
        q.push({0,x});
    }
    while(!q.empty()) {
        ii u=q.top();
        q.pop();
        if(u.fi > d[u.se]) continue;
        for(ii v:g[u.se]) {
            if(d[v.fi]>u.fi+v.se) {
                q.push({d[v.fi]=u.fi+v.se,v.fi});
            }
        }
    }
    long long res=363636363636363636;
    for(int u:b) {
        res=min(res,d[u]);
    }
    //cout << res << '\n';
    return res;
}

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