oj.uz

Submission #1100178

# Submission time Handle Problem Language Result Execution time Memory
1100178 2024-10-13T08:39:12 Z Nurislam Factories (JOI14_factories) C++17
33 / 100
 8000 ms 136948 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
template <class F, class _S>
bool chmin(F &u, const _S &v){
	bool flag = false;
	if ( u > v ){
		u = v; flag |= true;
	}
	return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
	bool flag = false;
	if ( u < v ){
		u = v; flag |= true;
	}
	return flag;
}
typedef long long ll;
const ll n = 5e5+5, inf = 1e17;
vector<vector<array<int,2>>> g(n);
vector<ll> dif(n, inf);
priority_queue<array<ll,2>> q;

	vector<vector<int> > lc(22, vector<int> (n, 0));
	vector<ll> ds(n, 0), tin(n),tout(n);
	int tim = 0;
	void dfs(int ps, int pr){
		lc[0][ps] = pr;
		for (int i = 1; i < 22; i++)
		{
			lc[i][ps] = lc[i-1][lc[i-1][ps]];
		}
		tin[ps] = tim++;
		for(auto [to, d]:g[ps]){
			if(to == pr)continue;
			ds[to] = ds[ps] + d;
			dfs(to, ps);
		}
		tout[ps] = tim++;
		
	}
	int lca (int a, int b){
		if(tin[a] < tin[b] && tout[b] < tout[a])return a;
		if(tin[b] < tin[a] && tout[a] < tout[b])return b;
		for(int i = 20; i >= 0; i--){
			int na = lc[i][a];
			if(tin[na] < tin[b] && tout[b] < tout[na])continue;
			a = na;
		}
		return lc[0][a];
	}
	
void Init(int N, int A[], int B[], int D[]) {
	
	for(int i = 0; i < N-1; i++){
		g[A[i]].pb({B[i], D[i]});
		g[B[i]].pb({A[i], D[i]});
	}
	dfs(0,0);
}
long long Query(int S, int X[], int T, int Y[]) {
	if(S*T >= 1000){
		if(S<T)swap(S,T),swap(X,Y);
		q = priority_queue<array<ll,2>> ();
		set<int> rem;
		set<int> st;
		for(int i = 0; i < T; i++){
			st.insert(Y[i]);
		}
		for(int i = 0; i < S; i++){
			q.push({0, X[i]});
			dif[X[i]] = 0;
			rem.insert(X[i]);
		}
		while(q.size()){
			auto [dis, ps] = q.top();
			q.pop();
			dis = abs(dis);
			if(dif[ps] < dis)continue;
			if(st.count(ps)){
				for(auto i:rem)dif[i] = inf;
				return dis;
			}
			for(auto &[to, d]:g[ps]){
				if(chmin(dif[to], dif[ps] + d)){
					rem.insert(to);
					q.push({-dif[to], to});
				}
			}
		}
	}else{
		ll ans = inf;
		for(int i = 0; i < S; i++){
			for(int j = 0; j < T; j++){
				int l = lca(X[i],Y[j]);
				chmin(ans, ds[X[i]]+ds[Y[j]]-2*ds[l]);
			}
		}
		return ans;
	}
	return inf;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 87324 KB Output is correct
2 Correct 840 ms 91892 KB Output is correct
3 Correct 794 ms 91812 KB Output is correct
4 Correct 823 ms 92120 KB Output is correct
5 Correct 864 ms 92100 KB Output is correct
6 Correct 1225 ms 92152 KB Output is correct
7 Correct 793 ms 91720 KB Output is correct
8 Correct 908 ms 91984 KB Output is correct
9 Correct 909 ms 92236 KB Output is correct
10 Correct 1370 ms 92368 KB Output is correct
11 Correct 755 ms 91812 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 87204 KB Output is correct
2 Correct 851 ms 112744 KB Output is correct
3 Correct 2774 ms 115468 KB Output is correct
4 Correct 849 ms 113820 KB Output is correct
5 Correct 1079 ms 136948 KB Output is correct
6 Correct 1929 ms 115816 KB Output is correct
7 Correct 3280 ms 96532 KB Output is correct
8 Correct 1031 ms 96392 KB Output is correct
9 Correct 921 ms 99236 KB Output is correct
10 Correct 1767 ms 96932 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 87324 KB Output is correct
2 Correct 840 ms 91892 KB Output is correct
3 Correct 794 ms 91812 KB Output is correct
4 Correct 823 ms 92120 KB Output is correct
5 Correct 864 ms 92100 KB Output is correct
6 Correct 1225 ms 92152 KB Output is correct
7 Correct 793 ms 91720 KB Output is correct
8 Correct 908 ms 91984 KB Output is correct
9 Correct 909 ms 92236 KB Output is correct
10 Correct 1370 ms 92368 KB Output is correct
11 Correct 755 ms 91812 KB Output is correct
12 Correct 40 ms 87204 KB Output is correct
13 Correct 851 ms 112744 KB Output is correct
14 Correct 2774 ms 115468 KB Output is correct
15 Correct 849 ms 113820 KB Output is correct
16 Correct 1079 ms 136948 KB Output is correct
17 Correct 1929 ms 115816 KB Output is correct
18 Correct 3280 ms 96532 KB Output is correct
19 Correct 1031 ms 96392 KB Output is correct
20 Correct 921 ms 99236 KB Output is correct
21 Correct 1767 ms 96932 KB Output is correct
22 Correct 2817 ms 131632 KB Output is correct
23 Execution timed out 8064 ms 135472 KB Time limit exceeded
24 Halted 0 ms 0 KB -