Submission #90844

#	Time	Username	Problem	Language	Result	Execution time	Memory
90844		liwi	Factories (JOI14_factories)	C++11	33 / 100	5667 ms	525312 KiB

factories

#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;
    getSz(node,-1,0);
    done[node] = true;
    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);
}

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

//    scanf(" %d %d",&num_nodes,&num_q);
//    for(int i=0; i<num_nodes-1; i++)
//        scanf(" %d %d %d",&A[i],&B[i],&D[i]);
//    Init(num_nodes,A,B,D);
//    for(int i=0; i<num_q; i++){
//        int s1,s2; scanf(" %d %d",&s1,&s2);
//        int first[MAXN],second[MAXN];
//        for(int k=0; k<s1; k++) scanf(" %d",&first[k]);
//        for(int k=0; k<s2; k++) scanf(" %d",&second[k]);
//        printf("%lld\n",Query(s1,first,s2,second));
//    }

/*
8 1
0 1 3
1 2 2
2 3 7
2 4 1
0 5 5
5 7 4
5 6 2
2 2
2 6
7 3

10 1
0 1 8
1 2 3
1 3 1
0 4 7
4 5 9
4 6 2
0 7 2
7 8 4
7 9 3
1 3
0
1 3 4
*/

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 0 / 67