oj.uz

Submission #1100176

# Submission time Handle Problem Language Result Execution time Memory
1100176 2024-10-13T08:38:42 Z Nurislam Factories (JOI14_factories) C++17
33 / 100
 8000 ms 137124 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 66 ms 87204 KB Output is correct
2 Correct 863 ms 92064 KB Output is correct
3 Correct 801 ms 91812 KB Output is correct
4 Correct 875 ms 91984 KB Output is correct
5 Correct 851 ms 92068 KB Output is correct
6 Correct 1226 ms 92068 KB Output is correct
7 Correct 758 ms 91772 KB Output is correct
8 Correct 803 ms 92052 KB Output is correct
9 Correct 868 ms 92216 KB Output is correct
10 Correct 1353 ms 92160 KB Output is correct
11 Correct 801 ms 91988 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 87204 KB Output is correct
2 Correct 985 ms 112832 KB Output is correct
3 Correct 2857 ms 115600 KB Output is correct
4 Correct 966 ms 113820 KB Output is correct
5 Correct 1000 ms 137124 KB Output is correct
6 Correct 1731 ms 115876 KB Output is correct
7 Correct 3428 ms 96536 KB Output is correct
8 Correct 1117 ms 96420 KB Output is correct
9 Correct 972 ms 99236 KB Output is correct
10 Correct 1976 ms 96932 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 87204 KB Output is correct
2 Correct 863 ms 92064 KB Output is correct
3 Correct 801 ms 91812 KB Output is correct
4 Correct 875 ms 91984 KB Output is correct
5 Correct 851 ms 92068 KB Output is correct
6 Correct 1226 ms 92068 KB Output is correct
7 Correct 758 ms 91772 KB Output is correct
8 Correct 803 ms 92052 KB Output is correct
9 Correct 868 ms 92216 KB Output is correct
10 Correct 1353 ms 92160 KB Output is correct
11 Correct 801 ms 91988 KB Output is correct
12 Correct 44 ms 87204 KB Output is correct
13 Correct 985 ms 112832 KB Output is correct
14 Correct 2857 ms 115600 KB Output is correct
15 Correct 966 ms 113820 KB Output is correct
16 Correct 1000 ms 137124 KB Output is correct
17 Correct 1731 ms 115876 KB Output is correct
18 Correct 3428 ms 96536 KB Output is correct
19 Correct 1117 ms 96420 KB Output is correct
20 Correct 972 ms 99236 KB Output is correct
21 Correct 1976 ms 96932 KB Output is correct
22 Correct 3217 ms 132388 KB Output is correct
23 Execution timed out 8064 ms 131144 KB Time limit exceeded
24 Halted 0 ms 0 KB -