답안 #57696 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
57696	2018-07-15T20:35:25 Z	Benq	공장들 (JOI14_factories)	C++14	100 / 100	7355 ms	275212 KB

factories

#include "factories.h"
 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
 
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
 
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
 
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
 
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
 
const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 500005;
 
 
template<int SZ> struct centroidDecomp {
    int N;
    bool done[SZ];
    int sub[SZ], par[SZ], cen[SZ];
    ll ans[SZ];
    ll dist[SZ][20], tmp[SZ];
    vpi adj[SZ];
    
    // INITIALIZE
    
    void addEdge(int a, int b, int d) { adj[a].pb({b,d}), adj[b].pb({a,d}); }
    
    void dfs (int no) {
        sub[no] = 1;
        for (pi i: adj[no]) if (!done[i.f] && i.f != par[no]) {
            par[i.f] = no;
            dfs(i.f);
            sub[no] += sub[i.f];
        }
    }
    
    void genDist(int par, int no, int t, ll dis) {
        dist[no][tmp[no]++] = dis;
        for (pi i: adj[no]) if (!done[i.f] && i.f != par) {
            cen[i.f] = t;
            genDist(no,i.f,t,dis+i.s);
        }
    }
    
    int getCentroid(int x) {
        par[x] = -1; dfs(x);
        int sz = sub[x];
        while (1) {
            pi mx = {0,0};
            for (pi i: adj[x]) if (!done[i.f] && i.f != par[x]) mx = max(mx,{sub[i.f],i.f});
            if (mx.f*2 > sz) x = mx.s;
            else return x;
        }
    }
    
    void solve (int x) {
        x = getCentroid(x); done[x] = 1;
        genDist(-1,x,x,0);
        for (pi i: adj[x]) if (!done[i.f]) solve(i.f);
    }
    
    void init() {
        F0R(i,N) cen[i] = -1, ans[i] = INF;
        solve(0);
    }
    
    // QUERY 
    
    void upd(int v, int x = 1) {
        for (int V = v, ind = tmp[v]-1; V >= 0; V = cen[V], ind --) {
            // cout << "OH " << v << " " << V << " " << x << "\n";
            if (x == 1) ans[V] = min(ans[V],dist[v][ind]);
            else ans[V] = INF;
        }
    }
    
    ll query(int v) {
        ll ret = INF;
        for (int V = v, ind = tmp[v]-1; V >= 0; V = cen[V], ind --) {
            // cout << "AH " << V << " " << v << "\n";
            ret = min(ret,ans[V]+dist[v][ind]);
        }
        return ret;
    }
};
 
centroidDecomp<MX> C;
 
void Init(int N, int A[], int B[], int D[]) {
    C.N = N;
    F0R(i,N-1) C.addEdge(A[i],B[i],D[i]);
    C.init();
}
 
long long Query(int S, int X[], int T, int Y[]) {
    ll ans = INF;
    if (S > T) {
        swap(S,T);
        swap(X,Y);
    }
    F0R(i,S) C.upd(X[i]);
    F0R(i,T) ans = min(ans,C.query(Y[i]));
    F0R(i,S) C.upd(X[i],-1);
    return ans;
}

Subtask #1
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	19 ms	12536 KB	Output is correct
2	Correct	367 ms	21360 KB	Output is correct
3	Correct	422 ms	27928 KB	Output is correct
4	Correct	370 ms	28036 KB	Output is correct
5	Correct	474 ms	28168 KB	Output is correct
6	Correct	335 ms	28168 KB	Output is correct
7	Correct	451 ms	28168 KB	Output is correct
8	Correct	445 ms	28168 KB	Output is correct
9	Correct	497 ms	28288 KB	Output is correct
10	Correct	347 ms	28288 KB	Output is correct
11	Correct	442 ms	28288 KB	Output is correct

Subtask #2
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	20 ms	28288 KB	Output is correct
2	Correct	3222 ms	143164 KB	Output is correct
3	Correct	4615 ms	143412 KB	Output is correct
4	Correct	1368 ms	160116 KB	Output is correct
5	Correct	6545 ms	178128 KB	Output is correct
6	Correct	4727 ms	178128 KB	Output is correct
7	Correct	1382 ms	178128 KB	Output is correct
8	Correct	653 ms	178128 KB	Output is correct
9	Correct	1753 ms	178128 KB	Output is correct
10	Correct	1215 ms	178128 KB	Output is correct

Subtask #3
67.0 / 67.0

#	결과	실행 시간	메모리	Grader output
1	Correct	19 ms	12536 KB	Output is correct
2	Correct	367 ms	21360 KB	Output is correct
3	Correct	422 ms	27928 KB	Output is correct
4	Correct	370 ms	28036 KB	Output is correct
5	Correct	474 ms	28168 KB	Output is correct
6	Correct	335 ms	28168 KB	Output is correct
7	Correct	451 ms	28168 KB	Output is correct
8	Correct	445 ms	28168 KB	Output is correct
9	Correct	497 ms	28288 KB	Output is correct
10	Correct	347 ms	28288 KB	Output is correct
11	Correct	442 ms	28288 KB	Output is correct
12	Correct	20 ms	28288 KB	Output is correct
13	Correct	3222 ms	143164 KB	Output is correct
14	Correct	4615 ms	143412 KB	Output is correct
15	Correct	1368 ms	160116 KB	Output is correct
16	Correct	6545 ms	178128 KB	Output is correct
17	Correct	4727 ms	178128 KB	Output is correct
18	Correct	1382 ms	178128 KB	Output is correct
19	Correct	653 ms	178128 KB	Output is correct
20	Correct	1753 ms	178128 KB	Output is correct
21	Correct	1215 ms	178128 KB	Output is correct
22	Correct	3698 ms	178128 KB	Output is correct
23	Correct	4374 ms	178664 KB	Output is correct
24	Correct	6144 ms	178664 KB	Output is correct
25	Correct	5630 ms	180816 KB	Output is correct
26	Correct	6124 ms	180816 KB	Output is correct
27	Correct	7355 ms	191804 KB	Output is correct
28	Correct	1797 ms	204256 KB	Output is correct
29	Correct	5974 ms	226512 KB	Output is correct
30	Correct	5781 ms	250460 KB	Output is correct
31	Correct	6449 ms	275212 KB	Output is correct
32	Correct	1828 ms	275212 KB	Output is correct
33	Correct	642 ms	275212 KB	Output is correct
34	Correct	1095 ms	275212 KB	Output is correct
35	Correct	1334 ms	275212 KB	Output is correct
36	Correct	1623 ms	275212 KB	Output is correct
37	Correct	1762 ms	275212 KB	Output is correct

답안 #57696

Compilation message

Subtask #1 15.0 / 15.0

Subtask #2 18.0 / 18.0

Subtask #3 67.0 / 67.0

Subtask #1
15.0 / 15.0

Subtask #2
18.0 / 18.0

Subtask #3
67.0 / 67.0