oj.uz

Submission #287430

# Submission time Handle Problem Language Result Execution time Memory
287430 2020-08-31T16:59:15 Z limabeans Factories (JOI14_factories) C++17
15 / 100
 8000 ms 184120 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 = 20;
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);
    if (u>v) swap(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 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;
}

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


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 24828 KB Output is correct
2 Correct 491 ms 36216 KB Output is correct
3 Correct 514 ms 36088 KB Output is correct
4 Correct 508 ms 36224 KB Output is correct
5 Correct 467 ms 36348 KB Output is correct
6 Correct 605 ms 36192 KB Output is correct
7 Correct 519 ms 36088 KB Output is correct
8 Correct 1293 ms 36600 KB Output is correct
9 Correct 471 ms 36428 KB Output is correct
10 Correct 628 ms 36364 KB Output is correct
11 Correct 508 ms 36088 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 24448 KB Output is correct
2 Correct 4395 ms 182512 KB Output is correct
3 Execution timed out 8071 ms 184120 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 24828 KB Output is correct
2 Correct 491 ms 36216 KB Output is correct
3 Correct 514 ms 36088 KB Output is correct
4 Correct 508 ms 36224 KB Output is correct
5 Correct 467 ms 36348 KB Output is correct
6 Correct 605 ms 36192 KB Output is correct
7 Correct 519 ms 36088 KB Output is correct
8 Correct 1293 ms 36600 KB Output is correct
9 Correct 471 ms 36428 KB Output is correct
10 Correct 628 ms 36364 KB Output is correct
11 Correct 508 ms 36088 KB Output is correct
12 Correct 20 ms 24448 KB Output is correct
13 Correct 4395 ms 182512 KB Output is correct
14 Execution timed out 8071 ms 184120 KB Time limit exceeded
15 Halted 0 ms 0 KB -