oj.uz

Submission #587066

# Submission time Handle Problem Language Result Execution time Memory
587066 2022-07-01T09:34:07 Z 8e7 Reconstruction Project (JOI22_reconstruction) C++17
42 / 100
 5000 ms 205604 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 2 ms 2644 KB Output is correct
2 Correct 2 ms 2700 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 1 ms 2692 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 1 ms 2696 KB Output is correct
10 Correct 1 ms 2688 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 2 ms 2696 KB Output is correct
16 Correct 2 ms 2692 KB Output is correct
17 Correct 2 ms 2644 KB Output is correct
18 Correct 2 ms 2644 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2700 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 1 ms 2692 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 1 ms 2696 KB Output is correct
10 Correct 1 ms 2688 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 2 ms 2696 KB Output is correct
16 Correct 2 ms 2692 KB Output is correct
17 Correct 2 ms 2644 KB Output is correct
18 Correct 2 ms 2644 KB Output is correct
19 Correct 2 ms 2688 KB Output is correct
20 Correct 1400 ms 201448 KB Output is correct
21 Correct 783 ms 190984 KB Output is correct
22 Correct 1178 ms 199072 KB Output is correct
23 Correct 1191 ms 200884 KB Output is correct
24 Correct 1118 ms 201204 KB Output is correct
25 Correct 1318 ms 201296 KB Output is correct
26 Correct 1319 ms 201432 KB Output is correct
27 Correct 1330 ms 201308 KB Output is correct
28 Correct 1323 ms 201552 KB Output is correct
29 Correct 1461 ms 201432 KB Output is correct
30 Correct 1421 ms 201336 KB Output is correct
31 Correct 1429 ms 201436 KB Output is correct
32 Correct 1446 ms 201420 KB Output is correct
33 Correct 1328 ms 201392 KB Output is correct
34 Correct 1324 ms 201304 KB Output is correct
35 Correct 1315 ms 201512 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 5105 ms 205604 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2700 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 1 ms 2692 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 1 ms 2696 KB Output is correct
10 Correct 1 ms 2688 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 2 ms 2696 KB Output is correct
16 Correct 2 ms 2692 KB Output is correct
17 Correct 2 ms 2644 KB Output is correct
18 Correct 2 ms 2644 KB Output is correct
19 Correct 2 ms 2644 KB Output is correct
20 Execution timed out 5018 ms 10872 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2700 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 1 ms 2692 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 1 ms 2696 KB Output is correct
10 Correct 1 ms 2688 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 2 ms 2696 KB Output is correct
16 Correct 2 ms 2692 KB Output is correct
17 Correct 2 ms 2644 KB Output is correct
18 Correct 2 ms 2644 KB Output is correct
19 Correct 2 ms 2688 KB Output is correct
20 Correct 1400 ms 201448 KB Output is correct
21 Correct 783 ms 190984 KB Output is correct
22 Correct 1178 ms 199072 KB Output is correct
23 Correct 1191 ms 200884 KB Output is correct
24 Correct 1118 ms 201204 KB Output is correct
25 Correct 1318 ms 201296 KB Output is correct
26 Correct 1319 ms 201432 KB Output is correct
27 Correct 1330 ms 201308 KB Output is correct
28 Correct 1323 ms 201552 KB Output is correct
29 Correct 1461 ms 201432 KB Output is correct
30 Correct 1421 ms 201336 KB Output is correct
31 Correct 1429 ms 201436 KB Output is correct
32 Correct 1446 ms 201420 KB Output is correct
33 Correct 1328 ms 201392 KB Output is correct
34 Correct 1324 ms 201304 KB Output is correct
35 Correct 1315 ms 201512 KB Output is correct
36 Correct 2262 ms 201652 KB Output is correct
37 Correct 1465 ms 192088 KB Output is correct
38 Correct 1892 ms 199140 KB Output is correct
39 Correct 1977 ms 201164 KB Output is correct
40 Correct 1988 ms 201332 KB Output is correct
41 Correct 2166 ms 201392 KB Output is correct
42 Correct 2233 ms 201504 KB Output is correct
43 Correct 2301 ms 201432 KB Output is correct
44 Correct 1976 ms 201488 KB Output is correct
45 Correct 1420 ms 201756 KB Output is correct
46 Correct 2446 ms 201400 KB Output is correct
47 Correct 2521 ms 201416 KB Output is correct
48 Correct 2501 ms 201520 KB Output is correct
49 Correct 2401 ms 201420 KB Output is correct
50 Correct 1361 ms 201932 KB Output is correct
51 Correct 1673 ms 202372 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2700 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 1 ms 2692 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 1 ms 2696 KB Output is correct
10 Correct 1 ms 2688 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 2 ms 2696 KB Output is correct
16 Correct 2 ms 2692 KB Output is correct
17 Correct 2 ms 2644 KB Output is correct
18 Correct 2 ms 2644 KB Output is correct
19 Correct 2 ms 2688 KB Output is correct
20 Correct 1400 ms 201448 KB Output is correct
21 Correct 783 ms 190984 KB Output is correct
22 Correct 1178 ms 199072 KB Output is correct
23 Correct 1191 ms 200884 KB Output is correct
24 Correct 1118 ms 201204 KB Output is correct
25 Correct 1318 ms 201296 KB Output is correct
26 Correct 1319 ms 201432 KB Output is correct
27 Correct 1330 ms 201308 KB Output is correct
28 Correct 1323 ms 201552 KB Output is correct
29 Correct 1461 ms 201432 KB Output is correct
30 Correct 1421 ms 201336 KB Output is correct
31 Correct 1429 ms 201436 KB Output is correct
32 Correct 1446 ms 201420 KB Output is correct
33 Correct 1328 ms 201392 KB Output is correct
34 Correct 1324 ms 201304 KB Output is correct
35 Correct 1315 ms 201512 KB Output is correct
36 Correct 2 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 5105 ms 205604 KB Time limit exceeded
40 Halted 0 ms 0 KB -