oj.uz

답안 #963116

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
963116 2024-04-14T14:31:36 Z vjudge1 공장들 (JOI14_factories) C++17
100 / 100
 4546 ms 300108 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;}

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

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 74332 KB Output is correct
2 Correct 393 ms 91896 KB Output is correct
3 Correct 528 ms 92140 KB Output is correct
4 Correct 536 ms 91988 KB Output is correct
5 Correct 551 ms 92640 KB Output is correct
6 Correct 205 ms 91880 KB Output is correct
7 Correct 519 ms 92244 KB Output is correct
8 Correct 541 ms 92132 KB Output is correct
9 Correct 531 ms 92652 KB Output is correct
10 Correct 203 ms 89936 KB Output is correct
11 Correct 557 ms 94704 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 74240 KB Output is correct
2 Correct 1977 ms 225764 KB Output is correct
3 Correct 2387 ms 252540 KB Output is correct
4 Correct 899 ms 199072 KB Output is correct
5 Correct 3156 ms 300108 KB Output is correct
6 Correct 2524 ms 252728 KB Output is correct
7 Correct 1543 ms 135360 KB Output is correct
8 Correct 378 ms 126664 KB Output is correct
9 Correct 1543 ms 141404 KB Output is correct
10 Correct 1603 ms 135616 KB Output is correct

Subtask #3
67.0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 74332 KB Output is correct
2 Correct 393 ms 91896 KB Output is correct
3 Correct 528 ms 92140 KB Output is correct
4 Correct 536 ms 91988 KB Output is correct
5 Correct 551 ms 92640 KB Output is correct
6 Correct 205 ms 91880 KB Output is correct
7 Correct 519 ms 92244 KB Output is correct
8 Correct 541 ms 92132 KB Output is correct
9 Correct 531 ms 92652 KB Output is correct
10 Correct 203 ms 89936 KB Output is correct
11 Correct 557 ms 94704 KB Output is correct
12 Correct 13 ms 74240 KB Output is correct
13 Correct 1977 ms 225764 KB Output is correct
14 Correct 2387 ms 252540 KB Output is correct
15 Correct 899 ms 199072 KB Output is correct
16 Correct 3156 ms 300108 KB Output is correct
17 Correct 2524 ms 252728 KB Output is correct
18 Correct 1543 ms 135360 KB Output is correct
19 Correct 378 ms 126664 KB Output is correct
20 Correct 1543 ms 141404 KB Output is correct
21 Correct 1603 ms 135616 KB Output is correct
22 Correct 2981 ms 227972 KB Output is correct
23 Correct 3168 ms 231048 KB Output is correct
24 Correct 4050 ms 248992 KB Output is correct
25 Correct 4030 ms 251288 KB Output is correct
26 Correct 4172 ms 249576 KB Output is correct
27 Correct 4546 ms 288188 KB Output is correct
28 Correct 1246 ms 197676 KB Output is correct
29 Correct 3937 ms 248844 KB Output is correct
30 Correct 3883 ms 248028 KB Output is correct
31 Correct 3936 ms 249016 KB Output is correct
32 Correct 1578 ms 138924 KB Output is correct
33 Correct 446 ms 123076 KB Output is correct
34 Correct 1291 ms 126188 KB Output is correct
35 Correct 1137 ms 126416 KB Output is correct
36 Correct 1450 ms 130716 KB Output is correct
37 Correct 1584 ms 130784 KB Output is correct