oj.uz

Submission #167543

# Submission time Handle Problem Language Result Execution time Memory
167543 2019-12-08T21:38:42 Z dessertion Factories (JOI14_factories) C++14
100 / 100
 6833 ms 261200 KB 
#pragma GCC optimize "O3"
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#define pb_ push_back
#define eb_ emplace_back
#define mp_ make_pair
//#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef pair<long,long> pll;
typedef pair<int,int> pii;

const int MN = 5e5+10,LVL=21;
const ll INF = 0x3f3f3f3f3f3f3f3f;
struct edge{
    int b,w;
};
vector<edge> adj[MN];
vector<int> adj2[MN];

int sz[MN],tree[MN],depth2[MN],parent[MN][LVL],touched[1000005],eid[MN],revid[MN],efirst[MN],id,cnt,last_touch;
int sparse[LVL][2*MN];
ll dist[MN],ans[MN];
bool done[MN];

int size(int u, int p){
    sz[u] = 1;
    for(auto e : adj[u]){
        if(e.b==p||done[e.b])continue;
        sz[u]+=size(e.b,u);
    }
    return sz[u];
}

int centroid(int u, int p, int tot){
    for(auto e:adj[u])if(e.b!=p&&!done[e.b]&&2*sz[e.b]>=tot)return centroid(e.b,u,tot);
    return u;
}

int decomp(int u, int last){
    int cent = centroid(u,-1,size(u,-1));
    tree[cent]=last;
    done[cent]=1;
    for(auto e : adj[cent]){
        if(done[e.b])continue;
        adj2[cent].pb_(decomp(e.b,cent));
    }
    return cent;
}

void Init(int n, int a[], int b[], int d[]){
    for(int i = 0 ;i < n-1; i++){
        adj[a[i]].pb_({b[i],d[i]});
        adj[b[i]].pb_({a[i],d[i]});
    }
    memset(sparse,0x3f,sizeof(sparse));
    decomp(0,-1);
    function<void(int,int)> dfs = [&](int u, int p){
        eid[u]=++id;
        revid[id]=u;
        efirst[id]=++cnt;
        sparse[0][cnt]=id;
        
        parent[u][0]=p;
        for(auto e : adj[u]){
            if(e.b==p)continue;
            dist[e.b]=e.w+dist[u],depth2[e.b]=depth2[u]+1,dfs(e.b,u);
            sparse[0][++cnt]=eid[u];
        }
    };
    dfs(0,-1);
    for(int i = 1; i < LVL ; i++){
        for(int j = 0; j < n; j++){
            parent[j][i] = parent[parent[j][i-1]][i-1];
        }
    }
    
    /*
    cout<<"SPARSE:\n";
    for(int i = 1; i <= 2*n; i++){
        cout<<sparse[0][i]<<" \n"[i==2*n];
    }
    */
    for(int i = 1; i <= 31-__builtin_clz(2*n); i++){
        for(int j = 1; j +(1<<i)<=2*n; j++){
            sparse[i][j] = min(sparse[i-1][j],sparse[i-1][j+(1<<(i-1))]);
            // cout<<sparse[i][j]<<" \n"[j+(1<<i)==2*n];
        }
    }
    
    memset(ans,0x3f,sizeof(ans));
}

ll getDist(int u, int v){
    /*function<int(int,int)> lca = [&](int a, int b){
        if(depth2[a]>depth2[b])swap(a,b);
        int diff = depth2[b]-depth2[a];
        for(int i =0 ; i < LVL; i++)if((diff>>i)&1)b=parent[b][i];
        if(b==a)return a;
        
        for(int i = LVL-1; i>=0; i--){
            if(parent[a][i]!=parent[b][i])a=parent[a][i],b=parent[b][i];
        }
        return parent[a][0];
    };*/
    function<int(int,int)> lca = [&](int a, int b){
        a=efirst[eid[a]],b=efirst[eid[b]];
        if(a>b)swap(a,b);
        int diff = b-a;
        int lg = 31-__builtin_clz(diff);
        int ret = min(sparse[lg][a],sparse[lg][b-(1<<lg)+1]);
        return revid[ret];
    };
    
    
    int anc = lca(u,v);
    return abs(dist[u]-dist[anc])+abs(dist[v]-dist[anc]);
}

