oj.uz

Submission #587835

# Submission time Handle Problem Language Result Execution time Memory
587835 2022-07-02T12:02:59 Z 8e7 Reconstruction Project (JOI22_reconstruction) C++17
3 / 100
 3898 ms 32308 KB 
//Challenge: Accepted
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 505
#define maxm 100005
#define maxq 1000005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const int inf = 1<<30;
struct edge{
	int u, v, w, id;
	edge(){u = v = w = id = 0;}
	edge(int a, int b, int c, int d){u = a, v = b, w = c, id = d;}
};

struct DSU{
	int par[maxn], siz[maxn];	
	vector<pii> op;
	void init(int n) {
		for (int i = 1;i <= n;i++) par[i] = i, siz[i] = 1;
	}
	int find(int a) {
		return a == par[a] ? a : (find(par[a]));
	}
	bool Union(int a, int b) {
		a = find(a), b = find(b);
		if (a == b) {
			op.push_back({0, 0});
			return 0;
		}
		if (siz[a] < siz[b]) swap(a, b);
		siz[a] += siz[b];
		par[b] = a;
		op.push_back({a, b});
		return 1;
	}
	void undo(int x) {
		while (x--) {
			assert(op.size() > 0);	
			int a = op.back().ff, b = op.back().ss;
			if (a) {
				siz[a] -= siz[b];
				par[b] = b;
			}
			op.pop_back();
		}
	}
} dsu;
vector<int> wei;
pii ran[maxm];

void solve(int l, int r, vector<edge> ed, vector<edge> lef, vector<edge> rig) {
	int m = (l + r) / 2;
	vector<edge> el, er, l0, r0, e1, l1, r1;

	int tot = ed.size() + lef.size() + rig.size();
	if (tot == 0) return;
	/*
	debug(l, r);
	for (auto e:ed) debug(e.id);
	debug();
	for (auto e:lef) debug(e.id);
	debug();
	for (auto e:rig) debug(e.id);
	debug("pick");
	*/

	auto cmp = [&] (edge &x, edge &y){
		return abs(x.w - m) < abs(y.w - m);
	};
	sort(ed.begin(), ed.end(), cmp);
	sort(lef.begin(), lef.end(), cmp);
	sort(rig.begin(), rig.end(), cmp);
	int s0 = ed.size(), s1 = lef.size(), s2 = rig.size();
	int i0 = 0, i1 = 0, i2 = 0;	
	for (int tmp = 0;tmp < tot;tmp++) {
		int mi = (i0 < s0 ? 0 : (i1 < s1 ? 1 : 2));
		edge cur = i0 < s0 ? ed[i0] : (i1 < s1 ? lef[i1] : rig[i2]);	
		if (i1 < s1 && cmp(lef[i1], cur)) {
			cur = lef[i1], mi = 1;
		}
		if (i2 < s2 && cmp(rig[i2], cur)) {
			cur = rig[i2], mi = 2;
		}
		if (mi == 0) {
			i0++;
			if (dsu.Union(cur.u, cur.v)) e1.push_back(cur);
			else if (cur.w <= m) el.push_back(cur);
			else er.push_back(cur);
		} else if (mi == 1) {
			i1++;
			if (dsu.Union(cur.u, cur.v)) l1.push_back(cur);
			else l0.push_back(cur);
		} else {
			i2++;
			if (dsu.Union(cur.u, cur.v)) r1.push_back(cur);
			else r0.push_back(cur);
		}
	}
	dsu.undo(tot);

	for (auto e:e1) ran[e.id] = {m, m+1};
	for (auto e:l1) ran[e.id].ff = m;
	//for (auto e:l0) ran[e.id].ff = r;
	for (auto e:r1) ran[e.id].ss = m+1;
	//for (auto e:r0) ran[e.id].ss = l;
	if (r - l == 1) return;

	vector<edge> tr = r1, tl = l1;
	tr.insert(tr.end(), e1.begin(), e1.end());
	tl.insert(tl.end(), e1.begin(), e1.end());

	int cnt = l1.size();
	for (auto e:l1) dsu.Union(e.u, e.v);
	solve(m, r, er, l0, tr);
	dsu.undo(cnt);
	
	cnt = r1.size();
	for (auto e:r1) dsu.Union(e.u, e.v);
	solve(l, m, el, tl, r0);
	dsu.undo(cnt);
}
bool on[maxm];
int main() {
	io
	int n, m;
	cin >> n >> m;
	vector<edge> ed, inil, inir;
	for (int i = 0;i < m;i++) {
		int u, v, w;
		cin >> u >> v >> w;
		wei.push_back(w);
		ed.push_back(edge(u, v, w, i));	
	}
	sort(ed.begin(), ed.end(), [&] (edge x, edge y){return x.w < y.w;});
	for (int i = 0;i < m;i++) ed[i].id = i;
	sort(wei.begin(), wei.end());
	dsu.init(n);
	solve(1, inf, ed, inil, inir);

	vector<pii> ev;
	for (int i = 0;i < m;i++) {
		//debug(ed[i].u, ed[i].v, ed[i].w, ran[i].ff, ran[i].ss);
		if (ran[i].ff) {
			ev.push_back({ran[i].ff, i});
			ev.push_back({ran[i].ss, i});
		}
	}
	sort(ev.begin(), ev.end());
 
	int q;
	cin >> q;
	vector<int> que(q);
	multiset<int> se;

	int ind = 0;
	for (int i = 0;i < q;i++) {
		cin >> que[i];
		while (ind < ev.size() && ev[ind].ff <= que[i]) {
			if (!on[ev[ind].ss]) {
				se.insert(wei[ev[ind].ss]);
				on[ev[ind].ss] = 1;
			} else {
				se.erase(se.find(wei[ev[ind].ss]));
			}
			ind++;
		}
		assert(se.size() == n - 1);
		ll ans = 0;
		for (int j:se) ans += abs(j - que[i]);
		cout << ans << "\n";
	}
	//for (int i = m - 1;i >= 0;i--) debug(ed[i].u, ed[i].v, ed[i].w);
 
}

