oj.uz

Submission #171003

# Submission time Handle Problem Language Result Execution time Memory
171003 2019-12-27T02:12:06 Z errorgorn Factories (JOI14_factories) C++14
100 / 100
 6330 ms 135188 KB 
#include "factories.h"
#include <cstdio>
#include <utility>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int,long long> ii;

vector<ii> al[500005];
long long w[500005],_w[500005];
int decomp[500005][20],r[500005];
bool target[500005];
priority_queue<ii, vector<ii>, greater<ii> > pq;

void dfs(int i){
    for (vector<ii>::iterator it=al[i].begin();it!=al[i].end();it++){
        if (w[(*it).first]==-1){
            w[(*it).first]=w[i]+(*it).second;
            r[(*it).first]=r[i]+1;

            //2k decomp shit here
            decomp[(*it).first][0]=i;
            int x=i,y=0;
            while (decomp[x][y]!=-1){
                decomp[(*it).first][y+1]=decomp[x][y];
                x=decomp[(*it).first][++y];
            }

            dfs((*it).first);
        }
    }
}

int move(int i,int j){
    int k;
    while (j!=0){
        k=j&-j;
        j-=k;
        i=decomp[i][__builtin_ctz(k)];
    }
    return i;
}

int lca(int i,int j){
    if (r[i]<r[j]) swap(i,j);
    //i is now a lower or equal rank to j
    //now we bring i up
    i=move(i,r[i]-r[j]);
    if (i==j) return i;
    for (int x=19;x>=0;x--){
        if (decomp[i][x]==-1 || decomp[i][x]==decomp[j][x]) continue;
        i=decomp[i][x];
        j=decomp[j][x];
    }
    return decomp[i][0];
}

long long dist(int i,int j){
    return w[i]+w[j]-(w[lca(i,j)]<<1);
}

void Init(int N, int A[], int B[], int D[]) {
    N--;
    for (int x=0;x<N;x++){
        al[A[x]].push_back(ii (B[x],D[x]));
        al[B[x]].push_back(ii (A[x],D[x]));
    }
    memset(w,-1,sizeof(w));
    memset(decomp,-1,sizeof(decomp));
    w[0]=0;
    dfs(0);
    /*for (int x=0;x<=N;x++){
        for (int y=0;y<=N;y++){
            printf("%d ",dist(x,y));
        }
        printf("\n");
    }*/
}

long long Query(int S, int X[], int T, int Y[]) {
    if ((long long)S*(long long)T<10000){ //binary search on this number because im lazy
    long long ans=1000000000000000000;
      for (int x=0;x<S;x++){
        for (int y=0;y<T;y++){
            ans=min(ans,dist(X[x],Y[y]));
        }
      }
      return ans;
    }
    else{
        while (!pq.empty()) pq.pop();
        memset(_w,-1,sizeof(_w));
        memset(target,false,sizeof(target));
        for (int x=0;x<T;x++){
            target[Y[x]]=true;
        }
        for (int x=0;x<S;x++){
            _w[X[x]]=0;
            pq.push(ii(0,X[x]));
        }
        long long i,j;
        while (true){
            j=pq.top().first,i=pq.top().second,pq.pop();
            if (target[i]) return j;
            if (_w[i]<j) continue;
            for (vector<ii>::iterator it=al[i].begin();it!=al[i].end();it++){
                if (_w[(*it).first]==-1||_w[(*it).first]>_w[i]+(*it).second){
                    _w[(*it).first]=_w[i]+(*it).second;
                    pq.push(ii (_w[(*it).first],(*it).first));
                }
            }
        }
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 55672 KB Output is correct
2 Correct 953 ms 77548 KB Output is correct
3 Correct 1828 ms 77560 KB Output is correct
4 Correct 859 ms 77560 KB Output is correct
5 Correct 979 ms 77688 KB Output is correct
6 Correct 1358 ms 77788 KB Output is correct
7 Correct 1818 ms 77488 KB Output is correct
8 Correct 621 ms 77424 KB Output is correct
9 Correct 963 ms 77596 KB Output is correct
10 Correct 1342 ms 77632 KB Output is correct
11 Correct 1852 ms 77420 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 55288 KB Output is correct
2 Correct 1767 ms 114404 KB Output is correct
3 Correct 3295 ms 105492 KB Output is correct
4 Correct 901 ms 111836 KB Output is correct
5 Correct 3066 ms 135188 KB Output is correct
6 Correct 2885 ms 117824 KB Output is correct
7 Correct 4614 ms 85652 KB Output is correct
8 Correct 967 ms 85776 KB Output is correct
9 Correct 3759 ms 89208 KB Output is correct
10 Correct 3104 ms 87064 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 55672 KB Output is correct
2 Correct 953 ms 77548 KB Output is correct
3 Correct 1828 ms 77560 KB Output is correct
4 Correct 859 ms 77560 KB Output is correct
5 Correct 979 ms 77688 KB Output is correct
6 Correct 1358 ms 77788 KB Output is correct
7 Correct 1818 ms 77488 KB Output is correct
8 Correct 621 ms 77424 KB Output is correct
9 Correct 963 ms 77596 KB Output is correct
10 Correct 1342 ms 77632 KB Output is correct
11 Correct 1852 ms 77420 KB Output is correct
12 Correct 50 ms 55288 KB Output is correct
13 Correct 1767 ms 114404 KB Output is correct
14 Correct 3295 ms 105492 KB Output is correct
15 Correct 901 ms 111836 KB Output is correct
16 Correct 3066 ms 135188 KB Output is correct
17 Correct 2885 ms 117824 KB Output is correct
18 Correct 4614 ms 85652 KB Output is correct
19 Correct 967 ms 85776 KB Output is correct
20 Correct 3759 ms 89208 KB Output is correct
21 Correct 3104 ms 87064 KB Output is correct
22 Correct 1832 ms 108032 KB Output is correct
23 Correct 2311 ms 110948 KB Output is correct
24 Correct 1991 ms 110892 KB Output is correct
25 Correct 2188 ms 113608 KB Output is correct
26 Correct 2320 ms 109080 KB Output is correct
27 Correct 2383 ms 126684 KB Output is correct
28 Correct 4698 ms 119248 KB Output is correct
29 Correct 4556 ms 110808 KB Output is correct
30 Correct 5445 ms 110328 KB Output is correct
31 Correct 6330 ms 117548 KB Output is correct
32 Correct 1146 ms 94188 KB Output is correct
33 Correct 1126 ms 92188 KB Output is correct
34 Correct 1323 ms 87944 KB Output is correct
35 Correct 1354 ms 87876 KB Output is correct
36 Correct 1466 ms 88312 KB Output is correct
37 Correct 1655 ms 88440 KB Output is correct