oj.uz

답안 #287490

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
287490 2020-08-31T17:57:26 Z limabeans 공장들 (JOI14_factories) C++17
15 / 100
 8000 ms 411044 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;
int cloc = 0;
int tin[maxn];
vector<pair<int,int>> ett;

struct sparse_table {

    int LOG = 0;
    int n;
    vector<pair<int,int>> a[100];
    vector<int> lg_floor;

    pair<int,int> eval(pair<int,int> x, pair<int,int> y) {
	return min(x, y);
    }

    void init(vector<pair<int,int>> v) {
	n = v.size();
	LOG = 0;
	while ((1<<LOG) <= n) LOG++;
	lg_floor.resize(n+10);
	lg_floor[1] = 0;
	for (int i=2; i<n+10; i++) lg_floor[i] = 1 + lg_floor[i/2];
	for (int j=0; j<LOG; j++) a[j].resize(n);
	for (int i=0; i<n; i++) a[0][i] = v[i];
	

	for (int j=1; j<LOG; j++) {
	    for (int i=0; i<n; i++) {
		a[j][i] = a[j-1][i];
		if (i + (1<<(j-1)) < n) {
		    a[j][i] = eval(a[j][i], a[j-1][i + (1<<(j-1))]);
		}
	    }
	}
    }

    pair<int,int> get(int l, int r) {
	assert(l<=r);
	int lg = lg_floor[r - l + 1];

	return eval(a[lg][l], a[lg][r-(1<<lg)+1]);
	
    }
};

sparse_table tbl;

void dfs(int at, int p) {
    tin[at] = cloc++;
    ett.push_back({tin[at], at});

    
    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);
	ett.push_back({tin[at], at});
	cloc++;
    }

    ett.push_back({tin[at], at});
    cloc++;
}


int lca(int u, int v) {
    if (u==v) return u;
    int lo = tin[u];
    int hi = tin[v];
    if (lo>hi) swap(lo, hi);
    pair<int,int> res = tbl.get(lo, hi);
    return res.second;
}

int lcaBrute(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);
    tbl.init(ett);
}





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 30 ms 24320 KB Output is correct
2 Correct 512 ms 34732 KB Output is correct
3 Correct 538 ms 34680 KB Output is correct
4 Correct 537 ms 34860 KB Output is correct
5 Correct 494 ms 34936 KB Output is correct
6 Correct 577 ms 34808 KB Output is correct
7 Correct 532 ms 34680 KB Output is correct
8 Correct 1333 ms 34888 KB Output is correct
9 Correct 495 ms 34936 KB Output is correct
10 Correct 576 ms 34716 KB Output is correct
11 Correct 541 ms 34680 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 24288 KB Output is correct
2 Correct 2037 ms 384320 KB Output is correct
3 Correct 2210 ms 388436 KB Output is correct
4 Correct 1750 ms 381712 KB Output is correct
5 Correct 2140 ms 411044 KB Output is correct
6 Correct 2035 ms 388024 KB Output is correct
7 Execution timed out 8031 ms 101472 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 24320 KB Output is correct
2 Correct 512 ms 34732 KB Output is correct
3 Correct 538 ms 34680 KB Output is correct
4 Correct 537 ms 34860 KB Output is correct
5 Correct 494 ms 34936 KB Output is correct
6 Correct 577 ms 34808 KB Output is correct
7 Correct 532 ms 34680 KB Output is correct
8 Correct 1333 ms 34888 KB Output is correct
9 Correct 495 ms 34936 KB Output is correct
10 Correct 576 ms 34716 KB Output is correct
11 Correct 541 ms 34680 KB Output is correct
12 Correct 18 ms 24288 KB Output is correct
13 Correct 2037 ms 384320 KB Output is correct
14 Correct 2210 ms 388436 KB Output is correct
15 Correct 1750 ms 381712 KB Output is correct
16 Correct 2140 ms 411044 KB Output is correct
17 Correct 2035 ms 388024 KB Output is correct
18 Execution timed out 8031 ms 101472 KB Time limit exceeded
19 Halted 0 ms 0 KB -