Submission #544958

#	Time	Username	Problem	Language	Result	Execution time	Memory
544958		benson1029	Reconstruction Project (JOI22_reconstruction)	C++14	100 / 100	4103 ms	436708 KiB

reconstruction

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

int n, m, q;
pair< int, pair<int,int> > edg[100005];
vector<int> f[100005], b[100005], t[100005];
int x[100005], y[100005];
int dsu[100005];
vector< pair<int,int> > v;
multiset<int> sm, lg; long long sm_sum = 0, lg_sum = 0;

int find(int x) {
	if(dsu[x]==x) return x;
	return dsu[x] = find(dsu[x]);
}

void merge(int x) {
	dsu[find(edg[x].second.first)] = find(edg[x].second.second);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for(int i=1; i<=m; i++) {
		cin >> edg[i].second.first >> edg[i].second.second >> edg[i].first;
	}
	sort(edg+1, edg+m+1);
	for(int i=1; i<=m; i++) {
		b[i].push_back(i);
		for(int j=1; j<=n; j++) dsu[j] = j;
		bool tmp = false;
		x[i] = -1;
		for(int j:b[i-1]) {
			if(find(edg[j].second.first)!=find(edg[j].second.second)) {
				merge(j);
				if(find(edg[i].second.first)==find(edg[i].second.second) && !tmp) {
					tmp = true;
					x[i] = (edg[j].first + edg[i].first + 2) / 2;
				}
				else b[i].push_back(j);
			}
		}
	}
	for(int i=m; i>=1; i--) {
		f[i].push_back(i);
		for(int j=1; j<=n; j++) dsu[j] = j;
		bool tmp = false;
		y[i] = 2e9;
		for(int j:f[i+1]) {
			if(find(edg[j].second.first)!=find(edg[j].second.second)) {
				merge(j);
				if(find(edg[i].second.first)==find(edg[i].second.second) && !tmp) {
					tmp = true;
					y[i] = (edg[j].first + edg[i].first) / 2;
				}
				else f[i].push_back(j);
			}
		}
	}
	for(int i=1; i<=m; i++) {
		if(x[i] <= y[i]) {
			v.push_back({x[i], edg[i].first});
			v.push_back({y[i]+1, -edg[i].first});
		}
	}
	sort(v.begin(), v.end());
	long long ans = 0;
	int ptr = 0;
	cin >> q;
	while(q--) {
		int w;
		cin >> w;
		while(!lg.empty() && (*lg.begin()) <= w) {
			sm_sum += (*lg.begin());
			lg_sum -= (*lg.begin());
			sm.insert(*lg.begin());
			lg.erase(lg.begin());
		}
		while(ptr < v.size() && v[ptr].first <= w) {
			if(abs(v[ptr].second) <= w) {
				sm_sum += v[ptr].second;
				if(v[ptr].second>0) sm.insert(v[ptr].second);
				else sm.erase(sm.find(-v[ptr].second));
			} else {
				lg_sum += v[ptr].second;
				if(v[ptr].second>0) lg.insert(v[ptr].second);
				else lg.erase(lg.find(-v[ptr].second));
			}
			ptr++;
		}
		cout << (w*sm.size() - sm_sum) + (lg_sum - w*lg.size()) << "\n";
	}
}

Compilation message (stderr)

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:80:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |   while(ptr < v.size() && v[ptr].first <= w) {
      |         ~~~~^~~~~~~~~~
reconstruction.cpp:68:12: warning: unused variable 'ans' [-Wunused-variable]
   68 |  long long ans = 0;
      |            ^~~

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