long long Query(int s, int x[], int t, int y[]){
    for(int i = 0 ; i < s ; i++){
        for(int v = x[i]; v!=-1; v=tree[v]){
            ans[v] = min(ans[v],getDist(x[i],v));
            touched[last_touch++]=v;
        }
    }
    ll ret = INF;
    for(int i = 0; i < t; i ++){
        for(int v = y[i]; v!=-1; v=tree[v]){
            ret=min(ret,getDist(v,y[i])+ans[v]);
        }
    }
    for(int i = last_touch-1;i>=0; i--)ans[touched[i]]=INF;
    last_touch=0;
    
    return ret;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 110584 KB Output is correct
2 Correct 618 ms 128504 KB Output is correct
3 Correct 726 ms 128632 KB Output is correct
4 Correct 735 ms 128508 KB Output is correct
5 Correct 829 ms 128924 KB Output is correct
6 Correct 427 ms 128376 KB Output is correct
7 Correct 721 ms 128504 KB Output is correct
8 Correct 743 ms 128376 KB Output is correct
9 Correct 820 ms 128852 KB Output is correct
10 Correct 424 ms 128372 KB Output is correct
11 Correct 728 ms 128604 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 110376 KB Output is correct
2 Correct 2855 ms 224464 KB Output is correct
3 Correct 3312 ms 226264 KB Output is correct
4 Correct 1219 ms 221788 KB Output is correct
5 Correct 5084 ms 256212 KB Output is correct
6 Correct 3514 ms 217188 KB Output is correct
7 Correct 1744 ms 146684 KB Output is correct
8 Correct 650 ms 151780 KB Output is correct
9 Correct 1958 ms 156664 KB Output is correct
10 Correct 1843 ms 153228 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 110584 KB Output is correct
2 Correct 618 ms 128504 KB Output is correct
3 Correct 726 ms 128632 KB Output is correct
4 Correct 735 ms 128508 KB Output is correct
5 Correct 829 ms 128924 KB Output is correct
6 Correct 427 ms 128376 KB Output is correct
7 Correct 721 ms 128504 KB Output is correct
8 Correct 743 ms 128376 KB Output is correct
9 Correct 820 ms 128852 KB Output is correct
10 Correct 424 ms 128372 KB Output is correct
11 Correct 728 ms 128604 KB Output is correct
12 Correct 107 ms 110376 KB Output is correct
13 Correct 2855 ms 224464 KB Output is correct
14 Correct 3312 ms 226264 KB Output is correct
15 Correct 1219 ms 221788 KB Output is correct
16 Correct 5084 ms 256212 KB Output is correct
17 Correct 3514 ms 217188 KB Output is correct
18 Correct 1744 ms 146684 KB Output is correct
19 Correct 650 ms 151780 KB Output is correct
20 Correct 1958 ms 156664 KB Output is correct
21 Correct 1843 ms 153228 KB Output is correct
22 Correct 3779 ms 227420 KB Output is correct
23 Correct 3706 ms 237692 KB Output is correct
24 Correct 5039 ms 236344 KB Output is correct
25 Correct 5430 ms 239672 KB Output is correct
26 Correct 5088 ms 234632 KB Output is correct
27 Correct 6833 ms 261200 KB Output is correct
28 Correct 1732 ms 231436 KB Output is correct
29 Correct 5276 ms 233792 KB Output is correct
30 Correct 5107 ms 233152 KB Output is correct
31 Correct 5130 ms 234404 KB Output is correct
32 Correct 2091 ms 159620 KB Output is correct
33 Correct 662 ms 152668 KB Output is correct
34 Correct 1361 ms 149288 KB Output is correct
35 Correct 1305 ms 149396 KB Output is correct
36 Correct 1721 ms 150160 KB Output is correct
37 Correct 1900 ms 150212 KB Output is correct