oj.uz

Submission #287408

# Submission time Handle Problem Language Result Execution time Memory
287408 2020-08-31T16:44:58 Z limabeans Factories (JOI14_factories) C++17
15 / 100
 8000 ms 148600 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl


using ll = long long;
const ll inf = 1e18;

const ll mod = 1e9+7;
const int maxn = 1e6+10;

vector<pair<ll,int>> g[maxn];
const int LOG = 14;
int par[LOG+1][maxn];
ll wei[LOG+1][maxn];
int dep[maxn];
int n;

void dfs(int at, int p) {
    if (~p) {
	for (int j=1; j<LOG; j++) {
	    par[j][at] = par[j-1][par[j-1][at]];
	    wei[j][at] = wei[j-1][at] + wei[j-1][par[j-1][at]];
	}
    }
    for (auto ed: g[at]) {
	int to = ed.second;
	if (to == p) continue;
	par[0][to] = at;
	wei[0][to] = ed.first;
	dep[to] = 1+dep[at];
	dfs(to, at);
    }
}

int lca(int u, int v) {
    if (dep[u]<dep[v]) swap(u, v);
    int dx = dep[u]-dep[v];

    for (int j=0; j<LOG; j++) {
	if (dx>>j&1) {
	    u=par[j][u];
	}
    }
    
    if (u==v) return v;

    for (int j=LOG-1; j>=0; j--) {
	if (par[j][u] != par[j][v]) {
	    u=par[j][u];
	    v=par[j][v];
	}
    }
    return par[0][v];
}


ll walk(ll at, ll to) {
    if (dep[at] < dep[to]) {
	swap(at, to);
    }
    ll res = 0;
    for (int j=LOG-1; j>=0 && at!=to; j--) {
	int up = par[j][at];
	if (dep[up]>=dep[to]) {
	    res += wei[j][at];
	    at=up;
	}
    }
    return res;    
}

ll dist(int u, int v) {
    if (u==v) return 0;
    int mid = lca(u,v);
    return walk(u,mid)+walk(v,mid);
}


void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for (int i=0; i<N; i++) {
	g[A[i]].push_back({D[i],B[i]});
	g[B[i]].push_back({D[i],A[i]});
    }

    dfs(0, -1);
}


ll dp[maxn];
bool dest[maxn];



ll QuerySmall(int S, int X[], int T, int Y[]) {
    ll res = inf;
    for (int i=0; i<S; i++) {
	for (int j=0; j<T; j++) {
	    //cout<<X[i]<<","<<Y[j]<<endl;
	    res = min(res, dist(X[i],Y[j]));
	}
    }
    return res;
}

long long Query(int S, int X[], int T, int Y[]) {

    if (S<=10 && T<=10) {
	return QuerySmall(S, X, T, Y);
    }
    
    for (int i=0; i<n; i++) {
	dp[i] = inf;
	dest[i] = false;
    }
    for (int i=0; i<S; i++) {
	dp[X[i]] = 0;
    }
    for (int i=0; i<T; i++) {
	dest[Y[i]] = true;
    }
    priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
    for (int i=0; i<S; i++) {
	pq.push({0, X[i]});
    }


    while (pq.size()) {
	auto cur = pq.top();
	pq.pop();
	int at = cur.second;
	ll len = cur.first;
	if (len > dp[at]) {
	    continue;
	}
	if (dest[at]) {
	    return len;
	}
	for (auto ed: g[at]) {
	    int to = ed.second;
	    ll wei = ed.first;
	    if (len+wei < dp[to]) {
		dp[to] = len+wei;
		pq.push({dp[to], to});
	    }
	}
    }

    ll res = inf;
    for (int i=0; i<T; i++) {
	res = min(res, dp[Y[i]]);
    }

    
    return res;
}

int q;
int a[maxn], b[maxn], d[maxn];
int x[maxn], y[maxn];

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 24568 KB Output is correct
2 Correct 518 ms 39940 KB Output is correct
3 Correct 515 ms 40440 KB Output is correct
4 Correct 503 ms 40464 KB Output is correct
5 Correct 466 ms 40824 KB Output is correct
6 Correct 589 ms 40552 KB Output is correct
7 Correct 510 ms 39672 KB Output is correct
8 Correct 1276 ms 39168 KB Output is correct
9 Correct 473 ms 39416 KB Output is correct
10 Correct 582 ms 39316 KB Output is correct
11 Correct 528 ms 39276 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 24312 KB Output is correct
2 Correct 3642 ms 147084 KB Output is correct
3 Execution timed out 8108 ms 148600 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 24568 KB Output is correct
2 Correct 518 ms 39940 KB Output is correct
3 Correct 515 ms 40440 KB Output is correct
4 Correct 503 ms 40464 KB Output is correct
5 Correct 466 ms 40824 KB Output is correct
6 Correct 589 ms 40552 KB Output is correct
7 Correct 510 ms 39672 KB Output is correct
8 Correct 1276 ms 39168 KB Output is correct
9 Correct 473 ms 39416 KB Output is correct
10 Correct 582 ms 39316 KB Output is correct
11 Correct 528 ms 39276 KB Output is correct
12 Correct 20 ms 24312 KB Output is correct
13 Correct 3642 ms 147084 KB Output is correct
14 Execution timed out 8108 ms 148600 KB Time limit exceeded
15 Halted 0 ms 0 KB -