Compilation message

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:174:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  174 |   while (ind < ev.size() && ev[ind].ff <= que[i]) {
      |          ~~~~^~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from reconstruction.cpp:2:
reconstruction.cpp:183:20: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  183 |   assert(se.size() == n - 1);
      |          ~~~~~~~~~~^~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 764 ms 13076 KB Output is correct
21 Correct 737 ms 12948 KB Output is correct
22 Correct 753 ms 13320 KB Output is correct
23 Correct 774 ms 13064 KB Output is correct
24 Correct 750 ms 13152 KB Output is correct
25 Correct 758 ms 13432 KB Output is correct
26 Correct 743 ms 12996 KB Output is correct
27 Correct 736 ms 13128 KB Output is correct
28 Incorrect 467 ms 13072 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 3660 ms 29384 KB Output is correct
5 Correct 3717 ms 28080 KB Output is correct
6 Correct 3898 ms 28116 KB Output is correct
7 Correct 3857 ms 29732 KB Output is correct
8 Correct 3691 ms 29828 KB Output is correct
9 Runtime error 914 ms 32308 KB Execution killed with signal 6
10 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 2936 ms 18996 KB Output is correct
21 Correct 2881 ms 19220 KB Output is correct
22 Correct 2952 ms 19100 KB Output is correct
23 Correct 2858 ms 19288 KB Output is correct
24 Correct 2845 ms 18968 KB Output is correct
25 Correct 2972 ms 19148 KB Output is correct
26 Correct 3088 ms 19472 KB Output is correct
27 Incorrect 2764 ms 19380 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 764 ms 13076 KB Output is correct
21 Correct 737 ms 12948 KB Output is correct
22 Correct 753 ms 13320 KB Output is correct
23 Correct 774 ms 13064 KB Output is correct
24 Correct 750 ms 13152 KB Output is correct
25 Correct 758 ms 13432 KB Output is correct
26 Correct 743 ms 12996 KB Output is correct
27 Correct 736 ms 13128 KB Output is correct
28 Incorrect 467 ms 13072 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 764 ms 13076 KB Output is correct
21 Correct 737 ms 12948 KB Output is correct
22 Correct 753 ms 13320 KB Output is correct
23 Correct 774 ms 13064 KB Output is correct
24 Correct 750 ms 13152 KB Output is correct
25 Correct 758 ms 13432 KB Output is correct
26 Correct 743 ms 12996 KB Output is correct
27 Correct 736 ms 13128 KB Output is correct
28 Incorrect 467 ms 13072 KB Output isn't correct
29 Halted 0 ms 0 KB -