Submission #656640

#	Time	Username	Problem	Language	Result	Execution time	Memory
656640		minhcool	Factories (JOI14_factories)	C++17	0 / 100	10 ms	12500 KiB

factories

#include<bits/stdc++.h>
#include "factories.h"
using namespace std;
 
#define ll long long
#define fi first
#define se second
#define pb push_back
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const ll N = 5e5 + 5, oo = 1e18 + 7, mod = 1e9 + 7;
 
ll n;
vector<pair<ll, ll>> Adj[N];
 
ll d1[N], d2[N];
 
ll anc[N][20];
//dist[N][20];
 
void dfs(int u, int p){
    for(auto it : Adj[u]){
        int v = it.fi, w = it.se;
        if(v == p) continue;
        d1[v] = d1[u] + 1;
        d2[v] = d2[u] + w;
        anc[v][0] = u;
        //dist[v][0] = w;
        dfs(v, u);
    }
}
 
void prep(){
    for(int i = 1; i <= 19; i++){
        for(int j = 1; j <= n; j++){
            anc[j][i] = anc[anc[j][i - 1]][i - 1];
            //dist[j][i] = dist[j][i - 1] + dist[anc[j][i - 1]][i - 1];
        }
    }
}
 
int lca(int x, int y){
    if(d1[x] > d1[y]) swap(x, y);
    for(int i = 19; i >= 0; i--){
        if((d1[x] + (1LL << i)) <= d1[y]) y = anc[y][i];
    }
    if(x == y) return x;
    for(int i = 19; i >= 0; i--){
        if(anc[x][i] != anc[y][i]){
            x = anc[x][i], y = anc[y][i];
        }
    }
    return anc[x][0];
}
 
ll dist(int x, int y){
    return d2[x] + d2[y] - 2 * d2[lca(x, y)];
}
 
int cnt;
int pos[N], l[N], r[N];
int arr[N];
 
void pre_dfs(int u, int p){
    cnt++;
    pos[u] = l[u] = cnt;
    arr[cnt] = u;
    for(auto it : Adj[u]){
        int v = it.fi;
        if(v == p) continue;
        pre_dfs(v, u);
    }
    r[u] = cnt;
}
 
void Init(int N, int A[], int B[], int D[]){
    n = N;
    for(int i = 0; i < (n - 1); i++){
        Adj[A[i] + 1].pb({B[i] + 1, D[i]});
        Adj[B[i] + 1].pb({A[i] + 1, D[i]});
    }
    pre_dfs(1, 1);
    dfs(1, 1);
    prep();
}
 
bool choose1[N], choose2[N];
 
int IT[N << 2];
 
vector<int> vis;
 
void upd(int id, int l, int r, int L, int R, int val){
    if(l > R || r < L) return;
    vis.pb(id);
    if(l >= L && r <= R){
        IT[id] = val;
        return;
    }
    if(IT[id]){
        IT[id << 1] = IT[id << 1 | 1] = IT[id];
        IT[id] = 0;
    }
    int mid = (l + r) >> 1;
    upd(id << 1, l, mid, L, R, val);
    upd(id << 1 | 1, mid + 1, r, L, R, val);
}
 
int get(int id, int l, int r, int pos){
    vis.pb(id);
    if(l == r){
        return IT[id];
    }
    if(IT[id]){
        IT[id << 1] = IT[id << 1 | 1] = IT[id];
        IT[id] = 0;
    }
    int mid = (l + r) >> 1;
    if(pos <= mid) return get(id << 1, l, mid, pos);
    else return get(id << 1 | 1, mid + 1, r, pos);
}
 
int sub[N];
 
 
ll Query(int S, int X[], int T, int Y[]){
    return 0;
    vis.clear();
    // build the subtree part
    vector<pair<ll, ll>> nodes;
    for(int i = 0; i < S; i++) nodes.pb({d2[X[i] + 1], X[i] + 1});
    sort(nodes.begin(), nodes.end());
    vector<pair<ll, ll>> queries;
    int cnt = -1;
    for(auto it : nodes){
        cnt++;
        ll u = it.se;
        ll temp = get(1, 1, n, pos[u]), temp3 = u;
        if(!temp) temp3 = 1;
        else{
            ll temp2 = dist(temp, sub[temp]);
            for(int i = 19; i >= 0; i--){
                int x = anc[temp3][i];
                if(!x) continue;
                if((temp2 + (d2[x] - d2[sub[temp]])) > (d2[u] - d2[x])) temp3 = x;
            }
        }
        sub[u] = temp3;
        upd(1, 1, n, l[temp3], r[temp3], u);
        queries.pb({l[temp3], cnt});
        queries.pb({r[temp3] + 1, cnt});
    }
    sort(queries.begin(), queries.end());
    set<int> cur;
    // process part
    vector<ii> nodes2;
    for(int i = 0; i < T; i++) nodes2.pb({pos[Y[i] + 1], Y[i] + 1});
    sort(nodes2.begin(), nodes2.end());
    int itr = 0;
    ll answer = oo;
    for(auto it : nodes2){
        while(itr < queries.size() && queries[itr].fi <= it.fi){
            if(cur.find(queries[itr].se) != cur.end()) cur.erase(queries[itr].se);
            else cur.insert(queries[itr].se);
            itr++;
        }
        assert(cur.size());
        int temp = (*cur.rbegin());
        answer = min(answer, dist(it.se, nodes[temp].se));
    }
    for(auto it : vis) IT[it] = 0;
    return answer;
    /*
    if(S <= 5000 && T <= 5000){
        ll ans = oo;
        for(int i = 0; i < S; i++){
            for(int j = 0; j < T; j++) ans = min(ans, dist(X[i] + 1, Y[j] + 1));
        }
        return ans;
    }
    else{
        answer = oo;
        //vis.clear();
        for(int i = 0; i < S; i++) choose1[X[i] + 1] = 1;
        for(int i = 0; i < T; i++) choose2[Y[i] + 1] = 1;
        ini(1, 1, n);
        main_dfs(1, 1);
        for(int i = 0; i < S; i++) choose1[X[i] + 1] = 0;
        for(int i = 0; i < T; i++) choose2[Y[i] + 1] = 0;
        return answer;
        //vis.clear();
    }*/
 
}
 
/*
void process(){
    int n, q;
    vector<int> a(n - 1), b(n - 1), d(n - 1);
    cin >> n >> q;
    for(int i = 0; i < (n - 1); i++){
        cin >> a[i] >> b[i] >> d[i];
    }
    Init(n, a, b, d);
    while(q--){
        int sz1, sz2;
        vector<int> vc1, vc2;
        cin >> sz1 >> sz2;
        vc1.resize(sz1);
        for(int i = 0; i < sz1; i++) cin >> vc1[i];
        vc2.resize(sz2);
        for(int i = 0; i < sz2; i++) cin >> vc2[i];
        cout << Query(sz1, vc1, sz2, vc2) << "\n"; 
    }
}
 
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    process();
}*/

Compilation message (stderr)

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:165:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  165 |         while(itr < queries.size() && queries[itr].fi <= it.fi){
      |               ~~~~^~~~~~~~~~~~~~~~

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