oj.uz

Submission #945214

# Submission time Handle Problem Language Result Execution time Memory
945214 2024-03-13T14:26:17 Z VMaksimoski008 Factories (JOI14_factories) C++14
15 / 100
 7749 ms 524288 KB 
#include <bits/stdc++.h>
#include "factories.h"

using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

const int maxn = 5e5 + 5;

int n, del[maxn], sub[maxn];
ll dist[maxn];
vector<vector<pll> > graph(maxn), anc(maxn);

int get_sub(int u, int p) {
    for(auto &[v, _] : graph[u])
        if(v != p && !del[v]) sub[u] += get_sub(v, u);
    return ++sub[u];
}

int get_cen(int u, int p, int sz) {
    for(auto &[v, _] : graph[u])
        if(v != p && !del[v] && 2 * sub[v] > sz) return get_cen(v, u, sz);
    return u;
}

void get_dist(int u, int cen, int p, ll d) {
    for(auto &[v, w] : graph[u])
        if(v != p && !del[v]) get_dist(v, cen, u, d + w);
    anc[u].push_back({ cen, d });
}

void update(int u, int t) {
    for(auto &[v, d] : anc[u])
        dist[v] = (t ? min(dist[v], d) : 1e18);
    dist[u] = (t ? 0 : 1e18);
}

ll query(int u) {
    ll ans = dist[u];
    for(auto &[v, d] : anc[u]) ans = min(ans, d + dist[v]);
    return ans;
}

void build(int u) {
    int cen = get_cen(u, -1, get_sub(u, -1));

    for(auto &[v, w] : graph[cen])
        if(!del[v]) get_dist(v, cen, cen, w);

    del[cen] = 1;
    for(auto &[v, w] : graph[cen])
        if(!del[v]) build(v);
}

void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for(int i=0; i<n-1; i++) {
        graph[A[i]].push_back({ B[i], D[i] });
        graph[B[i]].push_back({ A[i], D[i] });
    }
    for(int i=0; i<n; i++) dist[i] = 1e18;
    build(0);
}

ll Query(int S, int X[], int T, int Y[]) {
    ll ans = 1e18;
    for(int i=0; i<S; i++) update(X[i], 1);
    for(int i=0; i<T; i++) ans = min(ans, query(Y[i]));
    for(int i=0; i<S; i++) update(X[i], 0);
    return ans;
}

Compilation message

factories.cpp: In function 'int get_sub(int, int)':
factories.cpp:15:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   15 |     for(auto &[v, _] : graph[u])
      |               ^
factories.cpp: In function 'int get_cen(int, int, int)':
factories.cpp:21:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   21 |     for(auto &[v, _] : graph[u])
      |               ^
factories.cpp: In function 'void get_dist(int, int, int, ll)':
factories.cpp:27:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   27 |     for(auto &[v, w] : graph[u])
      |               ^
factories.cpp: In function 'void update(int, int)':
factories.cpp:33:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   33 |     for(auto &[v, d] : anc[u])
      |               ^
factories.cpp: In function 'll query(int)':
factories.cpp:40:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   40 |     for(auto &[v, d] : anc[u]) ans = min(ans, d + dist[v]);
      |               ^
factories.cpp: In function 'void build(int)':
factories.cpp:47:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   47 |     for(auto &[v, w] : graph[cen])
      |               ^
factories.cpp:51:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   51 |     for(auto &[v, w] : graph[cen])
      |               ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 44636 KB Output is correct
2 Correct 208 ms 52712 KB Output is correct
3 Correct 395 ms 58104 KB Output is correct
4 Correct 415 ms 58544 KB Output is correct
5 Correct 762 ms 66900 KB Output is correct
6 Correct 146 ms 51852 KB Output is correct
7 Correct 372 ms 57608 KB Output is correct
8 Correct 369 ms 57468 KB Output is correct
9 Correct 718 ms 67340 KB Output is correct
10 Correct 148 ms 51712 KB Output is correct
11 Correct 370 ms 57756 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 44380 KB Output is correct
2 Correct 2013 ms 222512 KB Output is correct
3 Runtime error 7749 ms 524288 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 44636 KB Output is correct
2 Correct 208 ms 52712 KB Output is correct
3 Correct 395 ms 58104 KB Output is correct
4 Correct 415 ms 58544 KB Output is correct
5 Correct 762 ms 66900 KB Output is correct
6 Correct 146 ms 51852 KB Output is correct
7 Correct 372 ms 57608 KB Output is correct
8 Correct 369 ms 57468 KB Output is correct
9 Correct 718 ms 67340 KB Output is correct
10 Correct 148 ms 51712 KB Output is correct
11 Correct 370 ms 57756 KB Output is correct
12 Correct 10 ms 44380 KB Output is correct
13 Correct 2013 ms 222512 KB Output is correct
14 Runtime error 7749 ms 524288 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -