oj.uz

Submission #1100160

# Submission time Handle Problem Language Result Execution time Memory
1100160 2024-10-13T07:37:16 Z Nurislam Factories (JOI14_factories) C++17
15 / 100
 8000 ms 99280 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);
int sz;
void Init(int N, int A[], int B[], int D[]) {
	sz = N;
	for(int i = 0; i < N-1; i++){
		g[A[i]].pb({B[i], D[i]});
		g[B[i]].pb({A[i], D[i]});
	}
}
vector<ll> dif(n, inf);
priority_queue<array<ll,2>> q;
long long Query(int S, int X[], int T, int 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();
		//cout << dis << ' ' << ps << '\n';
		dis = abs(dis);
		if(dif[ps] < dis)continue;
		if(st.count(ps)){
			//for(int i = 0; i < sz; i++){
				//cout << dif[i]  << ' ' << i << '\n';
			//}
			//cout << '\n';
			for(auto i:rem)dif[i] = inf;
			return dis;
		}
		//cout << ps << '\n';
		for(auto &[to, d]:g[ps]){
			//cout << to << ' ' << d << '\n';
			if(chmin(dif[to], dif[ps] + d)){
				rem.insert(to);
				q.push({-dif[to], to});
			}
		}
	}
	
	
	return inf;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 32596 KB Output is correct
2 Correct 2438 ms 46572 KB Output is correct
3 Correct 729 ms 46200 KB Output is correct
4 Correct 960 ms 46572 KB Output is correct
5 Correct 1693 ms 46412 KB Output is correct
6 Correct 4727 ms 46972 KB Output is correct
7 Correct 777 ms 46412 KB Output is correct
8 Correct 2463 ms 46572 KB Output is correct
9 Correct 1702 ms 46412 KB Output is correct
10 Correct 4798 ms 46720 KB Output is correct
11 Correct 711 ms 46416 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 32596 KB Output is correct
2 Execution timed out 8061 ms 99280 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 32596 KB Output is correct
2 Correct 2438 ms 46572 KB Output is correct
3 Correct 729 ms 46200 KB Output is correct
4 Correct 960 ms 46572 KB Output is correct
5 Correct 1693 ms 46412 KB Output is correct
6 Correct 4727 ms 46972 KB Output is correct
7 Correct 777 ms 46412 KB Output is correct
8 Correct 2463 ms 46572 KB Output is correct
9 Correct 1702 ms 46412 KB Output is correct
10 Correct 4798 ms 46720 KB Output is correct
11 Correct 711 ms 46416 KB Output is correct
12 Correct 19 ms 32596 KB Output is correct
13 Execution timed out 8061 ms 99280 KB Time limit exceeded
14 Halted 0 ms 0 KB -