oj.uz

Submission #586985

# Submission time Handle Problem Language Result Execution time Memory
586985 2022-07-01T07:35:04 Z 8e7 Reconstruction Project (JOI22_reconstruction) C++17
42 / 100
 5000 ms 217820 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];	
	void init(int n) {
		for (int i = 1;i <= n;i++) par[i] = i;
	}
	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;
		par[a] = b;
		return 1;
	}
} dsu;
int main() {
	io
	int n, m;
	cin >> n >> m;
	vector<edge> ed;
	for (int i = 0;i < m;i++) {
		int u, v, w;
		cin >> u >> v >> w;
		ed.push_back(edge(u, v, w));	
	}
	sort(ed.begin(), ed.end(), [&] (edge x, edge y){return x.w < y.w;});

	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 L, int id) {
		while (ind < q && que[ind] < L) {
			ll ans = 0;
			vector<int> &lef = g.ed, &rig = tree[id];
			dsu.init(n);
			int p = (int)rig.size() - 1;

			auto addedge = [&] (edge &e) {
				if (dsu.Union(e.u, e.v)) ans += abs(e.w - que[ind]);
			};
			for (int i = (int)lef.size()-1;i >= 0;i--) {
				while (p >= 0 && abs(ed[m-rig[p]].w-que[ind]) < abs(ed[lef[i]-1].w-que[ind])) {
					addedge(ed[m-rig[p]]);
					p--;
				}
				addedge(ed[lef[i]-1]);
			}
			while (p >= 0) {
				addedge(ed[m-rig[p]]);
				p--;
			}
			cout << ans << "\n";	
			ind++;
		}
	};
	for (int i = 0;i < m;i++) {	
		answer(ed[i].w, i);
		g.upd(ed[i].u, ed[i].v);
	}
	answer(inf, m);
}

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 2688 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 2688 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Correct 2 ms 2692 KB Output is correct
10 Correct 1 ms 2644 KB Output is correct
11 Correct 2 ms 2692 KB Output is correct
12 Correct 2 ms 2688 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 1 ms 2692 KB Output is correct
15 Correct 2 ms 2644 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct
17 Correct 2 ms 2644 KB Output is correct
18 Correct 1 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 2688 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 2688 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Correct 2 ms 2692 KB Output is correct
10 Correct 1 ms 2644 KB Output is correct
11 Correct 2 ms 2692 KB Output is correct
12 Correct 2 ms 2688 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 1 ms 2692 KB Output is correct
15 Correct 2 ms 2644 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct
17 Correct 2 ms 2644 KB Output is correct
18 Correct 1 ms 2644 KB Output is correct
19 Correct 2 ms 2644 KB Output is correct
20 Correct 1371 ms 202240 KB Output is correct
21 Correct 762 ms 191836 KB Output is correct
22 Correct 1105 ms 200012 KB Output is correct
23 Correct 1185 ms 201788 KB Output is correct
24 Correct 1122 ms 202096 KB Output is correct
25 Correct 1238 ms 202228 KB Output is correct
26 Correct 1290 ms 202292 KB Output is correct
27 Correct 1325 ms 202148 KB Output is correct
28 Correct 1290 ms 202300 KB Output is correct
29 Correct 1287 ms 202272 KB Output is correct
30 Correct 1298 ms 202280 KB Output is correct
31 Correct 1311 ms 202240 KB Output is correct
32 Correct 1288 ms 202288 KB Output is correct
33 Correct 1281 ms 202312 KB Output is correct
34 Correct 1291 ms 202336 KB Output is correct
35 Correct 1298 ms 202288 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 2672 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Execution timed out 5104 ms 217820 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 2688 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 2688 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Correct 2 ms 2692 KB Output is correct
10 Correct 1 ms 2644 KB Output is correct
11 Correct 2 ms 2692 KB Output is correct
12 Correct 2 ms 2688 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 1 ms 2692 KB Output is correct
15 Correct 2 ms 2644 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct
17 Correct 2 ms 2644 KB Output is correct
18 Correct 1 ms 2644 KB Output is correct
19 Correct 1 ms 2644 KB Output is correct
20 Execution timed out 5010 ms 22852 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 2688 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 2688 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Correct 2 ms 2692 KB Output is correct
10 Correct 1 ms 2644 KB Output is correct
11 Correct 2 ms 2692 KB Output is correct
12 Correct 2 ms 2688 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 1 ms 2692 KB Output is correct
15 Correct 2 ms 2644 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct
17 Correct 2 ms 2644 KB Output is correct
18 Correct 1 ms 2644 KB Output is correct
19 Correct 2 ms 2644 KB Output is correct
20 Correct 1371 ms 202240 KB Output is correct
21 Correct 762 ms 191836 KB Output is correct
22 Correct 1105 ms 200012 KB Output is correct
23 Correct 1185 ms 201788 KB Output is correct
24 Correct 1122 ms 202096 KB Output is correct
25 Correct 1238 ms 202228 KB Output is correct
26 Correct 1290 ms 202292 KB Output is correct
27 Correct 1325 ms 202148 KB Output is correct
28 Correct 1290 ms 202300 KB Output is correct
29 Correct 1287 ms 202272 KB Output is correct
30 Correct 1298 ms 202280 KB Output is correct
31 Correct 1311 ms 202240 KB Output is correct
32 Correct 1288 ms 202288 KB Output is correct
33 Correct 1281 ms 202312 KB Output is correct
34 Correct 1291 ms 202336 KB Output is correct
35 Correct 1298 ms 202288 KB Output is correct
36 Correct 1995 ms 202824 KB Output is correct
37 Correct 1280 ms 193388 KB Output is correct
38 Correct 1722 ms 200308 KB Output is correct
39 Correct 1768 ms 202256 KB Output is correct
40 Correct 1770 ms 202700 KB Output is correct
41 Correct 1982 ms 202700 KB Output is correct
42 Correct 1993 ms 202728 KB Output is correct
43 Correct 2013 ms 202748 KB Output is correct
44 Correct 1747 ms 202840 KB Output is correct
45 Correct 1697 ms 202840 KB Output is correct
46 Correct 1999 ms 202736 KB Output is correct
47 Correct 1990 ms 202776 KB Output is correct
48 Correct 2017 ms 202772 KB Output is correct
49 Correct 1956 ms 202840 KB Output is correct
50 Correct 1448 ms 203048 KB Output is correct
51 Correct 1620 ms 202716 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 2688 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 2688 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Correct 2 ms 2692 KB Output is correct
10 Correct 1 ms 2644 KB Output is correct
11 Correct 2 ms 2692 KB Output is correct
12 Correct 2 ms 2688 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 1 ms 2692 KB Output is correct
15 Correct 2 ms 2644 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct
17 Correct 2 ms 2644 KB Output is correct
18 Correct 1 ms 2644 KB Output is correct
19 Correct 2 ms 2644 KB Output is correct
20 Correct 1371 ms 202240 KB Output is correct
21 Correct 762 ms 191836 KB Output is correct
22 Correct 1105 ms 200012 KB Output is correct
23 Correct 1185 ms 201788 KB Output is correct
24 Correct 1122 ms 202096 KB Output is correct
25 Correct 1238 ms 202228 KB Output is correct
26 Correct 1290 ms 202292 KB Output is correct
27 Correct 1325 ms 202148 KB Output is correct
28 Correct 1290 ms 202300 KB Output is correct
29 Correct 1287 ms 202272 KB Output is correct
30 Correct 1298 ms 202280 KB Output is correct
31 Correct 1311 ms 202240 KB Output is correct
32 Correct 1288 ms 202288 KB Output is correct
33 Correct 1281 ms 202312 KB Output is correct
34 Correct 1291 ms 202336 KB Output is correct
35 Correct 1298 ms 202288 KB Output is correct
36 Correct 2 ms 2644 KB Output is correct
37 Correct 2 ms 2672 KB Output is correct
38 Correct 1 ms 2644 KB Output is correct
39 Execution timed out 5104 ms 217820 KB Time limit exceeded
40 Halted 0 ms 0 KB -