Submission #1113891

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113891		yusufhocaoglu	Factories (JOI14_factories)	C++17	0 / 100	16 ms	16976 KiB

factories

#include "factories.h"
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define MOD2 998244353
#define ll long long
#define pri pair<int,int>
#define prl pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define vp vector<pair<int,int>>
#define vpl vector<pair<ll,ll>>
#define re return 0
#define sqrt sqrtl

vector<vp> adj;
int n;
vp ed;
vp table;
vp seg;
vi cost;
vi order;

void dfs(int x,int p,int h,int w) {
    cost[x] = w;
    ed.push_back({x,h});;
    table[x] = {ed.size(),0};
    for (auto v : adj[x]) {
        if (v.first==p) continue;
        dfs(v.first,x,h+1,w+v.second);
        ed.push_back({x,h});
    }
    order[x] = ed.size()-1;
    table[x].second = ed.size();
}
//int min(int a,int b) return a<b?a:b;
int lca(int u,int v) {
    int l = min(min(table[u].first,table[u].second),min(table[v].first,table[v].second))-1;
    int r = max(max(table[u].first,table[u].second),max(table[v].first,table[v].second))-1;

    l+=ed.size();
    r+=ed.size()+1;
    pri ans = {1e9,1e9};
    for (;l<r;l/=2,r/=2) {
        if (l&1) ans=min(seg[l++],ans);
        if (r&1) ans=min(seg[--r],ans);
    }
    return ans.second;
}

void Init(int N, int A[],int B[],int D[]) {
    n = N;
    adj = vector<vp>(n);
    table = vp(n);
    cost =  vi(n);
    order = vi(n);
    for (int i = 0;i<n;i++) {
        adj[A[i]].push_back({B[i],D[i]});
        adj[B[i]].push_back({A[i],D[i]});
    }
    dfs(0,-1,0,0);
    seg = vp(2*ed.size()+1);
    int m = ed.size();
    for (int i = 0;i<m;i++) seg[i+m] = {ed[i].second,ed[i].first};
    for (int i = m-1;i>0;i--) {
        seg[i] = min(seg[2*i],seg[2*i+1]);
    }
}

ll Query(int S,int X[],int T, int Y[]) {
    ll ANS = 1e18;
    priority_queue<array<ll,3>> pq;
    for (int i = 0;i<S;i++) {
        pq.push(array<ll,3>{-order[X[i]],cost[X[i]],(int)1e18});
    }
    for (int i = 0;i<T;i++) {
        pq.push(array<ll,3>{-order[Y[i]],(int)1e18,cost[Y[i]]});
    }
    while (pq.size()>1) {
        auto a = pq.top();
        pq.pop();
        auto b = pq.top();
        pq.pop();

        //cout<<ed[-a[0]].first<<" "<<ed[-b[0]].first<<" "<<lca(ed[-a[0]].first,ed[-b[0]].first)<<" "<<a[1]<<" "<<a[2]<<" "<<b[1]<<" "<<b[2]<<endl;
        int lc  = lca(ed[-a[0]].first,ed[-b[0]].first);
        ll lch = cost[lc];
        ANS = min(ANS,min( - 2*lch + a[1] + b[2] , a[2]+b[1] - 2*lch));
        pq.push({-order[lc],min(a[1],b[1]),min(a[2],b[2])});
    }
    return ANS;
}

/*int32_t main() {
    Init(7,new int[6]{0,1,2,2,4,1},new int[6]{1,2,3,4,5,6},new int[6]{4,4,5,6,5,3});
    Query(1,new int[1]{2},1,new int[1]{5});
    return 0;
}*/

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