oj.uz

답안 #287448

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
287448 2020-08-31T17:06:25 Z limabeans 공장들 (JOI14_factories) C++17
15 / 100
 8000 ms 147060 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];
int dep[maxn];
ll depw[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]];
	}
    }
    for (auto ed: g[at]) {
	int to = ed.second;
	if (to == p) continue;
	par[0][to] = at;
	dep[to] = 1+dep[at];
	depw[to] = ed.first+depw[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 dist(int u, int v) {
    if (u==v) return 0;
    int mid = lca(u,v);
    return depw[u]+depw[v]-2ll*depw[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

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 24320 KB Output is correct
2 Correct 557 ms 32888 KB Output is correct
3 Correct 546 ms 32888 KB Output is correct
4 Correct 520 ms 33008 KB Output is correct
5 Correct 486 ms 33148 KB Output is correct
6 Correct 602 ms 32988 KB Output is correct
7 Correct 528 ms 32888 KB Output is correct
8 Correct 1356 ms 33016 KB Output is correct
9 Correct 507 ms 33180 KB Output is correct
10 Correct 590 ms 32988 KB Output is correct
11 Correct 522 ms 32760 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 24192 KB Output is correct
2 Correct 3165 ms 107484 KB Output is correct
3 Correct 5948 ms 109580 KB Output is correct
4 Correct 1948 ms 123564 KB Output is correct
5 Correct 5368 ms 147060 KB Output is correct
6 Correct 4918 ms 129800 KB Output is correct
7 Execution timed out 8093 ms 63196 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 24320 KB Output is correct
2 Correct 557 ms 32888 KB Output is correct
3 Correct 546 ms 32888 KB Output is correct
4 Correct 520 ms 33008 KB Output is correct
5 Correct 486 ms 33148 KB Output is correct
6 Correct 602 ms 32988 KB Output is correct
7 Correct 528 ms 32888 KB Output is correct
8 Correct 1356 ms 33016 KB Output is correct
9 Correct 507 ms 33180 KB Output is correct
10 Correct 590 ms 32988 KB Output is correct
11 Correct 522 ms 32760 KB Output is correct
12 Correct 19 ms 24192 KB Output is correct
13 Correct 3165 ms 107484 KB Output is correct
14 Correct 5948 ms 109580 KB Output is correct
15 Correct 1948 ms 123564 KB Output is correct
16 Correct 5368 ms 147060 KB Output is correct
17 Correct 4918 ms 129800 KB Output is correct
18 Execution timed out 8093 ms 63196 KB Time limit exceeded
19 Halted 0 ms 0 KB -