Submission #734178

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
734178	2023-05-02T03:27:45 Z	QwertyPi	Reconstruction Project (JOI22_reconstruction)	C++14	3 / 100	5000 ms	32012 KB

reconstruction

#include <bits/stdc++.h>
#define int long long
using namespace std;

struct Edge{
	int u, v, w;
	bool operator< (const Edge& o) const {
		return w < o.w;
	}
};

const int N = 501, B = 500, M = 1e5 + 11;
vector<Edge> E, EM[M / B + 11], EL[M / B + 11], ER[M / B + 11];

struct DSU{
	int dsu[N];
	void in(){
		for(int i = 0; i < N; i++){
			dsu[i] = i;
		}
	}
	DSU(){
		in();
	}
	int f(int x){
		return x == dsu[x] ? x : dsu[x] = f(dsu[x]);
	}
	bool g(int x, int y){
		x = f(x), y = f(y);
		if(x == y) return false;
		dsu[x] = y;
		return true;
	}
};
int32_t main(){
	cin.tie(0); cout.tie(0)->sync_with_stdio(false);
	int n, m; cin >> n >> m;
	for(int i = 0; i < m; i++){
		int u, v, w; cin >> u >> v >> w; 
		E.push_back({u, v, w});
	}
	sort(E.begin(), E.end());
	for(int i = 0; i < (m + B - 1) / B; i++){
		int l = i * B, r = min(m, (i + 1) * B) - 1;
		vector<Edge> CE(E.begin() + l, E.begin() + r + 1), AL;
		EM[i] = CE;
		if(i != 0) for(auto j : EL[i - 1]) CE.push_back(j);
		sort(CE.begin(), CE.end());
		DSU dsu;
		for(auto e : CE){
			if(dsu.g(e.u, e.v)){
				AL.push_back(e);
			}
		}
		EL[i] = AL;
	}
	for(int i = (m + B - 1) / B - 1; i >= 0; i--){
		int l = i * B, r = min(m, (i + 1) * B) - 1;
		vector<Edge> CE(E.begin() + l, E.begin() + r + 1), AL;
		if(i != (m + B - 1) / B - 1) for(auto j : ER[i + 1]) CE.push_back(j);
		sort(CE.begin(), CE.end(), [](Edge x, Edge y){
			return y < x;
		});
		DSU dsu;
		for(auto e : CE){
			if(dsu.g(e.u, e.v)){
				AL.push_back(e);
			}
		}
		ER[i] = AL;
	}
	vector<int> Q;
	int q; cin >> q;
	for(int i = 0; i < q; i++){
		int v; cin >> v; Q.push_back(v);
	}
	for(int i = 0; i < q; i++){
		int v = Q[i]; int idx = lower_bound(E.begin(), E.end(), Edge{-1, -1, v}) - E.begin();
		int b = idx / B;
		vector<Edge> AL;
		if(b != 0) for(auto j : EL[b - 1]) AL.push_back(j);
		for(auto j : EM[b]) AL.push_back(j);
		for(auto j : ER[b + 1]) AL.push_back(j);
		for(auto& e : AL) e.w = abs(e.w - v);
		sort(AL.begin(), AL.end());
		int ans = 0;
		DSU dsu;
		for(auto& e : AL){
			if(dsu.g(e.u, e.v)){
				ans += e.w;
			}
		}
		cout << ans << endl;
	}
}

Subtask #1
3.0 / 3.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	340 KB	Output is correct
4	Correct	1 ms	212 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	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	336 KB	Output is correct
16	Correct	1 ms	344 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	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	212 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	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	336 KB	Output is correct
16	Correct	1 ms	344 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	Incorrect	53 ms	11420 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

Subtask #3
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Execution timed out	5004 ms	32012 KB	Time limit exceeded
5	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	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	212 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	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	336 KB	Output is correct
16	Correct	1 ms	344 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	Execution timed out	5013 ms	19528 KB	Time limit exceeded
21	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	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	212 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	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	336 KB	Output is correct
16	Correct	1 ms	344 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	Incorrect	53 ms	11420 KB	Output isn't correct
21	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	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	212 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	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	336 KB	Output is correct
16	Correct	1 ms	344 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	Incorrect	53 ms	11420 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

Submission #734178

Compilation message

Subtask #1 3.0 / 3.0

Subtask #2 0 / 4.0

Subtask #3 0 / 7.0

Subtask #4 0 / 28.0

Subtask #5 0 / 35.0

Subtask #6 0 / 23.0

Subtask #1
3.0 / 3.0

Subtask #2
0 / 4.0

Subtask #3
0 / 7.0

Subtask #4
0 / 28.0

Subtask #5
0 / 35.0

Subtask #6
0 / 23.0