제출 #1310482

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1310482		thuhienne	Reconstruction Project (JOI22_reconstruction)	C++20	100 / 100	1751 ms	18936 KiB

reconstruction

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define re exit(0);
#define union __union__

const int maxm = 100009;
const int maxn = 509;

int n,m;
struct _ {
	int u,v,w;
	bool operator < (const _ & other) {
		return w < other.w;
	}
} edge[maxm];

int root[maxn],l[maxm],r[maxm];

//lemma 1:canh i se co mat o 1 trong cac cay khung nho nhat
//Chua chung minh duoc :)))

//lemma 2: trong doan tren thi canh i chac chan se co mat trong moi cay khung
//Do theo cach implementation thi nhung canh ma tao ra chu trinh voi i se k co trong doan

int getroot(int node) {
	return node == root[node] ? node : root[node] = getroot(root[node]);
}
void union(int u,int v) {
	u = getroot(u),v = getroot(v);
	if (u == v) return;
	root[u] = v;
}

pair <int, pair <int,int>> tdgc[3 * maxm];

int main() {
  ios_base::sync_with_stdio(0);cin.tie(nullptr);

	cin >> n >> m;
	for (int i = 1;i <= m;i++) cin >> edge[i].u >> edge[i].v >> edge[i].w;
	
	sort(edge + 1,edge + 1 + m);
	
	memset(l,-0x3f,sizeof(l));
	memset(r,0x3f,sizeof(r));
	
	for (int i = 1;i <= m;i++) {
		for (int j = 1;j <= n;j++) root[j] = j;
		for (int j = i - 1;j >= 1;j--) {
			
			union(edge[j].u,edge[j].v);
			if (getroot(edge[i].u) == getroot(edge[i].v)) {
				l[i] = (edge[i].w + edge[j].w) / 2 + 1;
				break;
			}
			
		}
		
		for (int j = 1;j <= n;j++) root[j] = j;
		for (int j = i + 1;j <= m;j++) {
			
			union(edge[j].u,edge[j].v);
			if (getroot(edge[i].u) == getroot(edge[i].v)) {
				r[i] = (edge[i].w + edge[j].w) / 2;
				break;
			}
			
		}
	}
	
	int sz = 0;
	for (int i = 1;i <= m;i++) {
		tdgc[++sz] = {l[i],{-1,edge[i].w}};
		tdgc[++sz] = {edge[i].w,{2,-2 * edge[i].w}};
		tdgc[++sz] = {r[i] + 1,{-1,edge[i].w}};
	}
	
	sort(tdgc + 1,tdgc + 1 + sz);
	
	int pt = 0;
	ll t1 = 0,t2 = 0;
	
	int q;cin >> q;while (q--) {
		int x;cin >> x;
		while (pt < sz && tdgc[pt + 1].first <= x) {
			pt++;
			t1 += tdgc[pt].second.first;
			t2 += tdgc[pt].second.second;
		}
		
		cout << 1ll * t1 * x + t2 << '\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