Submission #1111872

#TimeUsernameProblemLanguageResultExecution timeMemory
1111872whyalwaysmezzzFactories (JOI14_factories)C++14
100 / 100
3364 ms404784 KiB
// author : anhtun_hi , nqg #include <bits/stdc++.h> #define ll long long #define ii pair<ll, ll> #define fi first #define se second #define all(x) x.begin(), x.end() #define reset(h, v) memset(h, v, sizeof h) #define Forv(i, a) for(auto& i : a) #define For(i, a, b) for(int i = a; i <= b; ++i) #define Ford(i, a, b) for(int i = a; i >= b; --i) #define c_bit(i) __builtin_popcountll(i) #define Bit(mask, i) ((mask >> i) & 1LL) #define onbit(mask, i) ((mask) bitor (1LL << i)) #define offbit(mask, i) ((mask) &~ (1LL << i)) using namespace std; namespace std { template <typename T, int D> struct _vector : public vector <_vector <T, D - 1>> { static_assert(D >= 1, "Dimension must be positive!"); template <typename... Args> _vector(int n = 0, Args... args) : vector <_vector <T, D - 1>> (n, _vector <T, D - 1> (args...)) {} }; template <typename T> struct _vector <T, 1> : public vector <T> { _vector(int n = 0, const T& val = T()) : vector <T> (n, val) {} }; template <class A, class B> bool minimize(A &a, B b){return a > b ? a = b, true : false;} template <class A, class B> bool maximize(A &a, B b){return a < b ? a = b, true : false;} } const int dx[] = {0, 0, +1, -1}, dy[] = {-1, +1, 0, 0}, LOG = 20, base = 311, inf = 1e9 + 5; const int MAXN = 1e6 + 5; const ll mod = 1e9 + 7; const ll oo = 1e18; //#define int long long int sz[MAXN], p[MAXN]; bool del[MAXN]; ll d[MAXN]; vector<ii> g[MAXN]; void dfsSize(int u, int par) { sz[u] = 1; for(auto [v, w] : g[u]) if((v ^ par) && !del[v]){ dfsSize(v, u); sz[u] += sz[v]; } } int find(int u, int par, int n) { for(auto [v, w] : g[u])if(v ^ par){ if(sz[v] > n / 2 && !del[v]) return find(v, u, n); } return u; } vector<ii> List[MAXN]; void prepare(int u, int par, ll len, int root) { List[u].push_back({root, len}); for(auto [v, w] : g[u]) if(v != par && !del[v]) prepare(v, u, len + w, root); } void buildCentroid(int u, int par) { dfsSize(u, par); int c = find(u, par, sz[u]); del[c] = true; p[c] = par; prepare(c, 0, 0, c); for(auto [v, _] : g[c]) if((v ^ par) && !del[v]) { buildCentroid(v, c); } } long long Query(int S, int X[], int T, int Y[]){ // cin >> S;cin >> T; // For(i, 0, S - 1) cin >> X[i];For(i, 0, T - 1) cin >> Y[i]; For(i, 0, S - 1){ for(auto [par, w] : List[X[i] + 1]) minimize(d[par], w); } ll ans = oo; For(i, 0, T - 1){ int u = Y[i] + 1; for(auto [par, w] : List[u]){ minimize(ans, d[par] + w); } } For(i, 0, S - 1){ for(auto [par, w] : List[X[i] + 1]) d[par] = oo; } return ans; } int n, a[MAXN], b[MAXN], w[MAXN], S, T, x[MAXN], y[MAXN]; void Init(int n, int a[], int b[], int w[]){ // cin >> n; // int q; cin >> q; // For(i, 0, n - 2) { // cin >> a[i] >> b[i] >> w[i]; // } For(i, 0, n - 2){ ++a[i], ++b[i]; g[a[i]].push_back({b[i], w[i]}); g[b[i]].push_back({a[i], w[i]}); } For(i, 0, n + 5) d[i] = oo; buildCentroid(1, 0); // while(q--){ // cout << Query(S, x, T, y) << '\n'; // } } //void Solve() { // Init(n, a, b, w); //} // //int32_t main() { // cin.tie(0) -> sync_with_stdio(0); // if(fopen("JOI14_factories.inp", "r")) { // freopen("JOI14_factories.inp", "r", stdin); // freopen("JOI14_factories.out", "w", stdout); // } // // int t = 1; //// cin >> t; // // for (int test = 1; test <= t; test++) { // Solve(); // } // return 0; //}

Compilation message (stderr)

factories.cpp: In function 'void dfsSize(int, int)':
factories.cpp:43:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   43 |     for(auto [v, w] : g[u]) if((v ^ par) && !del[v]){
      |              ^
factories.cpp: In function 'int find(int, int, int)':
factories.cpp:51:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   51 |     for(auto [v, w] : g[u])if(v ^ par){
      |              ^
factories.cpp: In function 'void prepare(int, int, long long int, int)':
factories.cpp:62:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   62 |     for(auto [v, w] : g[u]) if(v != par && !del[v]) prepare(v, u, len + w, root);
      |              ^
factories.cpp: In function 'void buildCentroid(int, int)':
factories.cpp:72:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   72 |     for(auto [v, _] : g[c]) if((v ^ par) && !del[v]) {
      |              ^
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:83:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   83 |         for(auto [par, w] : List[X[i] + 1]) minimize(d[par], w);
      |                  ^
factories.cpp:88:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   88 |         for(auto [par, w] : List[u]){
      |                  ^
factories.cpp:93:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   93 |         for(auto [par, w] : List[X[i] + 1]) d[par] = oo;
      |                  ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...