oj.uz

답안 #287470

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
287470 2020-08-31T17:14:57 Z limabeans 공장들 (JOI14_factories) C++17
15 / 100
 8000 ms 130696 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[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 24568 KB Output is correct
2 Correct 496 ms 42164 KB Output is correct
3 Correct 519 ms 41976 KB Output is correct
4 Correct 495 ms 41968 KB Output is correct
5 Correct 485 ms 42104 KB Output is correct
6 Correct 590 ms 41952 KB Output is correct
7 Correct 527 ms 42104 KB Output is correct
8 Correct 1323 ms 42308 KB Output is correct
9 Correct 494 ms 42544 KB Output is correct
10 Correct 614 ms 42320 KB Output is correct
11 Correct 609 ms 42104 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 24064 KB Output is correct
2 Correct 2227 ms 110076 KB Output is correct
3 Correct 4583 ms 112560 KB Output is correct
4 Correct 1510 ms 107384 KB Output is correct
5 Correct 4862 ms 130696 KB Output is correct
6 Correct 3785 ms 113376 KB Output is correct
7 Execution timed out 8058 ms 53376 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 24568 KB Output is correct
2 Correct 496 ms 42164 KB Output is correct
3 Correct 519 ms 41976 KB Output is correct
4 Correct 495 ms 41968 KB Output is correct
5 Correct 485 ms 42104 KB Output is correct
6 Correct 590 ms 41952 KB Output is correct
7 Correct 527 ms 42104 KB Output is correct
8 Correct 1323 ms 42308 KB Output is correct
9 Correct 494 ms 42544 KB Output is correct
10 Correct 614 ms 42320 KB Output is correct
11 Correct 609 ms 42104 KB Output is correct
12 Correct 18 ms 24064 KB Output is correct
13 Correct 2227 ms 110076 KB Output is correct
14 Correct 4583 ms 112560 KB Output is correct
15 Correct 1510 ms 107384 KB Output is correct
16 Correct 4862 ms 130696 KB Output is correct
17 Correct 3785 ms 113376 KB Output is correct
18 Execution timed out 8058 ms 53376 KB Time limit exceeded
19 Halted 0 ms 0 KB -