oj.uz

Submission #587060

# Submission time Handle Problem Language Result Execution time Memory
587060 2022-07-01T09:31:18 Z 8e7 Reconstruction Project (JOI22_reconstruction) C++17
70 / 100
 5000 ms 206016 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 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;
	edge(){u = v = w = 0;}
	edge(int a, int b, int c){u = a, v = b, w = c;}
};

inline void del(vector<pii> &v, pii x) {
	v.erase(find(v.begin(), v.end(), x));
}
inline void del(vector<int> &v, int x) {
	v.erase(find(v.begin(), v.end(), x));
}
struct graph{
	vector<int> ed; //first < second
	vector<pii> adj[maxn];
	pii best;
	int bid, t;
	void init(int n) {
		ed.clear();
		t = 0;
		for (int i = 0;i <= n;i++) adj[i].clear();
	}
	bool getpath(int n, int par, int goal) {
		if (n == goal) return 1;
		for (auto [v, id]:adj[n]) {
			if (v != par && getpath(v, n, goal)) {
				if (id < bid) {
					bid = id;
					best = {n, v};
				}
				return 1;
			}
		}
		return 0;
	}
	void upd(int u, int v) {
		bid = inf;
		t++;
		if (u > v) swap(u, v);
		if (getpath(u, 0, v)) {
			if (best.ff > best.ss) swap(best.ff, best.ss);	
			del(adj[best.ff], make_pair(best.ss, bid));
			del(adj[best.ss], make_pair(best.ff, bid));
			del(ed, bid);
		}
		adj[u].push_back({v, t});
		adj[v].push_back({u, t});
		ed.push_back(t);
	}
} g;
vector<int> tree[100005];


struct DSU{
	int par[maxn], siz[maxn];	
	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 : (par[a] = find(par[a]));
	}
	bool Union(int a, int b) {
		a = find(a), b = find(b);
		if (a == b) return 0;
		if (siz[a] < siz[b]) par[a] = b;
		else par[b] = a;
		return 1;
	}
} dsu;
vector<int> wei;
vector<edge> ed;

ll ans[1000005];
int n, m;
vector<int> L, R;
vector<int> se(int x) {
	int st = (int)R.size() - 1;
	int l = (int)L.size() - 1;
	dsu.init(n);
	vector<int> ret;
	for (;st >= 0;st--) {
		int ir = R[st], il = 0;
		if (l >= 0) il = L[l];
		while (l >= 0 && x - wei[il] <= wei[ir] - x) {
			if (dsu.Union(ed[il].u, ed[il].v)) ret.push_back(il);
			l--;
			if (l >= 0) il = L[l];
		}
		if (dsu.Union(ed[ir].u, ed[ir].v)) ret.push_back(ir);
	}
	while (l >= 0) {
		int il = L[l];
		if (dsu.Union(ed[il].u, ed[il].v)) ret.push_back(il);
		l--;
	}
	sort(ret.begin(), ret.end());
	return ret;
}
void solve(vector<pii> v) {
	if (v.size() == 0) return;
	if (v.size() == 1) {
		vector<int> e = se(v[0].ff);
		for (int i:e) ans[v[0].ss] += abs(wei[i] - v[0].ff);
		return;
	}
	vector<int> e = se(v[0].ff);
	if (e == se(v.back().ff)) {
		for (pii p:v) {
			for (int i:e) ans[p.ss] += abs(wei[i] - p.ff);
		}
		return;
	}
	vector<pii> lef(v.begin(), v.begin() + (v.size() / 2));
	vector<pii> rig(v.begin() + (v.size()/2), v.end());
	solve(lef);
	solve(rig);
}
int main() {
	io
	cin >> n >> m;
	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));	
	}
	sort(ed.begin(), ed.end(), [&] (edge x, edge y){return x.w < y.w;});
	sort(wei.begin(), wei.end());
 
	int q;
	cin >> q;
	vector<int> que(q);
	for (int i = 0;i < q;i++) {
		cin >> que[i];
	}
	//for (int i = m - 1;i >= 0;i--) debug(ed[i].u, ed[i].v, ed[i].w);
 
	g.init(n);
	for (int i = m - 1;i >= 0;i--) {
		g.upd(ed[i].u, ed[i].v);
		tree[i] = g.ed;
	}
	g.init(n);
	int ind = 0;
	auto answer = [&] (int LIM, int id) {
		vector<pii> qi;
		while (ind < q && que[ind] < LIM) {
			qi.push_back({que[ind], ind});
			ind++;
		}
		L = g.ed, R = tree[id];
		for (int &i:R) i = m - i;
		for (int &i:L) i--;
		solve(qi);
	};
	for (int i = 0;i < m;i++) {	
		answer(ed[i].w, i);
		g.upd(ed[i].u, ed[i].v);
	}
	answer(inf, m);
	for (int i = 0;i < q;i++) cout << ans[i] << "\n";	
}

