oj.uz

Submission #1100161

# Submission time Handle Problem Language Result Execution time Memory
1100161 2024-10-13T07:38:09 Z Nurislam Factories (JOI14_factories) C++17
15 / 100
 8000 ms 77980 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 23 ms 32348 KB Output is correct
2 Correct 2487 ms 37120 KB Output is correct
3 Correct 734 ms 36888 KB Output is correct
4 Correct 988 ms 37124 KB Output is correct
5 Correct 1726 ms 36936 KB Output is correct
6 Correct 5007 ms 37280 KB Output is correct
7 Correct 818 ms 36852 KB Output is correct
8 Correct 2575 ms 37076 KB Output is correct
9 Correct 1818 ms 37092 KB Output is correct
10 Correct 4765 ms 37456 KB Output is correct
11 Correct 743 ms 36936 KB Output is correct

Subtask #2
0 / 18.0

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

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 32348 KB Output is correct
2 Correct 2487 ms 37120 KB Output is correct
3 Correct 734 ms 36888 KB Output is correct
4 Correct 988 ms 37124 KB Output is correct
5 Correct 1726 ms 36936 KB Output is correct
6 Correct 5007 ms 37280 KB Output is correct
7 Correct 818 ms 36852 KB Output is correct
8 Correct 2575 ms 37076 KB Output is correct
9 Correct 1818 ms 37092 KB Output is correct
10 Correct 4765 ms 37456 KB Output is correct
11 Correct 743 ms 36936 KB Output is correct
12 Correct 19 ms 32336 KB Output is correct
13 Execution timed out 8076 ms 77980 KB Time limit exceeded
14 Halted 0 ms 0 KB -