oj.uz

Submission #796850

# Submission time Handle Problem Language Result Execution time Memory
796850 2023-07-28T20:50:19 Z bane Factories (JOI14_factories) C++17
100 / 100
 3082 ms 166664 KB 
    #include <bits/stdc++.h>
    #include "factories.h"
     
   
     
    using namespace std;
     
    #define ll long long
     
    const ll MXN = 500005, INF = 1e18;
     
    bool done[MXN];
    int sz[MXN], cen[MXN], temp[MXN];
    ll dist[MXN][20], ans[MXN];
     
    vector<pair<int, ll>> g[MXN];
     
    int getSize(int cur, int par = -1) {
    	sz[cur] = 1;
    	for (auto [next, cost] : g[cur]) {
    		if (next != par && !done[next]) sz[cur] += getSize(next, cur);
    	}
    	return sz[cur];
    }
     
    int getCentroid(int cur, int des, int par = -1) {
    	for (auto [next, cost] : g[cur]) {
    		if (next != par && !done[next] && sz[next] > des / 2) return getCentroid(next, des, cur);
    	}
    	return cur;
    }
     
    void solve(int cur, int par, int top, ll dis) {
    	dist[cur][temp[cur]++] = dis;
    	for (auto [next, cost] : g[cur]) {
    		if (next != par && !done[next]) {
    			cen[next] = top;
    			solve(next, cur, top, dis + cost);
    		}
    	}
    }
     
    void decomp(int cur) {
    	cur = getCentroid(cur, getSize(cur));
    	done[cur] = 1;
    	solve(cur, cur, cur, 0);
    	for (auto [next, cost] : g[cur]) {
    		if (!done[next]) decomp(next);
    	}
    }
     
    void update(int cur, int t = 1) {
    	for (int Cur = cur, ind = temp[cur] - 1; Cur >= 0; Cur = cen[Cur], ind--) {
    		if (t) ans[Cur] = min(ans[Cur], dist[cur][ind]);
    		else ans[Cur] = INF;
    	}
    } 
     
    ll query(int cur) {
    	ll mn = INF;
    	for (int Cur = cur, ind = temp[cur] - 1; Cur >= 0; Cur = cen[Cur], ind--) {
    		mn = min(mn, ans[Cur] + dist[cur][ind]);
    	}
    	return mn;
    }
     
    void Init(int N, int A[], int B[], int D[]) {
    	for (int i = 0; i < N; i++) {
    		ans[i] = INF;
    		cen[i] = -1;
    		for (int j = 0; j < 20; j++) dist[i][j] = INF;
    		if (i == N - 1) break;
    		g[A[i]].push_back({B[i], D[i]});
    		g[B[i]].push_back({A[i], D[i]});
    	}
    	decomp(0);
    }
     
    ll Query(int S, int X[], int T, int Y[]) { 
    	for (int i = 0; i < S; i++) update(X[i]);
    	ll mn = INF;
    	for (int i = 0; i < T; i++) mn = min(mn, query(Y[i]));
    	for (int i = 0; i < S; i++) update(X[i], 0);
    	return mn;
    }

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12372 KB Output is correct
2 Correct 206 ms 21248 KB Output is correct
3 Correct 219 ms 21280 KB Output is correct
4 Correct 220 ms 21320 KB Output is correct
5 Correct 236 ms 21592 KB Output is correct
6 Correct 152 ms 21244 KB Output is correct
7 Correct 220 ms 21248 KB Output is correct
8 Correct 226 ms 21352 KB Output is correct
9 Correct 228 ms 21580 KB Output is correct
10 Correct 154 ms 21196 KB Output is correct
11 Correct 224 ms 21360 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12244 KB Output is correct
2 Correct 1314 ms 139052 KB Output is correct
3 Correct 2169 ms 142008 KB Output is correct
4 Correct 494 ms 136652 KB Output is correct
5 Correct 2777 ms 166664 KB Output is correct
6 Correct 2259 ms 143292 KB Output is correct
7 Correct 552 ms 46200 KB Output is correct
8 Correct 259 ms 45976 KB Output is correct
9 Correct 622 ms 50020 KB Output is correct
10 Correct 553 ms 47360 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12372 KB Output is correct
2 Correct 206 ms 21248 KB Output is correct
3 Correct 219 ms 21280 KB Output is correct
4 Correct 220 ms 21320 KB Output is correct
5 Correct 236 ms 21592 KB Output is correct
6 Correct 152 ms 21244 KB Output is correct
7 Correct 220 ms 21248 KB Output is correct
8 Correct 226 ms 21352 KB Output is correct
9 Correct 228 ms 21580 KB Output is correct
10 Correct 154 ms 21196 KB Output is correct
11 Correct 224 ms 21360 KB Output is correct
12 Correct 6 ms 12244 KB Output is correct
13 Correct 1314 ms 139052 KB Output is correct
14 Correct 2169 ms 142008 KB Output is correct
15 Correct 494 ms 136652 KB Output is correct
16 Correct 2777 ms 166664 KB Output is correct
17 Correct 2259 ms 143292 KB Output is correct
18 Correct 552 ms 46200 KB Output is correct
19 Correct 259 ms 45976 KB Output is correct
20 Correct 622 ms 50020 KB Output is correct
21 Correct 553 ms 47360 KB Output is correct
22 Correct 1471 ms 140668 KB Output is correct
23 Correct 1529 ms 142924 KB Output is correct
24 Correct 2461 ms 143972 KB Output is correct
25 Correct 2523 ms 147392 KB Output is correct
26 Correct 2486 ms 144064 KB Output is correct
27 Correct 3082 ms 164744 KB Output is correct
28 Correct 630 ms 140640 KB Output is correct
29 Correct 2512 ms 143692 KB Output is correct
30 Correct 2464 ms 143224 KB Output is correct
31 Correct 2515 ms 143776 KB Output is correct
32 Correct 649 ms 51148 KB Output is correct
33 Correct 255 ms 46392 KB Output is correct
34 Correct 416 ms 43988 KB Output is correct
35 Correct 415 ms 43964 KB Output is correct
36 Correct 548 ms 44920 KB Output is correct
37 Correct 543 ms 44756 KB Output is correct