제출 #1157649

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1157649		zhasyn	공장들 (JOI14_factories)	C++20	100 / 100	2910 ms	347756 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
using namespace std;
#define F first
#define S second
typedef long long ll;
#define pii pair <int, int>
#define pll pair <ll, ll>
typedef long double ld;
const ll N = 5 * 1e5 + 100, M = 4096 + 10, len = 21, inf = 1e18;
const ll mod = 1e9 + 7;
ll um(ll a, ll b){
	return (1LL * a * b) % mod;
}
ll subr(ll a, ll b){
	return ((1LL * a - b) % mod + mod) % mod;
}
int n;
ll dis[N], sz[N], p[N];
vector <pll> q[N], boss[N];
bool was[N];
int dfs1(int v, int pred){
	sz[v] = 1;
	for(int i = 0; i < (int)q[v].size(); i++){
		pll u = q[v][i];
		if(u.F == pred) continue;
		sz[v] += dfs1(u.F, v);
	}
	return sz[v];
}
int dfs2(int v, int pred = -1){
	for(int i = 0; i < (int)q[v].size(); i++){
		pll u = q[v][i];
		if(u.F == pred || was[u.F]) continue;
		if(sz[u.F] * 2 > sz[v]){
			sz[v] -= sz[u.F];
			sz[u.F] += sz[v];
			return dfs2(u.F, v);
		}
	}
	return v;
}
void dfs3(int v, int pred, int orig, ll sum){
	boss[v].pb(make_pair(orig, sum));
	for(int i = 0; i < (int)q[v].size(); i++){
		pll u = q[v][i];
		if(u.F == pred || was[u.F]) continue;
		dfs3(u.F, v, orig, sum + u.S);
	}
}
void centroid(int v, int pred = -1){
	v = dfs2(v);
	p[v] = pred;
	was[v] = true;
	dfs3(v, -1, v, 0LL);
	for(int i = 0; i < (int)q[v].size(); i++){
		pll u = q[v][i];
		if(u.F == pred || was[u.F]) continue;
		centroid(u.F, v);
	}
}
void Init(int nx, int a[], int b[], int d[]) {
	n = nx;
	for(int i = 0; i < n; i++){
		dis[i] = LLONG_MAX;
	}
	for(int i = 0; i < n - 1; i++){
		q[a[i]].pb(make_pair(b[i], d[i]));
		q[b[i]].pb(make_pair(a[i], d[i]));
	}
	dfs1(0, -1);
	centroid(0);
}

long long Query(int s, int x[], int t, int y[]) {
//	cout << "was\n";
  for(int i = 0; i < s; i++){
  	for(int j = 0; j < (int)boss[x[i]].size(); j++){
  		pll u = boss[x[i]][j];
  		dis[u.F] = min(dis[u.F], u.S);
  		//cout << u.F << " "<< dis[u.F] << " Bosses\n";
	}
  }
  ll ans = LLONG_MAX;
  for(int i = 0; i < t; i++){
  	for(int j = 0; j < (int)boss[y[i]].size(); j++){
  		pll u = boss[y[i]][j];
  		if(dis[u.F] == LLONG_MAX) continue;
  		//cout << u.F << " "<< dis[u.F] << " "<< u.S << " Search answer\n";
  		ans = min(ans, dis[u.F] + u.S);
	}
  }
  
  for(int i = 0; i < s; i++){
  	for(int j = 0; j < (int)boss[x[i]].size(); j++){
  		pll u = boss[x[i]][j];
  		dis[u.F] = LLONG_MAX;
	}
  }
  return ans;
}

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67