oj.uz

Submission #750568

# Submission time Handle Problem Language Result Execution time Memory
750568 2023-05-29T18:06:47 Z jmyszka2007 Factories (JOI14_factories) C++17
15 / 100
 8000 ms 388676 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
typedef long long ll;
constexpr int LIM = 5e5;
vector<pair<int, int> >g[LIM + 10];
map<int, ll>dist[LIM + 10];
map<int, ll>cnt;
int siz[LIM + 10];
int oj[LIM + 10];
bool vis[LIM + 10];
void cntsiz(int v, int o) {
	siz[v] = 1;
	for(auto x : g[v]) {
		if(x.st != o) {
			cntsiz(x.st, v);
			siz[v] += siz[x.st];
		}
	}
}
void cntdist(int v, int o, int kt) {
	for(auto x : g[v]) {
		if(x.st != o && !vis[x.st]) {
			dist[kt][x.st] = dist[kt][v] + x.nd;
			cntdist(x.st, v, kt);
		}
	}
}
int find(int a) {
	for(auto x : g[a]) {
		if(!vis[x.st] && siz[x.st] > siz[a] / 2) {
			int tmp = siz[x.st];
			siz[x.st] = siz[a];
			siz[a] -= tmp;
			return find(x.st);
		}
	}
	return a;
}
void dfs(int v, int o) {
	int c = find(v);
	oj[c] = o;
	vis[c] = 1;
	cntdist(c, c, c);
	for(auto x : g[c]) {
		if(!vis[x.st]) {
			dfs(x.st, c);
		}
	}
}
void Init(int n, int a[], int b[], int c[]) {
	for(int i = 0; i < n - 1; i++) {
		g[a[i]].push_back({b[i], c[i]});
		g[b[i]].push_back({a[i], c[i]});
	}
	cntsiz(1, 1);
	dfs(1, -1);
}
ll Query(int n, int a[], int m, int b[]) {
	vector<int>vs;
	for(int i = 0; i < n; i++) {
		int tmp = a[i];
		while(tmp != -1) {
			if(cnt.count(tmp)) {
				cnt[tmp] = min(cnt[tmp], dist[tmp][a[i]]);
			}
			else {
				cnt[tmp] = dist[tmp][a[i]];
			}
			tmp = oj[tmp];
		}
	}
	ll ans = 1e18;
	for(int i = 0; i < m; i++) {
		int tmp = b[i];
		while(tmp != -1) {
			if(cnt.count(tmp)) {
				ans = min(ans, cnt[tmp] + dist[tmp][b[i]]);
			}
			tmp = oj[tmp];
		}
	}
	cnt.clear();
	return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 36180 KB Output is correct
2 Correct 2968 ms 46424 KB Output is correct
3 Correct 4227 ms 47220 KB Output is correct
4 Correct 3341 ms 47632 KB Output is correct
5 Correct 5979 ms 48204 KB Output is correct
6 Correct 728 ms 44876 KB Output is correct
7 Correct 4229 ms 47172 KB Output is correct
8 Correct 4146 ms 47716 KB Output is correct
9 Correct 5823 ms 48036 KB Output is correct
10 Correct 731 ms 44948 KB Output is correct
11 Correct 4167 ms 47248 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 35796 KB Output is correct
2 Execution timed out 8058 ms 388676 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 36180 KB Output is correct
2 Correct 2968 ms 46424 KB Output is correct
3 Correct 4227 ms 47220 KB Output is correct
4 Correct 3341 ms 47632 KB Output is correct
5 Correct 5979 ms 48204 KB Output is correct
6 Correct 728 ms 44876 KB Output is correct
7 Correct 4229 ms 47172 KB Output is correct
8 Correct 4146 ms 47716 KB Output is correct
9 Correct 5823 ms 48036 KB Output is correct
10 Correct 731 ms 44948 KB Output is correct
11 Correct 4167 ms 47248 KB Output is correct
12 Correct 23 ms 35796 KB Output is correct
13 Execution timed out 8058 ms 388676 KB Time limit exceeded
14 Halted 0 ms 0 KB -