oj.uz

Submission #287378

# Submission time Handle Problem Language Result Execution time Memory
287378 2020-08-31T16:33:40 Z limabeans Factories (JOI14_factories) C++17
15 / 100
 2072 ms 23160 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 = 5001;

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];

long long Query(int S, int X[], int T, int 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 13 ms 1152 KB Output is correct
2 Correct 1388 ms 15480 KB Output is correct
3 Correct 503 ms 14892 KB Output is correct
4 Correct 702 ms 15028 KB Output is correct
5 Correct 857 ms 14972 KB Output is correct
6 Correct 2012 ms 15208 KB Output is correct
7 Correct 505 ms 18264 KB Output is correct
8 Correct 1505 ms 18432 KB Output is correct
9 Correct 854 ms 18424 KB Output is correct
10 Correct 2072 ms 18580 KB Output is correct
11 Correct 494 ms 18296 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 640 KB Output is correct
2 Runtime error 467 ms 23160 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1152 KB Output is correct
2 Correct 1388 ms 15480 KB Output is correct
3 Correct 503 ms 14892 KB Output is correct
4 Correct 702 ms 15028 KB Output is correct
5 Correct 857 ms 14972 KB Output is correct
6 Correct 2012 ms 15208 KB Output is correct
7 Correct 505 ms 18264 KB Output is correct
8 Correct 1505 ms 18432 KB Output is correct
9 Correct 854 ms 18424 KB Output is correct
10 Correct 2072 ms 18580 KB Output is correct
11 Correct 494 ms 18296 KB Output is correct
12 Correct 9 ms 640 KB Output is correct
13 Runtime error 467 ms 23160 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -