oj.uz

Submission #963112

# Submission time Handle Problem Language Result Execution time Memory
963112 2024-04-14T14:30:03 Z chifwin Factories (JOI14_factories) C++17
100 / 100
 4603 ms 304464 KB 
#include "factories.h"

#include <bits/stdc++.h>

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#define ll long long
#define ull unsigned long long
#define ld long double
#define vll vector<ll>
#define pll pair<ll, ll>
#define plll pair<pll, ll>
#define lpll pair<ll, pll>
#define FOR(i, start, stop) for(ll i = (start); i < (stop); i++)
#define fi(n)  FOR(i, 0, n)
#define fj(n)  FOR(j, 0, n)
#define fk(n)  FOR(k, 0, n)
#define fio(n) FOR(i, 1, n)
#define fjo(n) FOR(j, 1, n)
#define fko(n) FOR(k, 1, n)
#define fiv(n) for (ll i = n-1; i >= 0; i--)
#define fjv(n) for (ll j = n-1; j >= 0; j--)
#define fkv(n) for (ll k = n-1; k >= 0; k--)
#define f first
#define s second
#define pb push_back
#define rt return
#define cn continue;
#define br break;
#define sz(x) ((ll)x.size())
#define all(queries) begin(queries),end(queries)
#define rall(queries) (queries).rbegin(),(queries).rend()
#define YESNO(flag) cout<<(flag ? "YES" : "NO") <<'\n';
#define dbg(...) {cerr << "\033[33m" << (#__VA_ARGS__) << ": "; dbg_vals(__VA_ARGS__); cerr << "\033[0m\n";}
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

template<class T> istream& operator>>(istream& in, vector<T>& x){for(T& i : x) in >> i; return in; }
template<class T, class TT> istream& operator>>(istream& in, pair<T, TT>& x){ in >> x.f >> x.s; return in; }
template<class T, class TT> ostream& operator<<(ostream& out, const pair<T, TT>& x){ out << x.f << ' ' << x.s; return out; }
template <typename Iter, typename=decltype(declval<Iter>().begin()), typename=enable_if_t<!is_convertible_v<Iter, string>>> ostream& operator<<(ostream& out, const Iter& x){ for (const auto& i : x) out << i << ' '; return out;}

template<typename T> void dbg_vals(T x){ cerr<< "\033[31m" << x << "\033[0m"; }
template<typename T, typename... Args> void dbg_vals(T x, Args... args){ dbg_vals(x); cerr << " | "; dbg_vals(args...); }

struct custom_hash { static uint64_t splitmix64(uint64_t x) {/*http://xorshift.di.unimi.it/splitmix64.c*/ x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31);} size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();return splitmix64(x + FIXED_RANDOM);}};
template<class T> using ll_umap = unordered_map<ll, T, custom_hash>;
using ll_uset = unordered_set<ll, custom_hash>;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
template<class T, class comp=less<T>> using ordered_set = __gnu_pbds::tree<T, __gnu_pbds::null_type, comp, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
// find_by_order(k) - iterator on k's elements
// order_of_key(x) - number of elements, strictly less than x

template<class T> using min_pq = priority_queue<T, vector<T>, greater<T>>;

const ll MAXN = 512345;
const ll MOD = 1000'000'007;
const ld EPS = 1e-10;
const ll INF = (ll)(1ll<<60) + (ll)((1ll<<30)-1);
const ld PI = atanl(1)*4;

ll rll(ll r=numeric_limits<ll>::max(), ll l=0){ /*random long long*/ static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); return uniform_int_distribution<ll>(l, r)(rng); }
template<typename F> auto time_measure(F f){ auto start = chrono::steady_clock::now(); f(); auto end = chrono::steady_clock::now(); return std::chrono::duration_cast<std::chrono::microseconds>(end - start).count(); }
array<ll, 3> extgcd(ll a, ll b) { if (!b) return {a, 1, 0}; auto [d, y, x] = extgcd(b, a % b); return {d, x, y - a/b * x}; } // {gcd, x, y} such that a*x + b*y = gcd(a, b)
ll gcd(ll x, ll y){ return __gcd(x, y); }
ll binpow(ll x, ll p, ll mod){ if (p < 0) return 0; x %= mod; ll ans = 1; while(p){ if (p&1) ans = (ans*x)%mod; x = (x*x)%mod; p >>= 1; } return ans; }
ll invmod(ll x, ll mod=MOD){ return binpow(x, mod-2, mod); }
ll sign(ll x){ if (x < 0) rt -1; rt !!x; }
void FREOPEN(string s){ freopen(string(s + ".in").c_str(), "r", stdin); freopen(string(s + ".out").c_str(), "w", stdout); }
template<class T, class TT> bool mineq(T& a, const TT& b){ if (b < a) {a = b; return true;} return false;}
template<class T, class TT> bool maxeq(T& a, const TT& b){ if (b > a) {a = b; return true;} return false;}
const pll dxy[4] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
const pll dxy8[8] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};

