oj.uz

답안 #287486

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
287486 2020-08-31T17:40:08 Z limabeans 공장들 (JOI14_factories) C++17
15 / 100
 8000 ms 128332 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 = 19;
int par[maxn][LOG+1];
int dep[maxn];
ll depw[maxn];
int n;
 
void dfs(int at, int p) {
    if (~p) {
	for (int j=1; j<LOG; j++) {
	    par[at][j] = par[par[at][j-1]][j-1];
	}
    }
    for (auto ed: g[at]) {
	int to = ed.second;
	if (to == p) continue;
	par[to][0] = 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[u][j];
	}
    }
    
    if (u==v) return v;
 
    for (int j=LOG-1; j>=0; j--) {
	if (par[u][j] != par[v][j]) {
	    u=par[u][j];
	    v=par[v][j];
	}
    }
    return par[v][0];
}
 
 
 
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-1; 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 28 ms 24192 KB Output is correct
2 Correct 477 ms 32760 KB Output is correct
3 Correct 506 ms 32760 KB Output is correct
4 Correct 499 ms 32904 KB Output is correct
5 Correct 476 ms 33016 KB Output is correct
6 Correct 578 ms 32972 KB Output is correct
7 Correct 502 ms 32632 KB Output is correct
8 Correct 1282 ms 32896 KB Output is correct
9 Correct 478 ms 32996 KB Output is correct
10 Correct 577 ms 32868 KB Output is correct
11 Correct 502 ms 32752 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 24064 KB Output is correct
2 Correct 1705 ms 107488 KB Output is correct
3 Correct 3729 ms 109688 KB Output is correct
4 Correct 1135 ms 105168 KB Output is correct
5 Correct 3687 ms 128332 KB Output is correct
6 Correct 2976 ms 111220 KB Output is correct
7 Execution timed out 8060 ms 49484 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 24192 KB Output is correct
2 Correct 477 ms 32760 KB Output is correct
3 Correct 506 ms 32760 KB Output is correct
4 Correct 499 ms 32904 KB Output is correct
5 Correct 476 ms 33016 KB Output is correct
6 Correct 578 ms 32972 KB Output is correct
7 Correct 502 ms 32632 KB Output is correct
8 Correct 1282 ms 32896 KB Output is correct
9 Correct 478 ms 32996 KB Output is correct
10 Correct 577 ms 32868 KB Output is correct
11 Correct 502 ms 32752 KB Output is correct
12 Correct 19 ms 24064 KB Output is correct
13 Correct 1705 ms 107488 KB Output is correct
14 Correct 3729 ms 109688 KB Output is correct
15 Correct 1135 ms 105168 KB Output is correct
16 Correct 3687 ms 128332 KB Output is correct
17 Correct 2976 ms 111220 KB Output is correct
18 Execution timed out 8060 ms 49484 KB Time limit exceeded
19 Halted 0 ms 0 KB -