oj.uz

Submission #706173

# Submission time Handle Problem Language Result Execution time Memory
706173 2023-03-06T03:57:17 Z bLIC Factories (JOI14_factories) C++17
100 / 100
 5894 ms 381164 KB 
/**
 *  Author: Anil Byar
**/
 
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
 
// using namespace __gnu_pbds;
using namespace std;
 
// template<class T>
// using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
 
 
 
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)(x).size()
#define ft first
#define sd second
#define pb push_back
 
// Source: https://codeforces.com/blog/entry/68809
// { start
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
// } end
 
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<pll> vll;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
typedef vector<vl> vvl;
 
#define dbg if(0)
 
const ll MOD = 1e9+7;
const ll MOD9 = 998244353;
const ll INFLL = 1e18+5;
const int INF = 1e9;
const int maxN = 5e5+5;
const int maxK = 21;
 
void printbit(int x, int len) {string s="\n";while(len--){s=((x%2)?'1':'0')+s;x/=2;} cout<<s;}
 

ll gcd(ll a, ll b) {if (b > a) {return gcd(b, a);} if (b == 0) {return a;} return gcd(b, a % b);}
ll expo(ll a, ll b, ll mod) {ll res = 1; while (b > 0) {if (b & 1)res = (res * a) % mod; a = (a * a) % mod; b = b >> 1;} return res;}
void extendgcd(ll a, ll b, ll*v) {if (b == 0) {v[0] = 1; v[1] = 10; v[2] = a; return ;} extendgcd(b, a % b, v); ll x = v[1]; v[1] = v[0] - v[1] * (a / b); v[0] = x; return;} //pass an arry of size1 3
ll mod_add(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a + b) % m) + m) % m;}
ll mod_mul(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a * b) % m) + m) % m;}
ll mod_sub(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a - b) % m) + m) % m;}
ll mminv(ll a, ll b) {ll arr[3]; extendgcd(a, b, arr); return mod_add(arr[0], 0, b);} //for non prime b


template<class T>
istream& operator>>(istream&in, vector<T>&v){
    for (T& x:v) in>>x;
    return in;
}
template<class T>
ostream& operator<<(ostream&out, vector<T>&v){
    for (T& x:v) out<<x<<' ';
    cout<<'\n';
    return out;
}
  
template <class T> struct SparseTable {
    int n, K = 25; T ID;
    std::vector<int> lg;
    std::vector<std::vector<T>> table;
    SparseTable(){}
    SparseTable(int _n,T id){
        ID = id;
        n = _n;
        lg.resize(n+1, 0);
        table.resize(n+1, std::vector<T>(K, ID));
    }
    void build(std::vector<T> array){
        for (int i = 2;i<=n;i++) lg[i] = lg[i/2] + 1;
        for (int i = 0;i<n;i++) table[i][0] = array[i];
        for (int i = 1;(1<<i)<=n;i++){
            for (int j = 0;j<=n-(1<<i);j++){
                table[j][i] = oper(table[j][i-1], table[j+(1<<(i-1))][i-1]);
            }
        }
    }
    T oper(T a, T b){return min(a, b);} // change the operation as required
    T query(int a, int b){ // inclusive a, b, i.e. [a, b], indexing 0 to n-1;
        int bit = lg[b-a+1];
        return oper(table[a][bit], table[b+1-(1<<bit)][bit]);
    }
};


int n, m;
ll ans;

ll dist(int a, int b);
vector<vector<pii>> adj;
int par[maxN][maxK];
int dep[maxN];
bool used[maxN];
ll depth[maxN];
int st[maxN], en[maxN];
int tim;
vii tour;
std::vector<int> parent, stree;
vector<ll> nearest;

void DOO(std::vector<std::vector<pii>>& _adj){
    parent.resize((int)_adj.size());
    stree.resize((int)_adj.size());
    nearest.assign((int)_adj.size(), INFLL);
}

int dfssize(int, int);
int dfscentroid(int, int, int);

void build(int node = 1, int par = -1){
    int n = dfssize(node, par);
    int centroid = dfscentroid(node, par, n);
    parent[centroid] = par;
    used[centroid] = true;

    for (const pii &y:adj[centroid]) {
        int x = y.ft;
        if (x!=par && !used[x]) build(x, centroid);
    }
}

int dfssize(int node, int par){
    stree[node] = 1;
    for (const pii &y:adj[node]){
        int x = y.ft;
        if (x!=par && !used[x]) {
            dfssize(x, node);
            stree[node] += stree[x];
        }
    }
    return stree[node];
}

int dfscentroid(int node, int par, int n){
    for (const pii &y:adj[node]){
        int x = y.ft;
        if (x!=par && !used[x] && stree[x]>n/2) return dfscentroid(x, node, n);
    }
    return node;
}

void color(int node){
    nearest[node] = 0;
    int temp = node;
    while(parent[node]!=-1){
        node = parent[node];
        nearest[node] = min(nearest[node], dist(temp, node));
    }
}

void decolor(int node){
    nearest[node] = INFLL;
    while(parent[node]!=-1){
        node = parent[node];
        if (nearest[node]==INFLL) break;
        nearest[node] = INFLL;
    }
}

ll getnearest(int node){
    ll ret = nearest[node];
    int temp = node;
    while(parent[node]!=-1){
        node = parent[node];
        ret = min(ret, dist(temp, node) + nearest[node]);
    }
    return ret;
}



