Submission #393188

#	Time	Username	Problem	Language	Result	Execution time	Memory
393188		jeroenodb	Factories (JOI14_factories)	C++14	100 / 100	4172 ms	249372 KiB

factories

#include "factories.h"
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 5e5+1;
const ll oo = 1e18;
vector<pair<int,ll>> adj[mxN];
int sz[mxN];
bitset<mxN> visited;
struct anc {
    int i;
    ll d;
};
anc ancs[mxN][20];
int ancsz[mxN];
int curcentroid;
void dfsz(int at,int from=-1) {
    sz[at]=1;
    for(auto [to,w]: adj[at]) if(to!=from and !visited[to]) {
        dfsz(to,at);
        sz[at]+=sz[to];
    }
}
void dfsd(int at,int from=-1,ll d=0) {
    ancs[at][ancsz[at]++] = {curcentroid,d};
    for(auto [to,w]: adj[at]) if(to!=from and !visited[to]) {
        dfsd(to,at,w+d);
    }
}
int centroid(int at) {
    int from=-1,total=sz[at];
    bool done = false;
    while(!done) {
        done = true;
        for(auto [to,w]: adj[at]) if(to!=from and !visited[to]) {
            if(sz[to]*2>total) {
                from = at;
                at = to;
                done = false;
                break;
            }
        }
    }
    return at;
}
void decomp(int at) {
    dfsz(at);
    int c = curcentroid = centroid(at);
    dfsd(c);

    visited[c] = true;
    for(auto [to,w]: adj[c]) if(!visited[to]) {
        decomp(to);
    }
    visited[c]= false;
}
ll mn[mxN];
void Init(int N, int A[], int B[], int D[]) {
    for(int i=0;i<N;++i) {
        adj[i].clear();
        ancsz[i]=0;
    }
    for(int i=0;i<N-1;++i) {
        adj[A[i]].push_back({B[i],D[i]});
        adj[B[i]].push_back({A[i],D[i]});
    }
    decomp(0);
    fill(mn,mn+N,oo);
}


int st[mxN],p;
long long Query(int S, int X[], int T, int Y[]) {
    p=0;
    for(int i=0;i<S;++i) {
        int x = X[i];
        for(int j=0;j<ancsz[x];++j) {
            auto& a = ancs[x][j];
            if(mn[a.i]==oo) {
                st[p++]=a.i;  
            }
            mn[a.i] = min(mn[a.i],a.d);
        }
    }
    ll ans = oo;
    for(int i=0;i<T;++i) {
        int y = Y[i];
        for(int j=0;j<ancsz[y];++j) {
            auto& a = ancs[y][j];
            ans = min(ans, mn[a.i]+a.d);
        }
    }
    for(int i=0;i<p;++i) {
        mn[st[i]] = oo;
    }
    return ans;
}

Compilation message (stderr)

factories.cpp: In function 'void dfsz(int, int)':
factories.cpp:23:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   23 |     for(auto [to,w]: adj[at]) if(to!=from and !visited[to]) {
      |              ^
factories.cpp: In function 'void dfsd(int, int, ll)':
factories.cpp:30:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   30 |     for(auto [to,w]: adj[at]) if(to!=from and !visited[to]) {
      |              ^
factories.cpp: In function 'int centroid(int)':
factories.cpp:39:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   39 |         for(auto [to,w]: adj[at]) if(to!=from and !visited[to]) {
      |                  ^
factories.cpp: In function 'void decomp(int)':
factories.cpp:56:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   56 |     for(auto [to,w]: adj[c]) if(!visited[to]) {
      |              ^

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