oj.uz

답안 #287415

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
287415 2020-08-31T16:51:14 Z limabeans 공장들 (JOI14_factories) C++17
15 / 100
 8000 ms 336060 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 = 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;    
}

map<int, ll> cache;

int hsh(int u, int v) {
    if (u>v) swap(u,v);
    return ((1<<19)*u) + v;
}

ll dist(int u, int v) {
    if (u==v) return 0;
    int mid = lca(u,v);
    if (u>v) swap(u,v);
    int hh = hsh(u,v);
    if (cache.count(hh)) {
	//cout<<u<<v<<endl;
	return cache[hh];
    }
    return cache[hh]=(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 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 24448 KB Output is correct
2 Correct 524 ms 34168 KB Output is correct
3 Correct 540 ms 33404 KB Output is correct
4 Correct 537 ms 33536 KB Output is correct
5 Correct 507 ms 34424 KB Output is correct
6 Correct 612 ms 34244 KB Output is correct
7 Correct 538 ms 33272 KB Output is correct
8 Correct 1313 ms 33656 KB Output is correct
9 Correct 506 ms 34424 KB Output is correct
10 Correct 620 ms 34204 KB Output is correct
11 Correct 556 ms 33272 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 25088 KB Output is correct
2 Execution timed out 8064 ms 336060 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 24448 KB Output is correct
2 Correct 524 ms 34168 KB Output is correct
3 Correct 540 ms 33404 KB Output is correct
4 Correct 537 ms 33536 KB Output is correct
5 Correct 507 ms 34424 KB Output is correct
6 Correct 612 ms 34244 KB Output is correct
7 Correct 538 ms 33272 KB Output is correct
8 Correct 1313 ms 33656 KB Output is correct
9 Correct 506 ms 34424 KB Output is correct
10 Correct 620 ms 34204 KB Output is correct
11 Correct 556 ms 33272 KB Output is correct
12 Correct 25 ms 25088 KB Output is correct
13 Execution timed out 8064 ms 336060 KB Time limit exceeded
14 Halted 0 ms 0 KB -