oj.uz

Submission #750564

# Submission time Handle Problem Language Result Execution time Memory
750564 2023-05-29T18:00:58 Z jmyszka2007 Factories (JOI14_factories) C++17
15 / 100
 1352 ms 57164 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
typedef long long ll;
constexpr int LIM = 1e5;
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 19 ms 8532 KB Output is correct
2 Correct 893 ms 18292 KB Output is correct
3 Correct 1304 ms 28456 KB Output is correct
4 Correct 858 ms 28472 KB Output is correct
5 Correct 1302 ms 29076 KB Output is correct
6 Correct 323 ms 26928 KB Output is correct
7 Correct 1219 ms 28420 KB Output is correct
8 Correct 1256 ms 28572 KB Output is correct
9 Correct 1352 ms 29036 KB Output is correct
10 Correct 321 ms 26820 KB Output is correct
11 Correct 1288 ms 28544 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8404 KB Output is correct
2 Runtime error 330 ms 57164 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 8532 KB Output is correct
2 Correct 893 ms 18292 KB Output is correct
3 Correct 1304 ms 28456 KB Output is correct
4 Correct 858 ms 28472 KB Output is correct
5 Correct 1302 ms 29076 KB Output is correct
6 Correct 323 ms 26928 KB Output is correct
7 Correct 1219 ms 28420 KB Output is correct
8 Correct 1256 ms 28572 KB Output is correct
9 Correct 1352 ms 29036 KB Output is correct
10 Correct 321 ms 26820 KB Output is correct
11 Correct 1288 ms 28544 KB Output is correct
12 Correct 7 ms 8404 KB Output is correct
13 Runtime error 330 ms 57164 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -