oj.uz

Submission #1100175

# Submission time Handle Problem Language Result Execution time Memory
1100175 2024-10-13T08:38:26 Z Nurislam Factories (JOI14_factories) C++17
33 / 100
 8000 ms 152984 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 58 ms 87396 KB Output is correct
2 Correct 600 ms 91812 KB Output is correct
3 Correct 782 ms 91812 KB Output is correct
4 Correct 406 ms 91816 KB Output is correct
5 Correct 592 ms 92068 KB Output is correct
6 Correct 1130 ms 92068 KB Output is correct
7 Correct 741 ms 91588 KB Output is correct
8 Correct 455 ms 92056 KB Output is correct
9 Correct 596 ms 92244 KB Output is correct
10 Correct 1144 ms 92220 KB Output is correct
11 Correct 735 ms 91812 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 863 ms 112940 KB Output is correct
3 Correct 1972 ms 115620 KB Output is correct
4 Correct 692 ms 113820 KB Output is correct
5 Correct 943 ms 136964 KB Output is correct
6 Correct 1950 ms 115716 KB Output is correct
7 Correct 3273 ms 96456 KB Output is correct
8 Correct 1038 ms 96420 KB Output is correct
9 Correct 860 ms 99264 KB Output is correct
10 Correct 1692 ms 96956 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 87396 KB Output is correct
2 Correct 600 ms 91812 KB Output is correct
3 Correct 782 ms 91812 KB Output is correct
4 Correct 406 ms 91816 KB Output is correct
5 Correct 592 ms 92068 KB Output is correct
6 Correct 1130 ms 92068 KB Output is correct
7 Correct 741 ms 91588 KB Output is correct
8 Correct 455 ms 92056 KB Output is correct
9 Correct 596 ms 92244 KB Output is correct
10 Correct 1144 ms 92220 KB Output is correct
11 Correct 735 ms 91812 KB Output is correct
12 Correct 44 ms 87204 KB Output is correct
13 Correct 863 ms 112940 KB Output is correct
14 Correct 1972 ms 115620 KB Output is correct
15 Correct 692 ms 113820 KB Output is correct
16 Correct 943 ms 136964 KB Output is correct
17 Correct 1950 ms 115716 KB Output is correct
18 Correct 3273 ms 96456 KB Output is correct
19 Correct 1038 ms 96420 KB Output is correct
20 Correct 860 ms 99264 KB Output is correct
21 Correct 1692 ms 96956 KB Output is correct
22 Correct 1521 ms 121548 KB Output is correct
23 Correct 1130 ms 117088 KB Output is correct
24 Correct 1884 ms 123844 KB Output is correct
25 Correct 2027 ms 124260 KB Output is correct
26 Correct 2127 ms 114828 KB Output is correct
27 Correct 1720 ms 137452 KB Output is correct
28 Execution timed out 8074 ms 152984 KB Time limit exceeded
29 Halted 0 ms 0 KB -