oj.uz

답안 #706172

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
706172 2023-03-06T03:52:48 Z bLIC 공장들 (JOI14_factories) C++17
100 / 100
 5564 ms 398524 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});
    }
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 1108 KB Output is correct
2 Correct 370 ms 13100 KB Output is correct
3 Correct 535 ms 13176 KB Output is correct
4 Correct 494 ms 13108 KB Output is correct
5 Correct 510 ms 13432 KB Output is correct
6 Correct 196 ms 13160 KB Output is correct
7 Correct 521 ms 13052 KB Output is correct
8 Correct 507 ms 13104 KB Output is correct
9 Correct 496 ms 13512 KB Output is correct
10 Correct 198 ms 13004 KB Output is correct
11 Correct 506 ms 13096 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 2685 ms 341960 KB Output is correct
3 Correct 3587 ms 345328 KB Output is correct
4 Correct 1108 ms 342620 KB Output is correct
5 Correct 4210 ms 379472 KB Output is correct
6 Correct 3502 ms 364868 KB Output is correct
7 Correct 1936 ms 91308 KB Output is correct
8 Correct 468 ms 91600 KB Output is correct
9 Correct 1923 ms 96500 KB Output is correct
10 Correct 1929 ms 92564 KB Output is correct

Subtask #3
67.0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 1108 KB Output is correct
2 Correct 370 ms 13100 KB Output is correct
3 Correct 535 ms 13176 KB Output is correct
4 Correct 494 ms 13108 KB Output is correct
5 Correct 510 ms 13432 KB Output is correct
6 Correct 196 ms 13160 KB Output is correct
7 Correct 521 ms 13052 KB Output is correct
8 Correct 507 ms 13104 KB Output is correct
9 Correct 496 ms 13512 KB Output is correct
10 Correct 198 ms 13004 KB Output is correct
11 Correct 506 ms 13096 KB Output is correct
12 Correct 2 ms 724 KB Output is correct
13 Correct 2685 ms 341960 KB Output is correct
14 Correct 3587 ms 345328 KB Output is correct
15 Correct 1108 ms 342620 KB Output is correct
16 Correct 4210 ms 379472 KB Output is correct
17 Correct 3502 ms 364868 KB Output is correct
18 Correct 1936 ms 91308 KB Output is correct
19 Correct 468 ms 91600 KB Output is correct
20 Correct 1923 ms 96500 KB Output is correct
21 Correct 1929 ms 92564 KB Output is correct
22 Correct 3403 ms 366760 KB Output is correct
23 Correct 3567 ms 370204 KB Output is correct
24 Correct 4726 ms 370420 KB Output is correct
25 Correct 4636 ms 374664 KB Output is correct
26 Correct 4840 ms 370964 KB Output is correct
27 Correct 5564 ms 398524 KB Output is correct
28 Correct 1540 ms 370892 KB Output is correct
29 Correct 4869 ms 370124 KB Output is correct
30 Correct 4882 ms 369456 KB Output is correct
31 Correct 4737 ms 370132 KB Output is correct
32 Correct 1891 ms 97220 KB Output is correct
33 Correct 464 ms 92020 KB Output is correct
34 Correct 1488 ms 88736 KB Output is correct
35 Correct 1426 ms 88640 KB Output is correct
36 Correct 1741 ms 89448 KB Output is correct
37 Correct 1806 ms 89436 KB Output is correct