oj.uz

Submission #405739

# Submission time Handle Problem Language Result Execution time Memory
405739 2021-05-16T21:01:56 Z knightron0 Factories (JOI14_factories) C++17
100 / 100
 6006 ms 191528 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define fr first
#define sc second
#define clr(a, x) memset(a, x, sizeof(a))
#define dbg(x) cout<<"("<<#x<<"): "<<x<<endl;
#define printvector(arr) for (auto it = arr.begin(); it != arr.end(); ++it) cout<<*it<<" "; cout<<endl;
#define all(v) v.begin(), v.end()
#define lcm(a, b) (a * b)/__gcd(a, b)
#define printvecpairs(vec) for(auto it: vec) cout<<it.fr<<' '<<it.sc<<endl;
#define endl '\n'
#define ll long long int
#define float long double

const int MOD = 1e9 + 7;
const ll INF = 2e15;
const int MAXN = 5e5 + 5;
const int LOGN = 23;

vector<array<ll, 2>> adj[MAXN];
ll par[MAXN], sz[MAXN], depth[MAXN], dist[LOGN][MAXN], ans[MAXN], nm;
bool rm[MAXN];

int dfs(int u, int p){
	sz[u] = 1;
	for(auto &[v, w]: adj[u]){
		if(v != p && !rm[v]){
			sz[u] += dfs(v, u);
		}
	}
	return sz[u];
}

void dfs2(int u, int p, int l){
	for(auto &[v, w]: adj[u]){
		if(v != p && !rm[v]){
			dist[l][v] = dist[l][u] + w;
			dfs2(v, u, l);
		}
	}
}

int centroid(int u, int p, int n){
	for(auto &[v, w]: adj[u]){
		if(v != p && !rm[v]){
			if(sz[v]*2 > n){
				return centroid(v, u, n);
			}
		}
	}
	return u;
}

void decompose(int u, int p, int d){
	int n = dfs(u, p);
	int c = centroid(u, p, n);
	par[c] = p;
	depth[c] = d;
	dist[d][c] = 0;
	dfs2(c, -1, d);
	rm[c] = 1;
	for(auto &[v, w]: adj[c]){
		if(!rm[v]){
			decompose(v, c, d+1);
		}		
	}
}

void update(int v, int s){
	ans[v] = min(ans[v], dist[depth[v]][s]);
	if(depth[v] != 0){
		update(par[v], s);
	}
}

ll qry(int v, int s){
	if(depth[v] != 0){
		return min(ans[v]+dist[depth[v]][s], qry(par[v], s));
	} else {
		return ans[v] + dist[depth[v]][s];
	}
}

void Init(int N, int A[], int B[], int D[]) {
	nm = N;
	for(int i=0;i<=N;i++){
		rm[i] = false;
		sz[i] = 1;
	}
	for(int i= 0;i<nm-1;i++){
		A[i]++; B[i]++;
		adj[A[i]].pb({B[i], D[i]});
		adj[B[i]].pb({A[i], D[i]});
	}
	decompose(1, 0, 0);
	for(int i=0;i<=nm;i++) ans[i]= INF;
}

ll Query(int S, int X[], int T, int Y[]){
	for(int i=0;i<S;i++){
		X[i]++;
		update(X[i], X[i]);
	}
	ll res = INF;
	for(int i = 0;i<T;i++){
		Y[i]++;
		res = min(res, qry(Y[i], Y[i]));
	}
	for(int i = 0;i<S;i++){
		int curr = X[i];
		while(depth[curr] != 0){
			ans[curr] = INF;
			curr = par[curr];
		}
		ans[curr] = INF;
	}
	return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12612 KB Output is correct
2 Correct 376 ms 21728 KB Output is correct
3 Correct 427 ms 21840 KB Output is correct
4 Correct 438 ms 21952 KB Output is correct
5 Correct 482 ms 22176 KB Output is correct
6 Correct 249 ms 21400 KB Output is correct
7 Correct 409 ms 22088 KB Output is correct
8 Correct 444 ms 21952 KB Output is correct
9 Correct 456 ms 22212 KB Output is correct
10 Correct 244 ms 21412 KB Output is correct
11 Correct 406 ms 21892 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12256 KB Output is correct
2 Correct 2578 ms 125692 KB Output is correct
3 Correct 3928 ms 161868 KB Output is correct
4 Correct 795 ms 90396 KB Output is correct
5 Correct 4830 ms 187288 KB Output is correct
6 Correct 3880 ms 164088 KB Output is correct
7 Correct 1513 ms 58840 KB Output is correct
8 Correct 391 ms 46936 KB Output is correct
9 Correct 1669 ms 63716 KB Output is correct
10 Correct 1426 ms 60496 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12612 KB Output is correct
2 Correct 376 ms 21728 KB Output is correct
3 Correct 427 ms 21840 KB Output is correct
4 Correct 438 ms 21952 KB Output is correct
5 Correct 482 ms 22176 KB Output is correct
6 Correct 249 ms 21400 KB Output is correct
7 Correct 409 ms 22088 KB Output is correct
8 Correct 444 ms 21952 KB Output is correct
9 Correct 456 ms 22212 KB Output is correct
10 Correct 244 ms 21412 KB Output is correct
11 Correct 406 ms 21892 KB Output is correct
12 Correct 10 ms 12256 KB Output is correct
13 Correct 2578 ms 125692 KB Output is correct
14 Correct 3928 ms 161868 KB Output is correct
15 Correct 795 ms 90396 KB Output is correct
16 Correct 4830 ms 187288 KB Output is correct
17 Correct 3880 ms 164088 KB Output is correct
18 Correct 1513 ms 58840 KB Output is correct
19 Correct 391 ms 46936 KB Output is correct
20 Correct 1669 ms 63716 KB Output is correct
21 Correct 1426 ms 60496 KB Output is correct
22 Correct 3255 ms 150488 KB Output is correct
23 Correct 3189 ms 155096 KB Output is correct
24 Correct 5148 ms 170164 KB Output is correct
25 Correct 4717 ms 174000 KB Output is correct
26 Correct 4767 ms 170540 KB Output is correct
27 Correct 6006 ms 191528 KB Output is correct
28 Correct 997 ms 100864 KB Output is correct
29 Correct 4778 ms 170060 KB Output is correct
30 Correct 4718 ms 169712 KB Output is correct
31 Correct 4671 ms 170176 KB Output is correct
32 Correct 1606 ms 64128 KB Output is correct
33 Correct 388 ms 47400 KB Output is correct
34 Correct 929 ms 53792 KB Output is correct
35 Correct 950 ms 53820 KB Output is correct
36 Correct 1329 ms 57284 KB Output is correct
37 Correct 1336 ms 57296 KB Output is correct