oj.uz

Submission #153973

# Submission time Handle Problem Language Result Execution time Memory
153973 2019-09-17T15:42:16 Z Mercenary Factories (JOI14_factories) C++14
100 / 100
 7870 ms 315872 KB 
#include "factories.h"
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair

using namespace std;
const int maxn = 5e5 + 5;
const int logn = log2(maxn) + 1;
typedef pair<int,int> ii;
typedef long long ll;

int big[maxn] , vis[maxn] , n , sub[maxn];
ll dep[maxn] , cen[maxn];

vector<int> v[maxn];
vector<ii> adj[maxn];
vector<ll> predis[maxn];

void DFS(int u , int v){
    sub[u] = 1;
    big[u] = -1;
    for(auto& c : adj[u]){
        if(c.first != v && vis[c.first] == 0){
            DFS(c.first , u);
            sub[u] += sub[c.first];
            if(big[u] == -1 || sub[big[u]] < sub[c.first])big[u] = c.first;
        }
    }
}

int FindRoot(int u){
    DFS(u , -1);
    int total = sub[u];
    while(big[u] != -1 && sub[big[u]] * 2 >= total)u = big[u];
    return u;
}

void Decompose(int u){
    u = FindRoot(u);
    vis[u] = 1;
    function<void(int,int,ll dep)> DFS = [&](int uu , int v , ll dep){
        ::v[uu].pb(u);
        predis[uu].pb(dep);
        for(ii c : adj[uu]){
            if(c.first != v && vis[c.first] == 0){
                DFS(c.first , uu , dep + c.second);
            }
        }
    };
    DFS(u , -1 , 0);
    for(auto& c : adj[u]){
        if(vis[c.first] == 0){
            Decompose(c.first);
        }
    }
}

void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for(int i = 0 ; i < n - 1 ; ++i){
        adj[A[i]].pb(mp(B[i] , D[i]));
        adj[B[i]].pb(mp(A[i] , D[i]));
    }
    Decompose(0);
    for(int i = 0 ; i < n ; ++i)cen[i] = 1e18;
}

long long Query(int S, int X[], int T, int Y[]) {
    ll total = 1e18;
    for(int i = 0 ; i < S ; ++i){
        for(int j = (int)v[X[i]].size() -1; j >= 0 ; --j){
            cen[v[X[i]][j]] = min(cen[v[X[i]][j]] , predis[X[i]][j]);
        }
    }
    for(int i = 0 ; i < T ; ++i){
        ll res = 1e18;
        for(int j = (int)v[Y[i]].size() -1; j >= 0 ; --j){
             res = min(res , predis[Y[i]][j] + cen[v[Y[i]][j]]);
        }
        total = min(total , res);
    }
    for(int i = 0 ; i < S ; ++i){
        for(int c : v[X[i]]){
            cen[c] = 1e18;
        }
    }
    return total;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 36188 KB Output is correct
2 Correct 494 ms 49528 KB Output is correct
3 Correct 503 ms 49968 KB Output is correct
4 Correct 506 ms 50072 KB Output is correct
5 Correct 541 ms 50424 KB Output is correct
6 Correct 398 ms 49608 KB Output is correct
7 Correct 501 ms 50576 KB Output is correct
8 Correct 499 ms 50528 KB Output is correct
9 Correct 549 ms 51352 KB Output is correct
10 Correct 409 ms 50784 KB Output is correct
11 Correct 496 ms 51848 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 35832 KB Output is correct
2 Correct 3762 ms 180664 KB Output is correct
3 Correct 6103 ms 232284 KB Output is correct
4 Correct 1473 ms 109132 KB Output is correct
5 Correct 7372 ms 288252 KB Output is correct
6 Correct 5925 ms 251440 KB Output is correct
7 Correct 1633 ms 88024 KB Output is correct
8 Correct 813 ms 73080 KB Output is correct
9 Correct 1805 ms 98884 KB Output is correct
10 Correct 1708 ms 89328 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 36188 KB Output is correct
2 Correct 494 ms 49528 KB Output is correct
3 Correct 503 ms 49968 KB Output is correct
4 Correct 506 ms 50072 KB Output is correct
5 Correct 541 ms 50424 KB Output is correct
6 Correct 398 ms 49608 KB Output is correct
7 Correct 501 ms 50576 KB Output is correct
8 Correct 499 ms 50528 KB Output is correct
9 Correct 549 ms 51352 KB Output is correct
10 Correct 409 ms 50784 KB Output is correct
11 Correct 496 ms 51848 KB Output is correct
12 Correct 38 ms 35832 KB Output is correct
13 Correct 3762 ms 180664 KB Output is correct
14 Correct 6103 ms 232284 KB Output is correct
15 Correct 1473 ms 109132 KB Output is correct
16 Correct 7372 ms 288252 KB Output is correct
17 Correct 5925 ms 251440 KB Output is correct
18 Correct 1633 ms 88024 KB Output is correct
19 Correct 813 ms 73080 KB Output is correct
20 Correct 1805 ms 98884 KB Output is correct
21 Correct 1708 ms 89328 KB Output is correct
22 Correct 4869 ms 204732 KB Output is correct
23 Correct 4786 ms 209160 KB Output is correct
24 Correct 6724 ms 258052 KB Output is correct
25 Correct 7264 ms 261912 KB Output is correct
26 Correct 6965 ms 258256 KB Output is correct
27 Correct 7870 ms 315872 KB Output is correct
28 Correct 1911 ms 137524 KB Output is correct
29 Correct 6809 ms 257824 KB Output is correct
30 Correct 7248 ms 258572 KB Output is correct
31 Correct 6549 ms 258436 KB Output is correct
32 Correct 2134 ms 99344 KB Output is correct
33 Correct 882 ms 73636 KB Output is correct
34 Correct 1289 ms 82768 KB Output is correct
35 Correct 1304 ms 83224 KB Output is correct
36 Correct 1626 ms 86264 KB Output is correct
37 Correct 1763 ms 86496 KB Output is correct