oj.uz

Submission #212578

# Submission time Handle Problem Language Result Execution time Memory
212578 2020-03-23T15:17:39 Z ChrisT Factories (JOI14_factories) C++17
100 / 100
 5098 ms 509532 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pil = pair<int,ll>;
using ld = long double;
#define all(x) (x).begin(),(x).end()
const int MN = 5e5+3, LOG = 20, MOD = 1e9+7;
mt19937_64 rnd = mt19937_64(chrono::steady_clock::now().time_since_epoch().count());
int sz[MN], p[MN], st[MN], tt=0; bool done[MN]; ll push[MN], down[MN], up[MN], sp[MN<<1][LOG];
vector<pii> adj[MN];vector<pil> go[MN];
void prep (int cur, int par = -1) {
	sp[st[cur] = ++tt][0] = push[cur];
    for (pii i : adj[cur]) if (i.first != par) {
        push[i.first] = push[cur] + i.second;
        prep(i.first,cur);
		sp[++tt][0] = push[cur];
    }
}
void initlca () {
	for (int j = 1; j < LOG; j++)
		for (int i = 1; i <= tt-(1<<j)+1; i++)
			sp[i][j] = min(sp[i][j-1],sp[i+(1<<(j-1))][j-1]);
}
ll dist (int a, int b) {
	if (a == b) return 0;
	if (st[a] > st[b]) swap(a,b);
	int lg = 31 - __builtin_clz(st[b]-st[a]+1);
	return push[a] + push[b] - min(sp[st[a]][lg],sp[st[b]-(1<<lg)+1][lg])*2;
}
int dfs (int cur, int par = -1) {
    sz[cur] = 1;
    for (pii i : adj[cur]) if (!done[i.first] && i.first != par) {
        sz[cur] += dfs(i.first,cur);
    }
    return sz[cur];
}
int findcent (int cur, int tot, int par = -1) {
    for (pii i : adj[cur]) {
        if (i.first != par && !done[i.first] && sz[i.first] > (tot>>1))
            return findcent(i.first,tot,cur);
    }
    return cur;
}
void maketree (int cur, int lst = 0) {
    dfs(cur);
    int cent = findcent(cur,sz[cur]);
    done[cent] = 1;
    p[cent] = lst;
    for (pii i : adj[cent]) if (!done[i.first]) maketree(i.first,cent);
}
void Init (int n, int *a, int *b, int *d) {
    for (int i = 0; i < n-1; i++) {
        adj[++a[i]].emplace_back(++b[i],d[i]);
        adj[b[i]].emplace_back(a[i],d[i]);
    }
    prep(1);
    maketree(1);
	initlca();
	for (int i = 1; i <= n; i++) {
		int cur = i;
		while (cur) {
			go[i].emplace_back(cur,dist(i,cur));
			cur = p[cur];
		}
	}
    memset(down,0x3f,sizeof down);
}
ll Query (int s, int *x, int t, int *y) {
    ll ret = LLONG_MAX;
    for (int i = 0; i < s; i++) {
		for (auto &pp : go[++x[i]])
			if (pp.second < down[pp.first])
				down[pp.first] = pp.second;
    }
    for (int i = 0; i < t; i++) {
		for (auto &pp : go[++y[i]])
			ret = min(ret,pp.second + down[pp.first]);
    }
    for (int i = 0; i < s; i++) {
        for (auto &pp : go[x[i]])
			down[pp.first] = 1e18;
    }
    return ret;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 28544 KB Output is correct
2 Correct 435 ms 47968 KB Output is correct
3 Correct 450 ms 48376 KB Output is correct
4 Correct 457 ms 48384 KB Output is correct
5 Correct 475 ms 48632 KB Output is correct
6 Correct 346 ms 47352 KB Output is correct
7 Correct 461 ms 48376 KB Output is correct
8 Correct 463 ms 48376 KB Output is correct
9 Correct 488 ms 48760 KB Output is correct
10 Correct 346 ms 47352 KB Output is correct
11 Correct 470 ms 48380 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 28160 KB Output is correct
2 Correct 2629 ms 368736 KB Output is correct
3 Correct 3425 ms 434436 KB Output is correct
4 Correct 1284 ms 268672 KB Output is correct
5 Correct 4420 ms 503912 KB Output is correct
6 Correct 3538 ms 436164 KB Output is correct
7 Correct 1267 ms 116216 KB Output is correct
8 Correct 655 ms 95208 KB Output is correct
9 Correct 1384 ms 127840 KB Output is correct
10 Correct 1265 ms 117640 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 28544 KB Output is correct
2 Correct 435 ms 47968 KB Output is correct
3 Correct 450 ms 48376 KB Output is correct
4 Correct 457 ms 48384 KB Output is correct
5 Correct 475 ms 48632 KB Output is correct
6 Correct 346 ms 47352 KB Output is correct
7 Correct 461 ms 48376 KB Output is correct
8 Correct 463 ms 48376 KB Output is correct
9 Correct 488 ms 48760 KB Output is correct
10 Correct 346 ms 47352 KB Output is correct
11 Correct 470 ms 48380 KB Output is correct
12 Correct 23 ms 28160 KB Output is correct
13 Correct 2629 ms 368736 KB Output is correct
14 Correct 3425 ms 434436 KB Output is correct
15 Correct 1284 ms 268672 KB Output is correct
16 Correct 4420 ms 503912 KB Output is correct
17 Correct 3538 ms 436164 KB Output is correct
18 Correct 1267 ms 116216 KB Output is correct
19 Correct 655 ms 95208 KB Output is correct
20 Correct 1384 ms 127840 KB Output is correct
21 Correct 1265 ms 117640 KB Output is correct
22 Correct 3206 ms 374616 KB Output is correct
23 Correct 3282 ms 379672 KB Output is correct
24 Correct 4174 ms 442620 KB Output is correct
25 Correct 4104 ms 446776 KB Output is correct
26 Correct 4149 ms 443508 KB Output is correct
27 Correct 5098 ms 509532 KB Output is correct
28 Correct 1724 ms 279132 KB Output is correct
29 Correct 4022 ms 442624 KB Output is correct
30 Correct 4043 ms 442496 KB Output is correct
31 Correct 4006 ms 443184 KB Output is correct
32 Correct 1511 ms 128612 KB Output is correct
33 Correct 745 ms 95848 KB Output is correct
34 Correct 1084 ms 109560 KB Output is correct
35 Correct 1099 ms 110328 KB Output is correct
36 Correct 1276 ms 114552 KB Output is correct
37 Correct 1295 ms 114508 KB Output is correct