oj.uz

Submission #706214

# Submission time Handle Problem Language Result Execution time Memory
706214 2023-03-06T05:02:42 Z bLIC Factories (JOI14_factories) C++17
100 / 100
 4202 ms 221248 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 = 22;
 
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;
}
  

int n, m;
ll ans;

vector<vector<pii>> adj;
vl dist[maxN];
bool used[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 dfs(int node, ll d, int p){
    dist[node].push_back(d);
    for (pii x:adj[node]){
        if (x.ft!=p && !used[x.ft]){
            dfs(x.ft, d+x.sd, node);
        }
    }
}

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


    
    dfs(centroid, 0, par);

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

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;
    int up = 1;
    while(parent[node]!=-1){
        node = parent[node];
        nearest[node] = min(nearest[node], dist[temp][up++]);
    }
}

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;
    int up = 1;
    while(parent[node]!=-1){
        node = parent[node];
        ret = min(ret, dist[temp][up++] + nearest[node]);
    }
    return ret;
}


void Init(int N, int A[], int B[], int D[]){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    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});
    }

    DOO(adj);
    build(0, -1);
    for (int i = 0;i<n;i++) {
        reverse(all(dist[i]));
    }
}

long long Query(int S, int X[], int T, int Y[]){
    ll res = INFLL;

    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]);

    return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12372 KB Output is correct
2 Correct 234 ms 21488 KB Output is correct
3 Correct 255 ms 21896 KB Output is correct
4 Correct 272 ms 21732 KB Output is correct
5 Correct 282 ms 22096 KB Output is correct
6 Correct 176 ms 21160 KB Output is correct
7 Correct 257 ms 21988 KB Output is correct
8 Correct 271 ms 21836 KB Output is correct
9 Correct 259 ms 22048 KB Output is correct
10 Correct 176 ms 21216 KB Output is correct
11 Correct 258 ms 21748 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12168 KB Output is correct
2 Correct 2019 ms 130580 KB Output is correct
3 Correct 3202 ms 166904 KB Output is correct
4 Correct 674 ms 80248 KB Output is correct
5 Correct 3899 ms 221248 KB Output is correct
6 Correct 3310 ms 167560 KB Output is correct
7 Correct 833 ms 45124 KB Output is correct
8 Correct 296 ms 34520 KB Output is correct
9 Correct 1073 ms 53656 KB Output is correct
10 Correct 847 ms 46352 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12372 KB Output is correct
2 Correct 234 ms 21488 KB Output is correct
3 Correct 255 ms 21896 KB Output is correct
4 Correct 272 ms 21732 KB Output is correct
5 Correct 282 ms 22096 KB Output is correct
6 Correct 176 ms 21160 KB Output is correct
7 Correct 257 ms 21988 KB Output is correct
8 Correct 271 ms 21836 KB Output is correct
9 Correct 259 ms 22048 KB Output is correct
10 Correct 176 ms 21216 KB Output is correct
11 Correct 258 ms 21748 KB Output is correct
12 Correct 8 ms 12168 KB Output is correct
13 Correct 2019 ms 130580 KB Output is correct
14 Correct 3202 ms 166904 KB Output is correct
15 Correct 674 ms 80248 KB Output is correct
16 Correct 3899 ms 221248 KB Output is correct
17 Correct 3310 ms 167560 KB Output is correct
18 Correct 833 ms 45124 KB Output is correct
19 Correct 296 ms 34520 KB Output is correct
20 Correct 1073 ms 53656 KB Output is correct
21 Correct 847 ms 46352 KB Output is correct
22 Correct 2226 ms 130956 KB Output is correct
23 Correct 2436 ms 134148 KB Output is correct
24 Correct 3550 ms 168144 KB Output is correct
25 Correct 3545 ms 171896 KB Output is correct
26 Correct 3519 ms 168788 KB Output is correct
27 Correct 4202 ms 217624 KB Output is correct
28 Correct 808 ms 83924 KB Output is correct
29 Correct 3489 ms 168212 KB Output is correct
30 Correct 3565 ms 167656 KB Output is correct
31 Correct 3505 ms 168220 KB Output is correct
32 Correct 918 ms 54568 KB Output is correct
33 Correct 296 ms 35016 KB Output is correct
34 Correct 584 ms 40812 KB Output is correct
35 Correct 580 ms 41164 KB Output is correct
36 Correct 800 ms 43904 KB Output is correct
37 Correct 794 ms 43836 KB Output is correct