oj.uz

답안 #287472

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
287472 2020-08-31T17:17:40 Z limabeans 공장들 (JOI14_factories) C++17
15 / 100
 8000 ms 128596 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; 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 24440 KB Output is correct
2 Correct 507 ms 33148 KB Output is correct
3 Correct 523 ms 33568 KB Output is correct
4 Correct 527 ms 33684 KB Output is correct
5 Correct 490 ms 33784 KB Output is correct
6 Correct 589 ms 33868 KB Output is correct
7 Correct 519 ms 33152 KB Output is correct
8 Correct 1297 ms 33180 KB Output is correct
9 Correct 480 ms 33408 KB Output is correct
10 Correct 606 ms 33452 KB Output is correct
11 Correct 511 ms 33180 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 24056 KB Output is correct
2 Correct 2156 ms 107976 KB Output is correct
3 Correct 4694 ms 110312 KB Output is correct
4 Correct 1414 ms 105360 KB Output is correct
5 Correct 4705 ms 128596 KB Output is correct
6 Correct 3659 ms 111376 KB Output is correct
7 Execution timed out 8023 ms 50184 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 24440 KB Output is correct
2 Correct 507 ms 33148 KB Output is correct
3 Correct 523 ms 33568 KB Output is correct
4 Correct 527 ms 33684 KB Output is correct
5 Correct 490 ms 33784 KB Output is correct
6 Correct 589 ms 33868 KB Output is correct
7 Correct 519 ms 33152 KB Output is correct
8 Correct 1297 ms 33180 KB Output is correct
9 Correct 480 ms 33408 KB Output is correct
10 Correct 606 ms 33452 KB Output is correct
11 Correct 511 ms 33180 KB Output is correct
12 Correct 21 ms 24056 KB Output is correct
13 Correct 2156 ms 107976 KB Output is correct
14 Correct 4694 ms 110312 KB Output is correct
15 Correct 1414 ms 105360 KB Output is correct
16 Correct 4705 ms 128596 KB Output is correct
17 Correct 3659 ms 111376 KB Output is correct
18 Execution timed out 8023 ms 50184 KB Time limit exceeded
19 Halted 0 ms 0 KB -