제출 #589611

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
589611		perchuts	공장들 (JOI14_factories)	C++17	100 / 100	3383 ms	196304 KiB

factories

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ii = pair<int,int>;
using iii = tuple<int,int,int>;

const int inf = 2e9+1;
const int mod = 1e9+7;
const int maxn = 5e5+100;

template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }

vector<pair<int,ll>>g[maxn];

int n, subt[maxn], vis[maxn], par[maxn], lvl[maxn];

ll dist[maxn][20], best[maxn];

int dfs(int u,int p,int lvl,int d){
    if(lvl!=-1)dist[u][lvl] = dist[p][lvl]+d;
    subt[u] = 1;
    for(auto [v,w]:g[u]){
        if(v==p||vis[v])continue;
        subt[u] += dfs(v,u,lvl,w);
    }
    return subt[u];
}

int find_centroid(int u,int p,int tam){
    for(auto [v,d]:g[u]){
        if(vis[v]||v==p)continue;
        if(subt[v]*2>tam)return find_centroid(v,u,tam);
    }
    return u;
}

void centroid_decomposition(int u=1,int p=-1,int w=0){
    int c = find_centroid(u,p, dfs(u,p,p==-1?-1:lvl[p],w) );
    vis[c] = 1, par[c] = p;
    if(p!=-1)lvl[c] = lvl[p] + 1;
    for(auto [v,w]:g[c]){
        if(vis[v])continue;
        centroid_decomposition(v,c,w);
    }
}

void Init(int N,int a[],int b[],int d[]) {
    n = N;
    for(int i=0;i<n-1;++i){
        ++a[i], ++b[i];
        g[a[i]].pb({b[i],d[i]});
        g[b[i]].pb({a[i],d[i]});
    }
    centroid_decomposition();
    for(int i=1;i<=n;++i)best[i] = 1e18;
}

ll distance(int u,int v){
    int su = u, sv = v;
    if(lvl[u]<lvl[v])swap(u,v), swap(su,sv);
    while(lvl[u]!=lvl[v])u = par[u];
    while(u!=v)u = par[u], v = par[v];
    return dist[su][lvl[u]] + dist[sv][lvl[u]];
}

void update(int u, bool type){
    int cur = u;
    while(cur!=-1){
        if(type)ckmin(best[cur],dist[u][lvl[cur]]);
        else best[cur] = 1e18;
        cur = par[cur];
    }
}

ll query(int u){
    ll resp = best[u];
    int cur = par[u];
    while(cur!=-1){
        ckmin(resp,best[cur]+distance(u,cur));
        cur = par[cur];
    }
    return resp;
}

long long Query(int S,int X[], int T,int Y[]) {
    for(int i=0;i<T;++i){
        update(Y[i]+1,1);
    }
    ll ans = 1e18;
    for(int i=0;i<S;++i){
        ckmin(ans,query(X[i]+1));
    }
    for(int i=0;i<T;++i)update(Y[i]+1,0);
    return ans;
}

// int main(){
//     int n,q;cin>>n>>q;
//     vector<int>a,b,d;
//     for(int i=0;i<n-1;++i){
//         int x,y,z;cin>>x>>y>>z;
//         a.pb(x), b.pb(y), d.pb(z);
//     }
//     vector<vector<int>>s, t;
//     for(int i=0;i<q;++i){
//         vector<int>sc, tc;
//         int x,y;cin>>x>>y;
//         for(int j=0;j<x;++j){
//             int z;cin>>z;
//             sc.pb(z);
//         }
//         for(int j=0;j<y;++j){
//             int z;cin>>z;
//             tc.pb(z);
//         }
//         s.pb(sc), t.pb(tc);
//     }
//     Init(n,a,b,d);
//     for(int i=0;i<q;++i){
//         cout<<Query(sz(s[i]),s[i],sz(t[i]),t[i])<<endl;
//     }
// }

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