void dfs(int node, int p){
    tour.pb({dep[node], node});
    st[node] = tim++;
    for (const pii &y:adj[node]){
        int x = y.ft;
        if (x==p) continue;
        par[x][0] = node;
        dep[x] = dep[node] + 1;
        depth[x] = depth[node] + y.sd;
        dfs(x, node);
        tour.pb({dep[node], node});
    }
    en[node] = tim++;
}

int kup(int node, int h){
    for (int i = 0;i<maxK;i++){
        if ((h>>i)&1) node = par[node][i];
    }
    return node;
}


int lca(int x, int y){
    if (dep[x]>dep[y]) swap(x, y);
    y = kup(y, dep[y]-dep[x]);
    if (x==y) return x;
    for (int i = maxK-1;i>=0;i--){
        if (par[x][i]!=par[y][i]) x = par[x][i], y = par[y][i];
    }
    return par[x][0];
}

SparseTable<pii> table;
ll dist(int u, int v){
    if (st[u]>st[v]) swap(u, v);
    int lc = table.query(st[u], st[v]).sd;
    return depth[u]+depth[v]-2*depth[lc];
}


void Init(int N, int A[], int B[], int D[]){
    n = N;
    adj.resize(n);
    for (int i = 0;i<n-1;i++){
        int u = A[i], v = B[i], w = D[i];
        adj[u].pb({v, w});
        adj[v].pb({u, w});
    }
    tour.reserve(n);
    dfs(0, -1);
    table = SparseTable<pii>(tim, {INF, -1});
    table.build(tour);
    for (int j = 1;j<maxK;j++){
        for (int i = 0;i<n;i++) par[i][j] = par[par[i][j-1]][j-1];
    }
    DOO(adj);
    build(0, -1);
}

long long Query(int S, int X[], int T, int Y[]){
    ll res = INFLL;
    if (S<T){
        for (int i = 0;i<S;i++) color(X[i]);
        for (int i = 0;i<T;i++) res = min(res, getnearest(Y[i]));
        for (int i = 0;i<S;i++) decolor(X[i]);
    } else {
        for (int i = 0;i<T;i++) color(Y[i]);
        for (int i = 0;i<S;i++) res = min(res, getnearest(X[i]));
        for (int i = 0;i<T;i++) decolor(Y[i]);
    }
    return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1108 KB Output is correct
2 Correct 374 ms 13628 KB Output is correct
3 Correct 515 ms 13732 KB Output is correct
4 Correct 505 ms 13888 KB Output is correct
5 Correct 491 ms 14248 KB Output is correct
6 Correct 193 ms 13636 KB Output is correct
7 Correct 513 ms 13664 KB Output is correct
8 Correct 489 ms 13668 KB Output is correct
9 Correct 525 ms 13992 KB Output is correct
10 Correct 220 ms 13624 KB Output is correct
11 Correct 515 ms 13680 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 2567 ms 342008 KB Output is correct
3 Correct 3391 ms 345504 KB Output is correct
4 Correct 1109 ms 342952 KB Output is correct
5 Correct 4246 ms 379496 KB Output is correct
6 Correct 3519 ms 364800 KB Output is correct
7 Correct 1977 ms 91452 KB Output is correct
8 Correct 488 ms 91628 KB Output is correct
9 Correct 1978 ms 96160 KB Output is correct
10 Correct 1960 ms 92692 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1108 KB Output is correct
2 Correct 374 ms 13628 KB Output is correct
3 Correct 515 ms 13732 KB Output is correct
4 Correct 505 ms 13888 KB Output is correct
5 Correct 491 ms 14248 KB Output is correct
6 Correct 193 ms 13636 KB Output is correct
7 Correct 513 ms 13664 KB Output is correct
8 Correct 489 ms 13668 KB Output is correct
9 Correct 525 ms 13992 KB Output is correct
10 Correct 220 ms 13624 KB Output is correct
11 Correct 515 ms 13680 KB Output is correct
12 Correct 2 ms 724 KB Output is correct
13 Correct 2567 ms 342008 KB Output is correct
14 Correct 3391 ms 345504 KB Output is correct
15 Correct 1109 ms 342952 KB Output is correct
16 Correct 4246 ms 379496 KB Output is correct
17 Correct 3519 ms 364800 KB Output is correct
18 Correct 1977 ms 91452 KB Output is correct
19 Correct 488 ms 91628 KB Output is correct
20 Correct 1978 ms 96160 KB Output is correct
21 Correct 1960 ms 92692 KB Output is correct
22 Correct 3489 ms 348976 KB Output is correct
23 Correct 3595 ms 350688 KB Output is correct
24 Correct 4640 ms 351392 KB Output is correct
25 Correct 4628 ms 354844 KB Output is correct
26 Correct 5391 ms 351132 KB Output is correct
27 Correct 5894 ms 381164 KB Output is correct
28 Correct 1378 ms 352496 KB Output is correct
29 Correct 4847 ms 352400 KB Output is correct
30 Correct 4911 ms 351232 KB Output is correct
31 Correct 4912 ms 351748 KB Output is correct
32 Correct 2007 ms 91060 KB Output is correct
33 Correct 484 ms 85756 KB Output is correct
34 Correct 1509 ms 83356 KB Output is correct
35 Correct 1543 ms 83176 KB Output is correct
36 Correct 2009 ms 84004 KB Output is correct
37 Correct 1949 ms 84132 KB Output is correct