struct Edge{
    int to, w;
    Edge(int x = 0, int w=0):to(x), w(w){}
};

ll n, m, k, q;
ll ar[MAXN], cd[MAXN];
vector<Edge> gr[MAXN];

template<int N=MAXN>
class Calc_LCA{
    constexpr static int log2_floor(int i) { return i ? __builtin_clz(1) - __builtin_clz(i) : -1; }
    constexpr static int K = log2_floor(2*N)+1;
    int pos[N], eul[2*N], lev[2*N], spt[K][2*N], t;
	int merge(int a, int b){ return lev[a] < lev[b] ? a : b; }
    int lca_h(int l, int r){ 
		if (l > r) swap(l, r);
		int i = log2_floor(r-l+1);
		return merge(spt[i][l], spt[i][r-(1ll<<i)+1]);
	}
public:
    void build(const vector<Edge> gr[]){
        function<void(int, int, int)> dfs = [&](int x, int p, int l){
            eul[t] = x, pos[x] = t, lev[t] = l; t++;
            for(Edge e : gr[x]) if (e.to != p){
                dfs(e.to, x, l+1);
                lev[t] = l, eul[t] = x; t++;
            }
        }; dfs(0, -1, 0);
        for(int i = 0; i < t; i++) spt[0][i] = i;
        for(int i = 1, k = log2_floor(t)+1; i < k; i++)
            for(int j = 0; j + (1ll<<i) < t; j++)
                spt[i][j] = merge(spt[i-1][j], spt[i-1][j + (1ll<<(i-1))]);
    }
    int lca(int a, int b){
        a = pos[a], b = pos[b];
        return eul[lca_h(a, b)];
    }
    int dist(int a, int b){
        a = pos[a], b = pos[b];
        return lev[a] + lev[b] - 2*lev[lca_h(a, b)];
    }
}; Calc_LCA lca;

template<int N=MAXN>
struct Centroids_Tree{
    int root, label[N], sizes[N];
    vector<int> parent[N];
    void build(const vector<Edge> gr[]){
        function<int(int, int)> siz = [&](int x, int p){
            sizes[x] = 1;
            for(Edge e: gr[x]) if (e.to != p) sizes[x] += siz(e.to, x);
            return sizes[x];
        }; siz(0, -1);
        fill(label, label+sizes[0], 0);
        function<int(int, int, int)> dfs = [&](int x, int pc, int lab){
            int n = sizes[x];
            for (int ok = 1, p = -1; ok; ){
                ok = 0;
                for(Edge e : gr[x]){
                    if (e.to == p || label[e.to] || sizes[e.to] <= n/2) cn;
                    ok = 1, p = x;
                    sizes[x] = n - sizes[e.to];
                    x = e.to;
                    break;
                }
                sizes[x] = n;
            }
            if (pc == -1) pc = x, parent[x].clear();
            parent[x] = parent[pc];
            parent[x].push_back(x);
            label[x] = lab;
            for(Edge e: gr[x]) if (!label[e.to]) dfs(e.to, x, lab+1);
            return x;
        };
        root = dfs(0, -1, 1);
    }
}; Centroids_Tree ctree;

void dfs(int x, int p=-1){
    for(Edge e : gr[x]){
        if (e.to != p){
            ar[e.to] = ar[x] + e.w;
            dfs(e.to, x);
        }
    }
}

void solve(){
    cin >> n;
    fi(n-1){
        ll a, b, c;
        cin >> a >> b >> c;
        a--, b--;
        gr[a].pb(Edge(b, c));
        gr[b].pb(Edge(a, c));
    }
    dfs(0);
    ctree.build(gr);
    lca.build(gr);
}

ll dist(int a, int b){
	return ar[a] + ar[b] - 2*ar[lca.lca(a, b)];
};

