제출 #639699

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
639699		LittleCube	Reconstruction Project (JOI22_reconstruction)	C++14	7 / 100	5080 ms	253748 KiB

reconstruction

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

int N, M, Q, dsu[505];
pii E[100005];
ll w[100005], q[1000006], ans[1000006];
vector<int> mst[1000006];


int find(int k)
{
	return k == dsu[k] ? k : dsu[k] = find(dsu[k]);
}

void MST(int qdx, vector<int> &edx)
{
	if(!mst[qdx].empty())
		return;
	for(int i = 1; i <= N; i++)
		dsu[i] = i;
	sort(edx.begin(), edx.end(), [&](int i, int j){ return make_pair(abs(q[qdx] - w[i]), i) < make_pair(abs(q[qdx] - w[j]), j); });
	int cnt = N - 1;
	for(auto i : edx)
	{
		if(find(E[i].F) != find(E[i].S))
		{
			dsu[find(E[i].F)] = find(E[i].S);
			mst[qdx].emplace_back(i);
			cnt--;
		}
		if(!cnt) break;
	}
	sort(mst[qdx].begin(), mst[qdx].end());
}



signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> N >> M;
	for(int i = 1; i <= M; i++)
		cin >> E[i].F >> E[i].S >> w[i];

	cin >> Q;
	vector<int> v;
	for(int i = 1; i <= M; i++)
		v.emplace_back(i);

	for(int i = 1; i <= Q; i++)
	{
		cin >> q[i];
		MST(i, v);
		for(int j : mst[i])
			ans[i] += abs(q[i] - w[j]);
		cout << ans[i] << '\n';
	}
	
}

• Subtask 1: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 0 / 7
• Subtask 4: 0 / 28
• Subtask 5: 0 / 35
• Subtask 6: 0 / 23