oj.uz

답안 #1100177

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1100177 2024-10-13T08:38:57 Z Nurislam 공장들 (JOI14_factories) C++17
33 / 100
 8000 ms 137104 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

# 결과 실행 시간 메모리 Grader output
1 Correct 81 ms 87204 KB Output is correct
2 Correct 953 ms 91960 KB Output is correct
3 Correct 843 ms 91820 KB Output is correct
4 Correct 851 ms 92108 KB Output is correct
5 Correct 954 ms 92220 KB Output is correct
6 Correct 1405 ms 92152 KB Output is correct
7 Correct 840 ms 91732 KB Output is correct
8 Correct 906 ms 92104 KB Output is correct
9 Correct 970 ms 92240 KB Output is correct
10 Correct 1337 ms 92068 KB Output is correct
11 Correct 849 ms 91776 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 87204 KB Output is correct
2 Correct 982 ms 112744 KB Output is correct
3 Correct 2684 ms 115636 KB Output is correct
4 Correct 834 ms 113792 KB Output is correct
5 Correct 1039 ms 137104 KB Output is correct
6 Correct 1717 ms 115732 KB Output is correct
7 Correct 3313 ms 96536 KB Output is correct
8 Correct 1075 ms 96444 KB Output is correct
9 Correct 870 ms 99236 KB Output is correct
10 Correct 1811 ms 96948 KB Output is correct

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 81 ms 87204 KB Output is correct
2 Correct 953 ms 91960 KB Output is correct
3 Correct 843 ms 91820 KB Output is correct
4 Correct 851 ms 92108 KB Output is correct
5 Correct 954 ms 92220 KB Output is correct
6 Correct 1405 ms 92152 KB Output is correct
7 Correct 840 ms 91732 KB Output is correct
8 Correct 906 ms 92104 KB Output is correct
9 Correct 970 ms 92240 KB Output is correct
10 Correct 1337 ms 92068 KB Output is correct
11 Correct 849 ms 91776 KB Output is correct
12 Correct 51 ms 87204 KB Output is correct
13 Correct 982 ms 112744 KB Output is correct
14 Correct 2684 ms 115636 KB Output is correct
15 Correct 834 ms 113792 KB Output is correct
16 Correct 1039 ms 137104 KB Output is correct
17 Correct 1717 ms 115732 KB Output is correct
18 Correct 3313 ms 96536 KB Output is correct
19 Correct 1075 ms 96444 KB Output is correct
20 Correct 870 ms 99236 KB Output is correct
21 Correct 1811 ms 96948 KB Output is correct
22 Correct 3243 ms 131640 KB Output is correct
23 Execution timed out 8051 ms 131136 KB Time limit exceeded
24 Halted 0 ms 0 KB -