Subtask #1
3.0 / 3.0

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

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 2696 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 2 ms 2696 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 2 ms 2692 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 1 ms 2644 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct
17 Correct 3 ms 2644 KB Output is correct
18 Correct 2 ms 2676 KB Output is correct
19 Correct 2 ms 2692 KB Output is correct
20 Correct 1424 ms 201396 KB Output is correct
21 Correct 880 ms 190948 KB Output is correct
22 Correct 1180 ms 199160 KB Output is correct
23 Correct 1249 ms 200952 KB Output is correct
24 Correct 1139 ms 201320 KB Output is correct
25 Correct 1322 ms 201364 KB Output is correct
26 Correct 1344 ms 201372 KB Output is correct
27 Correct 1410 ms 201456 KB Output is correct
28 Correct 1409 ms 201580 KB Output is correct
29 Correct 1336 ms 201556 KB Output is correct
30 Correct 1374 ms 201408 KB Output is correct
31 Correct 1332 ms 201340 KB Output is correct
32 Correct 1392 ms 201348 KB Output is correct
33 Correct 1369 ms 201380 KB Output is correct
34 Correct 1360 ms 201524 KB Output is correct
35 Correct 1351 ms 201532 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Execution timed out 5021 ms 206016 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 2696 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 2 ms 2696 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 2 ms 2692 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 1 ms 2644 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct
17 Correct 3 ms 2644 KB Output is correct
18 Correct 2 ms 2676 KB Output is correct
19 Correct 2 ms 2644 KB Output is correct
20 Correct 1405 ms 28912 KB Output is correct
21 Correct 1355 ms 28656 KB Output is correct
22 Correct 1448 ms 28756 KB Output is correct
23 Correct 1441 ms 28664 KB Output is correct
24 Correct 1362 ms 28832 KB Output is correct
25 Correct 1299 ms 28764 KB Output is correct
26 Correct 1196 ms 28896 KB Output is correct
27 Correct 749 ms 32672 KB Output is correct
28 Correct 1330 ms 28608 KB Output is correct
29 Correct 1307 ms 28860 KB Output is correct
30 Correct 1020 ms 29076 KB Output is correct
31 Correct 1044 ms 28704 KB Output is correct
32 Correct 741 ms 31836 KB Output is correct
33 Correct 799 ms 55284 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 2696 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 2 ms 2696 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 2 ms 2692 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 1 ms 2644 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct
17 Correct 3 ms 2644 KB Output is correct
18 Correct 2 ms 2676 KB Output is correct
19 Correct 2 ms 2692 KB Output is correct
20 Correct 1424 ms 201396 KB Output is correct
21 Correct 880 ms 190948 KB Output is correct
22 Correct 1180 ms 199160 KB Output is correct
23 Correct 1249 ms 200952 KB Output is correct
24 Correct 1139 ms 201320 KB Output is correct
25 Correct 1322 ms 201364 KB Output is correct
26 Correct 1344 ms 201372 KB Output is correct
27 Correct 1410 ms 201456 KB Output is correct
28 Correct 1409 ms 201580 KB Output is correct
29 Correct 1336 ms 201556 KB Output is correct
30 Correct 1374 ms 201408 KB Output is correct
31 Correct 1332 ms 201340 KB Output is correct
32 Correct 1392 ms 201348 KB Output is correct
33 Correct 1369 ms 201380 KB Output is correct
34 Correct 1360 ms 201524 KB Output is correct
35 Correct 1351 ms 201532 KB Output is correct
36 Correct 2787 ms 201808 KB Output is correct
37 Correct 1953 ms 192984 KB Output is correct
38 Correct 2395 ms 199956 KB Output is correct
39 Correct 2350 ms 201792 KB Output is correct
40 Correct 2363 ms 202268 KB Output is correct
41 Correct 2667 ms 202232 KB Output is correct
42 Correct 2724 ms 202184 KB Output is correct
43 Correct 2720 ms 202312 KB Output is correct
44 Correct 2157 ms 202240 KB Output is correct
45 Correct 1370 ms 202368 KB Output is correct
46 Correct 2577 ms 202300 KB Output is correct
47 Correct 2561 ms 202324 KB Output is correct
48 Correct 2635 ms 202252 KB Output is correct
49 Correct 2649 ms 202288 KB Output is correct
50 Correct 1380 ms 202580 KB Output is correct
51 Correct 1366 ms 203172 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 2696 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 2 ms 2696 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 2 ms 2692 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 1 ms 2644 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct
17 Correct 3 ms 2644 KB Output is correct
18 Correct 2 ms 2676 KB Output is correct
19 Correct 2 ms 2692 KB Output is correct
20 Correct 1424 ms 201396 KB Output is correct
21 Correct 880 ms 190948 KB Output is correct
22 Correct 1180 ms 199160 KB Output is correct
23 Correct 1249 ms 200952 KB Output is correct
24 Correct 1139 ms 201320 KB Output is correct
25 Correct 1322 ms 201364 KB Output is correct
26 Correct 1344 ms 201372 KB Output is correct
27 Correct 1410 ms 201456 KB Output is correct
28 Correct 1409 ms 201580 KB Output is correct
29 Correct 1336 ms 201556 KB Output is correct
30 Correct 1374 ms 201408 KB Output is correct
31 Correct 1332 ms 201340 KB Output is correct
32 Correct 1392 ms 201348 KB Output is correct
33 Correct 1369 ms 201380 KB Output is correct
34 Correct 1360 ms 201524 KB Output is correct
35 Correct 1351 ms 201532 KB Output is correct
36 Correct 1 ms 2644 KB Output is correct
37 Correct 2 ms 2644 KB Output is correct
38 Correct 2 ms 2644 KB Output is correct
39 Execution timed out 5021 ms 206016 KB Time limit exceeded
40 Halted 0 ms 0 KB -