Submission #635466

#	Time	Username	Problem	Language	Result	Execution time	Memory
635466		Ronin13	Factories (JOI14_factories)	C++14	100 / 100	2909 ms	132360 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;

const int NMAX = 5e5 + 1;
ll linf = 1e18;

vector <vector <pll> > g(NMAX);
vector <ll> d(NMAX);
vector <int> head(NMAX);
vector <int> sz(NMAX);
vector <int> p(NMAX);

void dfs(int v, int e = -1){
    sz[v] = 1;
    p[v] = e;
    for(auto x : g[v]){
        int to = x.f;
        ll len = x.s;
        if(to == e) continue;
        d[to] = d[v] + len;
        dfs(to, v);
        sz[v] += sz[to];
    }
}

//vector <vector <int> > path(NMAX);
vector <int> lead(NMAX);
vector <ll> mn(NMAX, linf);

vector <pair<pll, pii> > vec;

void lift(int x, int ind){
    int cur = x;
    while(x != -1){
        vec.pb({{d[x], d[cur]}, {lead[x], ind}});
        x = lead[x]; x = p[x];
    }
}

void prep(int v, int head, int e = -1){
    lead[v] = head;
    for(auto x : g[v]){
        int to = x.f;
        if(to == e) continue;
        if(sz[to] * 2 > sz[v]){
            prep(to, head, v);
        }
        else prep(to, to, v);
    }
}

ll cur[NMAX][2];

int n;

void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for(int i = 0; i < n - 1; i++){
        g[A[i]].pb({B[i], D[i]});
        g[B[i]].pb({A[i], D[i]});
    }
    dfs(0);
    prep(0, 0);
    for(int i = 0; i <= n; i++){
        cur[i][0] = cur[i][1] = 1e18;
    }
}

long long Query(int S, int X[], int T, int Y[]) {
    ll ans = linf;
    for(int i = 0; i < S; i++){
        lift(X[i], 0);
    }
    for(int i = 0; i < T; i++){
        lift(Y[i], 1);
    }
    sort(vec.begin(), vec.end());
    reverse(vec.begin(), vec.end());
    for(int i = 0; i < vec.size(); i++){
        int ind = vec[i].s.s;
        ll v = vec[i].f.f, xx = vec[i].f.s;
        int lll = vec[i].s.f;
        ans = min(ans, cur[lll][ind ^ 1] + xx - 2 * v);
        cur[lll][ind] = min(cur[lll][ind], xx);
    }
    for(int i = 0; i < vec.size(); i++){
        int lll = vec[i].s.f;
        cur[lll][1] = cur[lll][0] = linf;
    }
    vec.clear();
    return ans;
}

Compilation message (stderr)

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:88:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, long long int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for(int i = 0; i < vec.size(); i++){
      |                    ~~^~~~~~~~~~~~
factories.cpp:95:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, long long int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for(int i = 0; i < vec.size(); i++){
      |                    ~~^~~~~~~~~~~~

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