oj.uz

Submission #1020833

# Submission time Handle Problem Language Result Execution time Memory
1020833 2024-07-12T10:21:36 Z Unforgettablepl Reconstruction Project (JOI22_reconstruction) C++17
70 / 100
 5000 ms 23052 KB 
#pragma GCC optimize("Ofast","unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int INF = 1e15;

struct UFDS{
	vector<int> p,siz;
	UFDS(int n):p(n+1),siz(n+1,1){iota(p.begin(),p.end(),0);}
	int findRoot(int x){
		return p[x]==x ? x : p[x]=findRoot(p[x]);
	}
	bool unite(int a,int b){
		a = findRoot(a);
		b = findRoot(b);
		if(a==b)return false;
		if(siz[a]<siz[b])swap(a,b);
		siz[a]+=siz[b];
		p[b]=a;
		return true;
	}
};

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin >> n >> m;
	vector<pair<int,pair<int,int>>> edges(m);
	for(auto&[a,b]:edges)cin>>b.first>>b.second>>a;
	sort(edges.begin(),edges.end());
	vector<set<pair<int,int>>> adj;
	vector<int> replaces_front(m,-1);
	{
		// Calculation from the front
		adj = vector<set<pair<int,int>>>(n+1);
		int tar;
		function<pair<bool,int>(int,int)> dfs = [&](int x,int p){
			if(x==tar)return make_pair(true,(int)1e15);
			for(auto[v,i]:adj[x])if(v!=p){
				auto res = dfs(v,x);
				if(res.first)return make_pair(true,min(res.second,i));
			}
			return make_pair(false,(int)0);
		};
		for(int i=0;i<m;i++){
			tar = edges[i].second.second;
			auto res = dfs(edges[i].second.first,-1);
			if(res.first){
				adj[edges[res.second].second.first].erase({edges[res.second].second.second,res.second});
				adj[edges[res.second].second.second].erase({edges[res.second].second.first,res.second});
				replaces_front[i] = res.second;
			}
			adj[edges[i].second.first].insert({edges[i].second.second,i});
			adj[edges[i].second.second].insert({edges[i].second.first,i});
		}
	}
	vector<int> replaces_back(m,-1);
	{
		// Calculation from the back
		adj = vector<set<pair<int,int>>>(n+1);
		int tar;
		function<pair<bool,int>(int,int)> dfs = [&](int x,int p){
			if(x==tar)return make_pair(true,(int)-1);
			for(auto[v,i]:adj[x])if(v!=p){
				auto res = dfs(v,x);
				if(res.first)return make_pair(true,max(res.second,i));
			}
			return make_pair(false,(int)0);
		};
		for(int i=m-1;i>=0;i--){
			tar = edges[i].second.second;
			auto res = dfs(edges[i].second.first,-1);
			if(res.first){
				adj[edges[res.second].second.first].erase({edges[res.second].second.second,res.second});
				adj[edges[res.second].second.second].erase({edges[res.second].second.first,res.second});
				replaces_back[i] = res.second;
			}
			adj[edges[i].second.first].insert({edges[i].second.second,i});
			adj[edges[i].second.second].insert({edges[i].second.first,i});
		}
	}
	set<int> curr_left;
	set<int> curr_right;
	vector<pair<int,int>> curredgesl;
	vector<pair<int,int>> curredgesr;
	bool changed;
	for(auto&i:adj)for(auto[a,b]:i)curr_right.insert(b);
	for(int i:curr_right)curredgesr.emplace_back(0,i);
	vector<bool> blacklist(m+1);
	auto solve = [&](int x){
		if(changed){
			curredgesl.clear();
			for(int i:curr_left){
				curredgesl.emplace_back(x-edges[i].first,i);
			}
			sort(curredgesl.begin(),curredgesl.end());
			curredgesr.clear();
			for(int i:curr_right){
				curredgesr.emplace_back(edges[i].first-x,i);
			}
			sort(curredgesr.begin(),curredgesr.end());
		} else {
			for(auto&[c,i]:curredgesl)c=x-edges[i].first;
			for(auto&[c,i]:curredgesr)c=edges[i].first-x;
		}
		for(auto[c,i]:curredgesl)blacklist[i+1]=false;
		for(auto[c,i]:curredgesr)blacklist[i+1]=false;
		auto iterl = curredgesl.begin();
		auto iterr = curredgesr.begin();
		int ans = 0;
		int cnt = 1;
		while(cnt<n){
			if(iterl==curredgesl.end()){
				if(!blacklist[iterr->second+1]){
					ans+=iterr->first;
					blacklist[replaces_front[iterr->second]+1]=true;
					cnt++;
				}
				iterr++;
			} else if(iterr==curredgesr.end()){
				if(!blacklist[iterl->second+1]){
					ans+=iterl->first;
					blacklist[replaces_back[iterl->second]+1]=true;
					cnt++;
				}
				iterl++;
			} else if(iterl->first<iterr->first){
				if(!blacklist[iterl->second+1]){
					ans+=iterl->first;
					blacklist[replaces_back[iterl->second]+1]=true;
					cnt++;
				}
				iterl++;
			} else {
				if(!blacklist[iterr->second+1]){
					ans+=iterr->first;
					blacklist[replaces_front[iterr->second]+1]=true;
					cnt++;
				}
				iterr++;
			}
		}
		return ans;
	};
	int iter = 0;
	int q;
	cin >> q;
	for(int i=1;i<=q;i++){
		int query;
		cin >> query;
		changed = false;
		while(iter!=m and edges[iter].first<query){
			curr_right.erase(iter);
			if(replaces_back[iter]!=-1){
				curr_right.insert(replaces_back[iter]);
			}
			curr_left.insert(iter);
			if(replaces_front[iter]!=-1){
				curr_left.erase(replaces_front[iter]);
			}
			iter++;
			changed = true;
		}
		cout << solve(query) << '\n';
	}
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 460 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 456 KB Output is correct
5 Correct 0 ms 456 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 388 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 460 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 456 KB Output is correct
5 Correct 0 ms 456 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 388 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 832 ms 6184 KB Output is correct
21 Correct 427 ms 6140 KB Output is correct
22 Correct 635 ms 6224 KB Output is correct
23 Correct 700 ms 6136 KB Output is correct
24 Correct 729 ms 6184 KB Output is correct
25 Correct 802 ms 6248 KB Output is correct
26 Correct 842 ms 6144 KB Output is correct
27 Correct 874 ms 6116 KB Output is correct
28 Correct 889 ms 6224 KB Output is correct
29 Correct 663 ms 6116 KB Output is correct
30 Correct 854 ms 6184 KB Output is correct
31 Correct 868 ms 6144 KB Output is correct
32 Correct 897 ms 6244 KB Output is correct
33 Correct 948 ms 6228 KB Output is correct
34 Correct 419 ms 6224 KB Output is correct
35 Correct 969 ms 6136 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Execution timed out 5035 ms 17464 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 460 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 456 KB Output is correct
5 Correct 0 ms 456 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 388 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 3071 ms 22332 KB Output is correct
21 Correct 3030 ms 22608 KB Output is correct
22 Correct 3223 ms 22388 KB Output is correct
23 Correct 2947 ms 22476 KB Output is correct
24 Correct 2837 ms 22596 KB Output is correct
25 Correct 2804 ms 22568 KB Output is correct
26 Correct 2870 ms 22496 KB Output is correct
27 Correct 2821 ms 22596 KB Output is correct
28 Correct 2935 ms 22420 KB Output is correct
29 Correct 2857 ms 22532 KB Output is correct
30 Correct 3174 ms 22536 KB Output is correct
31 Correct 2834 ms 22376 KB Output is correct
32 Correct 2056 ms 23052 KB Output is correct
33 Correct 3189 ms 22592 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 460 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 456 KB Output is correct
5 Correct 0 ms 456 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 388 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 832 ms 6184 KB Output is correct
21 Correct 427 ms 6140 KB Output is correct
22 Correct 635 ms 6224 KB Output is correct
23 Correct 700 ms 6136 KB Output is correct
24 Correct 729 ms 6184 KB Output is correct
25 Correct 802 ms 6248 KB Output is correct
26 Correct 842 ms 6144 KB Output is correct
27 Correct 874 ms 6116 KB Output is correct
28 Correct 889 ms 6224 KB Output is correct
29 Correct 663 ms 6116 KB Output is correct
30 Correct 854 ms 6184 KB Output is correct
31 Correct 868 ms 6144 KB Output is correct
32 Correct 897 ms 6244 KB Output is correct
33 Correct 948 ms 6228 KB Output is correct
34 Correct 419 ms 6224 KB Output is correct
35 Correct 969 ms 6136 KB Output is correct
36 Correct 1258 ms 6628 KB Output is correct
37 Correct 839 ms 6504 KB Output is correct
38 Correct 1020 ms 6632 KB Output is correct
39 Correct 1066 ms 6628 KB Output is correct
40 Correct 1086 ms 6452 KB Output is correct
41 Correct 1189 ms 6632 KB Output is correct
42 Correct 1202 ms 6624 KB Output is correct
43 Correct 1243 ms 6484 KB Output is correct
44 Correct 944 ms 6628 KB Output is correct
45 Correct 677 ms 6632 KB Output is correct
46 Correct 1191 ms 6736 KB Output is correct
47 Correct 1180 ms 6680 KB Output is correct
48 Correct 1203 ms 6496 KB Output is correct
49 Correct 1152 ms 6596 KB Output is correct
50 Correct 435 ms 6740 KB Output is correct
51 Correct 887 ms 6480 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 460 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 456 KB Output is correct
5 Correct 0 ms 456 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 388 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 832 ms 6184 KB Output is correct
21 Correct 427 ms 6140 KB Output is correct
22 Correct 635 ms 6224 KB Output is correct
23 Correct 700 ms 6136 KB Output is correct
24 Correct 729 ms 6184 KB Output is correct
25 Correct 802 ms 6248 KB Output is correct
26 Correct 842 ms 6144 KB Output is correct
27 Correct 874 ms 6116 KB Output is correct
28 Correct 889 ms 6224 KB Output is correct
29 Correct 663 ms 6116 KB Output is correct
30 Correct 854 ms 6184 KB Output is correct
31 Correct 868 ms 6144 KB Output is correct
32 Correct 897 ms 6244 KB Output is correct
33 Correct 948 ms 6228 KB Output is correct
34 Correct 419 ms 6224 KB Output is correct
35 Correct 969 ms 6136 KB Output is correct
36 Correct 1 ms 600 KB Output is correct
37 Correct 1 ms 344 KB Output is correct
38 Correct 1 ms 344 KB Output is correct
39 Execution timed out 5035 ms 17464 KB Time limit exceeded
40 Halted 0 ms 0 KB -