제출 #748571

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
748571		AdamGS	Reconstruction Project (JOI22_reconstruction)	C++17	100 / 100	724 ms	74456 KiB

reconstruction

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll INF=1e18+7;
const int LIM=1e5+7;
vector<pair<int,pair<ll,ll>>>V[LIM];
pair<ll,pair<int,int>>kraw[LIM];
pair<ll,ll>pr[LIM];
vector<pair<ll,pair<ll,ll>>>P;
ll ans[10*LIM];
pair<ll,ll>DFS(int x, int o, int p) {
	if(x==p) return {INF, INF};
	for(auto i : V[x]) if(i.st!=o) {
		pair<ll,ll>a=DFS(i.st, x, p);
		if(a.st!=-1) return min(a, i.nd);
	}
	return {-1, -1};
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, m;
	cin >> n >> m;
	rep(i, m) {
		cin >> kraw[i].nd.st >> kraw[i].nd.nd >> kraw[i].st;
		--kraw[i].nd.st; --kraw[i].nd.nd;
		pr[i].nd=INF;
	}
	sort(kraw, kraw+m);
	rep(i, m) {
		pair<ll,ll>a=DFS(kraw[i].nd.st, kraw[i].nd.st, kraw[i].nd.nd);
		if(a.nd!=-1) {
			pr[a.nd].nd=(kraw[a.nd].st+kraw[i].st+1)/2;
			pr[i].st=(kraw[a.nd].st+kraw[i].st+1)/2;
			vector<pair<int,pair<ll,ll>>>tmp;
			for(auto i : V[kraw[a.nd].nd.st]) if(i.nd.nd!=a.nd) tmp.pb(i);
			V[kraw[a.nd].nd.st]=tmp;
			tmp.clear();
			for(auto i : V[kraw[a.nd].nd.nd]) if(i.nd.nd!=a.nd) tmp.pb(i);
			V[kraw[a.nd].nd.nd]=tmp;
		}
		V[kraw[i].nd.st].pb({kraw[i].nd.nd, {kraw[i].st, i}});
		V[kraw[i].nd.nd].pb({kraw[i].nd.st, {kraw[i].st, i}});
	}
	rep(i, m) {
		P.pb({pr[i].st, {-1, kraw[i].st}});
		P.pb({kraw[i].st, {1, -kraw[i].st}});
		P.pb({kraw[i].st, {1, -kraw[i].st}});
		P.pb({pr[i].nd, {-1, kraw[i].st}});
	}
	int q;
	cin >> q;
	rep(i, q) {
		ll x;
		cin >> x;
		P.pb({x, {2, i}});
	}
	sort(all(P));
	ll ilex=0, ileconst=0;
	for(auto i : P) {
		if(i.nd.st==2) ans[i.nd.nd]=ilex*i.st+ileconst;
		else {
			ilex+=i.nd.st;
			ileconst+=i.nd.nd;
		}
	}
	rep(i, q) cout << ans[i] << '\n';
}

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