제출 #963111

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
963111		vjudge1	공장들 (JOI14_factories)	C++17	15 / 100	576 ms	74956 KiB

factories

#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 = 112345;
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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67