oj.uz

Submission #587072

# Submission time Handle Problem Language Result Execution time Memory
587072 2022-07-01T09:37:15 Z 8e7 Reconstruction Project (JOI22_reconstruction) C++17
70 / 100
 5000 ms 206012 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;

bool vis[100005];
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), f = se(v.back().ff);
	bool eq = 1;
	for (int i:e) vis[i] = 1; 
	for (int i:f) {
		if (!vis[i]) {
			eq = 0;
			break;
		}
	}
	if (eq) {
		for (pii p:v) {
			for (int i:e) ans[p.ss] += abs(wei[i] - p.ff);
		}
		for (int i:e) vis[i] = 0;
		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 2 ms 2644 KB Output is correct
4 Correct 2 ms 2656 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 1 ms 2644 KB Output is correct
10 Correct 1 ms 2644 KB Output is correct
11 Correct 1 ms 2644 KB Output is correct
12 Correct 1 ms 2644 KB Output is correct
13 Correct 1 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 2688 KB Output is correct
17 Correct 1 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 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 Correct 2 ms 2656 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 1 ms 2644 KB Output is correct
10 Correct 1 ms 2644 KB Output is correct
11 Correct 1 ms 2644 KB Output is correct
12 Correct 1 ms 2644 KB Output is correct
13 Correct 1 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 2688 KB Output is correct
17 Correct 1 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 Correct 1356 ms 201072 KB Output is correct
21 Correct 806 ms 190588 KB Output is correct
22 Correct 1175 ms 198744 KB Output is correct
23 Correct 1252 ms 200500 KB Output is correct
24 Correct 1178 ms 200808 KB Output is correct
25 Correct 1276 ms 201012 KB Output is correct
26 Correct 1325 ms 200956 KB Output is correct
27 Correct 1371 ms 200988 KB Output is correct
28 Correct 1487 ms 201136 KB Output is correct
29 Correct 1424 ms 200980 KB Output is correct
30 Correct 1470 ms 201032 KB Output is correct
31 Correct 1395 ms 201036 KB Output is correct
32 Correct 1461 ms 200964 KB Output is correct
33 Correct 1488 ms 200980 KB Output is correct
34 Correct 1456 ms 200936 KB Output is correct
35 Correct 1536 ms 201060 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 2668 KB Output is correct
4 Execution timed out 5057 ms 206012 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 2 ms 2644 KB Output is correct
4 Correct 2 ms 2656 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 1 ms 2644 KB Output is correct
10 Correct 1 ms 2644 KB Output is correct
11 Correct 1 ms 2644 KB Output is correct
12 Correct 1 ms 2644 KB Output is correct
13 Correct 1 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 2688 KB Output is correct
17 Correct 1 ms 2644 KB Output is correct
18 Correct 2 ms 2644 KB Output is correct
19 Correct 1 ms 2644 KB Output is correct
20 Correct 1259 ms 28496 KB Output is correct
21 Correct 1156 ms 28788 KB Output is correct
22 Correct 1156 ms 28680 KB Output is correct
23 Correct 1189 ms 28712 KB Output is correct
24 Correct 1158 ms 28724 KB Output is correct
25 Correct 1121 ms 28904 KB Output is correct
26 Correct 1053 ms 28956 KB Output is correct
27 Correct 763 ms 32776 KB Output is correct
28 Correct 1164 ms 28592 KB Output is correct
29 Correct 1104 ms 28888 KB Output is correct
30 Correct 941 ms 28928 KB Output is correct
31 Correct 940 ms 28688 KB Output is correct
32 Correct 742 ms 31836 KB Output is correct
33 Correct 732 ms 55412 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 2 ms 2644 KB Output is correct
4 Correct 2 ms 2656 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 1 ms 2644 KB Output is correct
10 Correct 1 ms 2644 KB Output is correct
11 Correct 1 ms 2644 KB Output is correct
12 Correct 1 ms 2644 KB Output is correct
13 Correct 1 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 2688 KB Output is correct
17 Correct 1 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 Correct 1356 ms 201072 KB Output is correct
21 Correct 806 ms 190588 KB Output is correct
22 Correct 1175 ms 198744 KB Output is correct
23 Correct 1252 ms 200500 KB Output is correct
24 Correct 1178 ms 200808 KB Output is correct
25 Correct 1276 ms 201012 KB Output is correct
26 Correct 1325 ms 200956 KB Output is correct
27 Correct 1371 ms 200988 KB Output is correct
28 Correct 1487 ms 201136 KB Output is correct
29 Correct 1424 ms 200980 KB Output is correct
30 Correct 1470 ms 201032 KB Output is correct
31 Correct 1395 ms 201036 KB Output is correct
32 Correct 1461 ms 200964 KB Output is correct
33 Correct 1488 ms 200980 KB Output is correct
34 Correct 1456 ms 200936 KB Output is correct
35 Correct 1536 ms 201060 KB Output is correct
36 Correct 2134 ms 201668 KB Output is correct
37 Correct 1430 ms 192368 KB Output is correct
38 Correct 1906 ms 199260 KB Output is correct
39 Correct 1951 ms 201108 KB Output is correct
40 Correct 2013 ms 201364 KB Output is correct
41 Correct 2382 ms 201464 KB Output is correct
42 Correct 2448 ms 201524 KB Output is correct
43 Correct 2437 ms 201516 KB Output is correct
44 Correct 2043 ms 201560 KB Output is correct
45 Correct 1362 ms 201648 KB Output is correct
46 Correct 2172 ms 201780 KB Output is correct
47 Correct 2144 ms 201596 KB Output is correct
48 Correct 2267 ms 201576 KB Output is correct
49 Correct 2446 ms 201488 KB Output is correct
50 Correct 1431 ms 201872 KB Output is correct
51 Correct 1375 ms 202344 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 2 ms 2644 KB Output is correct
4 Correct 2 ms 2656 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 1 ms 2644 KB Output is correct
10 Correct 1 ms 2644 KB Output is correct
11 Correct 1 ms 2644 KB Output is correct
12 Correct 1 ms 2644 KB Output is correct
13 Correct 1 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 2688 KB Output is correct
17 Correct 1 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 Correct 1356 ms 201072 KB Output is correct
21 Correct 806 ms 190588 KB Output is correct
22 Correct 1175 ms 198744 KB Output is correct
23 Correct 1252 ms 200500 KB Output is correct
24 Correct 1178 ms 200808 KB Output is correct
25 Correct 1276 ms 201012 KB Output is correct
26 Correct 1325 ms 200956 KB Output is correct
27 Correct 1371 ms 200988 KB Output is correct
28 Correct 1487 ms 201136 KB Output is correct
29 Correct 1424 ms 200980 KB Output is correct
30 Correct 1470 ms 201032 KB Output is correct
31 Correct 1395 ms 201036 KB Output is correct
32 Correct 1461 ms 200964 KB Output is correct
33 Correct 1488 ms 200980 KB Output is correct
34 Correct 1456 ms 200936 KB Output is correct
35 Correct 1536 ms 201060 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 2668 KB Output is correct
39 Execution timed out 5057 ms 206012 KB Time limit exceeded
40 Halted 0 ms 0 KB -