oj.uz

Submission #750565

# Submission time Handle Problem Language Result Execution time Memory
750565 2023-05-29T18:01:52 Z jmyszka2007 Factories (JOI14_factories) C++17
15 / 100
 8000 ms 524288 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];
unordered_map<int, ll>dist[LIM + 10];
unordered_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[]) {
	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 38 ms 39920 KB Output is correct
2 Correct 919 ms 49712 KB Output is correct
3 Correct 1208 ms 50292 KB Output is correct
4 Correct 840 ms 50380 KB Output is correct
5 Correct 1366 ms 51120 KB Output is correct
6 Correct 341 ms 48780 KB Output is correct
7 Correct 1194 ms 50376 KB Output is correct
8 Correct 1106 ms 50484 KB Output is correct
9 Correct 1319 ms 50996 KB Output is correct
10 Correct 317 ms 48904 KB Output is correct
11 Correct 1207 ms 50492 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 39680 KB Output is correct
2 Correct 5387 ms 324632 KB Output is correct
3 Correct 7566 ms 455828 KB Output is correct
4 Correct 1298 ms 162436 KB Output is correct
5 Execution timed out 8102 ms 524288 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 39920 KB Output is correct
2 Correct 919 ms 49712 KB Output is correct
3 Correct 1208 ms 50292 KB Output is correct
4 Correct 840 ms 50380 KB Output is correct
5 Correct 1366 ms 51120 KB Output is correct
6 Correct 341 ms 48780 KB Output is correct
7 Correct 1194 ms 50376 KB Output is correct
8 Correct 1106 ms 50484 KB Output is correct
9 Correct 1319 ms 50996 KB Output is correct
10 Correct 317 ms 48904 KB Output is correct
11 Correct 1207 ms 50492 KB Output is correct
12 Correct 24 ms 39680 KB Output is correct
13 Correct 5387 ms 324632 KB Output is correct
14 Correct 7566 ms 455828 KB Output is correct
15 Correct 1298 ms 162436 KB Output is correct
16 Execution timed out 8102 ms 524288 KB Time limit exceeded
17 Halted 0 ms 0 KB -