oj.uz

Submission #90846

# Submission time Handle Problem Language Result Execution time Memory
90846 2018-12-24T19:52:34 Z liwi Factories (JOI14_factories) C++11
100 / 100
 5557 ms 159756 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
typedef tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;

#define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
char _;
#define println printf("\n");
#define readln(x) getline(cin,x);
#define pb push_back
#define endl "\n"
#define MOD 1000000007
#define mp make_pair

#define MAXN 500005
#define LOGN 25

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef unordered_map<int,int> umii;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,pii> triple;
typedef int8_t byte;

ll gcd(ll a, ll b) {return b == 0 ? a : gcd(b, a % b);}
ll fpow(ll  b, ll exp, ll mod){if(exp == 0) return 1;ll t = fpow(b,exp/2,mod);if(exp&1) return t*t%mod*b%mod;return t*t%mod;}
ll divmod(ll i, ll j, ll mod){i%=mod,j%=mod;return i*fpow(j,mod-2,mod)%mod;}

int num_nodes,num_q,sz[MAXN],lvl[MAXN],par[MAXN],upd[MAXN],qcnt,A[MAXN],B[MAXN],D[MAXN],cur_lvl;
ll small[MAXN],dis[LOGN][MAXN];
bool done[MAXN];
vector<pii> tconnections[MAXN];

int getSz(int node, int prev, ll dd){
    sz[node] = 1;
    dis[cur_lvl][node] = dd;
    for(pii check:tconnections[node]){
        if(check.first == prev || done[check.first]) continue;
        sz[node]+=getSz(check.first,node,dd+check.second);
    }
    return sz[node];
}

int centroid(int node, int prev, int mx){
    for(pii check:tconnections[node]){
        if(check.first == prev || done[check.first]) continue;
        if(sz[check.first]<<1 > mx)
            return centroid(check.first,node,mx);
    }
    return node;
}

void getTree(int node, int prev, int mx, int lv){
    cur_lvl = lv;
    getSz(node,-1,0);
    node = centroid(node,-1,mx);
    par[node] = prev, lvl[node] = lv, done[node] = true;
    getSz(node,-1,0);
    for(pii check:tconnections[node]){
        if(check.first == prev || done[check.first]) continue;
        getTree(check.first,node,sz[check.first],lv+1);
    }
}

void Init(int N, int A[MAXN], int B[MAXN], int D[MAXN]){
    num_nodes = N;
    for(int i=0; i<N-1; i++){
        int a = A[i], b = B[i], dis = D[i];
        tconnections[a].pb(mp(b,dis));
        tconnections[b].pb(mp(a,dis));
    }
    getTree(0,-1,num_nodes,0);
    memset(small,0x3f,sizeof small);
}

ll Query(int s1, int X[MAXN], int s2, int Y[MAXN]){
    for(int i=0; i<s1; i++){
        int current = X[i];
        while(current != -1){
            small[current] = min(small[current],dis[lvl[current]][X[i]]);
            current = par[current];
        }
    }
    ll best = LONG_MAX;
    for(int i=0; i<s2; i++){
        int current = Y[i];
        while(current != -1){
            best = min(best,dis[lvl[current]][Y[i]]+small[current]);
            current = par[current];
        }
    }
    for(int i=0; i<s1; i++){
        int current = X[i];
        while(current != -1){
            small[current] = 0x3f3f3f3f3f3f3f3f;
            current = par[current];
        }
    }
    return best;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 16632 KB Output is correct
2 Correct 306 ms 29944 KB Output is correct
3 Correct 335 ms 29964 KB Output is correct
4 Correct 332 ms 30080 KB Output is correct
5 Correct 361 ms 30228 KB Output is correct
6 Correct 241 ms 30228 KB Output is correct
7 Correct 341 ms 32164 KB Output is correct
8 Correct 344 ms 32164 KB Output is correct
9 Correct 367 ms 32488 KB Output is correct
10 Correct 237 ms 32488 KB Output is correct
11 Correct 339 ms 32488 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 32488 KB Output is correct
2 Correct 2725 ms 120160 KB Output is correct
3 Correct 4270 ms 137368 KB Output is correct
4 Correct 932 ms 137368 KB Output is correct
5 Correct 5557 ms 159756 KB Output is correct
6 Correct 4351 ms 159756 KB Output is correct
7 Correct 1124 ms 159756 KB Output is correct
8 Correct 379 ms 159756 KB Output is correct
9 Correct 1431 ms 159756 KB Output is correct
10 Correct 1116 ms 159756 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 16632 KB Output is correct
2 Correct 306 ms 29944 KB Output is correct
3 Correct 335 ms 29964 KB Output is correct
4 Correct 332 ms 30080 KB Output is correct
5 Correct 361 ms 30228 KB Output is correct
6 Correct 241 ms 30228 KB Output is correct
7 Correct 341 ms 32164 KB Output is correct
8 Correct 344 ms 32164 KB Output is correct
9 Correct 367 ms 32488 KB Output is correct
10 Correct 237 ms 32488 KB Output is correct
11 Correct 339 ms 32488 KB Output is correct
12 Correct 16 ms 32488 KB Output is correct
13 Correct 2725 ms 120160 KB Output is correct
14 Correct 4270 ms 137368 KB Output is correct
15 Correct 932 ms 137368 KB Output is correct
16 Correct 5557 ms 159756 KB Output is correct
17 Correct 4351 ms 159756 KB Output is correct
18 Correct 1124 ms 159756 KB Output is correct
19 Correct 379 ms 159756 KB Output is correct
20 Correct 1431 ms 159756 KB Output is correct
21 Correct 1116 ms 159756 KB Output is correct
22 Correct 3186 ms 159756 KB Output is correct
23 Correct 3347 ms 159756 KB Output is correct
24 Correct 5008 ms 159756 KB Output is correct
25 Correct 5210 ms 159756 KB Output is correct
26 Correct 3823 ms 159756 KB Output is correct
27 Correct 5371 ms 159756 KB Output is correct
28 Correct 1138 ms 159756 KB Output is correct
29 Correct 5056 ms 159756 KB Output is correct
30 Correct 4975 ms 159756 KB Output is correct
31 Correct 5254 ms 159756 KB Output is correct
32 Correct 1402 ms 159756 KB Output is correct
33 Correct 380 ms 159756 KB Output is correct
34 Correct 805 ms 159756 KB Output is correct
35 Correct 800 ms 159756 KB Output is correct
36 Correct 1079 ms 159756 KB Output is correct
37 Correct 1103 ms 159756 KB Output is correct