void Init(int n, int A[], int B[], int D[]) {
	fi(n-1){
        gr[A[i]].pb(Edge(B[i], D[i]));
        gr[B[i]].pb(Edge(A[i], D[i]));
	}
	dfs(0);
    ctree.build(gr);
    lca.build(gr);
	fi(n) cd[i] = INF;
}

long long Query(int S, int X[], int T, int Y[]) {
	fi(S){
		for(auto cur : ctree.parent[X[i]]){
			mineq(cd[cur], dist(X[i], cur));
		}
	}
	ll ans = INF;
	fi(T){
		for(auto cur : ctree.parent[Y[i]]){
			mineq(ans, cd[cur] + dist(Y[i], cur));
		}
	}
	fi(S){
		for(auto cur : ctree.parent[X[i]]){
			cd[cur] = INF;
		}
	}
  	return ans;
}

Compilation message

factories.cpp: In function 'void FREOPEN(std::string)':
factories.cpp:73:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 | void FREOPEN(string s){ freopen(string(s + ".in").c_str(), "r", stdin); freopen(string(s + ".out").c_str(), "w", stdout); }
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
factories.cpp:73:80: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 | void FREOPEN(string s){ freopen(string(s + ".in").c_str(), "r", stdin); freopen(string(s + ".out").c_str(), "w", stdout); }
      |                                                                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 74328 KB Output is correct
2 Correct 392 ms 87036 KB Output is correct
3 Correct 526 ms 87296 KB Output is correct
4 Correct 516 ms 87376 KB Output is correct
5 Correct 525 ms 87772 KB Output is correct
6 Correct 202 ms 87020 KB Output is correct
7 Correct 525 ms 87280 KB Output is correct
8 Correct 549 ms 87384 KB Output is correct
9 Correct 528 ms 87772 KB Output is correct
10 Correct 191 ms 87044 KB Output is correct
11 Correct 516 ms 87276 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 74328 KB Output is correct
2 Correct 1961 ms 211340 KB Output is correct
3 Correct 2388 ms 256628 KB Output is correct
4 Correct 827 ms 203324 KB Output is correct
5 Correct 3062 ms 304464 KB Output is correct
6 Correct 2499 ms 257076 KB Output is correct
7 Correct 1620 ms 138496 KB Output is correct
8 Correct 394 ms 129780 KB Output is correct
9 Correct 1476 ms 144700 KB Output is correct
10 Correct 1521 ms 138904 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 74328 KB Output is correct
2 Correct 392 ms 87036 KB Output is correct
3 Correct 526 ms 87296 KB Output is correct
4 Correct 516 ms 87376 KB Output is correct
5 Correct 525 ms 87772 KB Output is correct
6 Correct 202 ms 87020 KB Output is correct
7 Correct 525 ms 87280 KB Output is correct
8 Correct 549 ms 87384 KB Output is correct
9 Correct 528 ms 87772 KB Output is correct
10 Correct 191 ms 87044 KB Output is correct
11 Correct 516 ms 87276 KB Output is correct
12 Correct 12 ms 74328 KB Output is correct
13 Correct 1961 ms 211340 KB Output is correct
14 Correct 2388 ms 256628 KB Output is correct
15 Correct 827 ms 203324 KB Output is correct
16 Correct 3062 ms 304464 KB Output is correct
17 Correct 2499 ms 257076 KB Output is correct
18 Correct 1620 ms 138496 KB Output is correct
19 Correct 394 ms 129780 KB Output is correct
20 Correct 1476 ms 144700 KB Output is correct
21 Correct 1521 ms 138904 KB Output is correct
22 Correct 2935 ms 233836 KB Output is correct
23 Correct 3043 ms 236984 KB Output is correct
24 Correct 4046 ms 260212 KB Output is correct
25 Correct 4011 ms 263220 KB Output is correct
26 Correct 4065 ms 261544 KB Output is correct
27 Correct 4603 ms 300292 KB Output is correct
28 Correct 1220 ms 209848 KB Output is correct
29 Correct 3868 ms 260840 KB Output is correct
30 Correct 3805 ms 260068 KB Output is correct
31 Correct 3676 ms 261036 KB Output is correct
32 Correct 1464 ms 145936 KB Output is correct
33 Correct 347 ms 129880 KB Output is correct
34 Correct 1185 ms 132944 KB Output is correct
35 Correct 1127 ms 133072 KB Output is correct
36 Correct 1545 ms 137380 KB Output is correct
37 Correct 1571 ms 137444 KB Output is correct