oj.uz

Submission #974738

# Submission time Handle Problem Language Result Execution time Memory
974738 2024-05-03T17:42:01 Z happy_node Reconstruction Project (JOI22_reconstruction) C++17
70 / 100
 5000 ms 436084 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
const int MX=505;
 
int N,M,Q;
 
struct DSU {
	int par[MX],sz[MX];
 
	int fd(int v) {
		return par[v]==v?v:par[v]=fd(par[v]);
	}
 
	bool merge(int u, int v) {
		u=fd(u),v=fd(v);
		if(u==v) return false;
		if(sz[u]>sz[v]) swap(u,v);
		par[u]=v;
		sz[v]+=sz[u];
		return true;
	}
 
	void reset() {
		for(int i=1;i<=N;i++) par[i]=i,sz[i]=1;
	}
} ds;
 
set<array<int,3>> adj[MX];
 
const int inf=2e9;
 
pair<int,int> bfs(int S, int T) {
	queue<int> q;
	q.push(S);
	
	vector<pair<int,int>> dist(N+1,{-1,-1});
	dist[S]={inf,inf};
 
	while(!q.empty()) {
		auto v=q.front(); q.pop();
		for(auto [u,w,ii]:adj[v]) {
			if(dist[u].first!=-1) continue;
 
			dist[u]=min(make_pair(w,ii),dist[v]);
			q.push(u);
		}
	}
 
	return dist[T];
}
 
pair<int,int> BFS(int S, int T) {
	queue<int> q;
	q.push(S);
	
	vector<pair<int,int>> dist(N+1,{-1,-1});
	dist[S]={0,0};
 
	while(!q.empty()) {
		auto v=q.front(); q.pop();
		for(auto [u,w,ii]:adj[v]) {
			if(dist[u].first!=-1) continue;
 
			dist[u]=max(make_pair(w,ii),dist[v]);
			q.push(u);
		}
	}
 
	return dist[T];
}
 
array<int,3> e[100000+5];
vector<int> PF[100000+5], SF[100000+5];
 
set<array<int,4>> E;
map<array<int,3>, int> id;
 
int L[100000+5], R[100000+5];
 
int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);
 
	cin>>N>>M;
 
	vector<array<int,4>> edges;
 
	for(int i=0;i<M;i++) {
		int u,v,w;
		cin>>u>>v>>w;
		e[i]={w,u,v};
		id[e[i]]=i;
		edges.push_back({w,u,v,i});
	}		
 
	sort(edges.begin(),edges.end());
 
	int i=0;
	for(auto [w,u,v,ID]:edges) {
		auto [ww,ii]=bfs(u,v);
		auto [WW,uu,vv]=e[ii];
		if(ww!=-1) {
			adj[uu].erase({vv,ww,ii});
			adj[vv].erase({uu,ww,ii});
			E.erase({ww,uu,vv,ii});
		}
		adj[u].insert({v,w,ID});
		adj[v].insert({u,w,ID});
		E.insert({w,u,v,ID});
		for(auto [ww,uu,vv,id]:E) {
			PF[i].push_back(id);
		}
		reverse(PF[i].begin(),PF[i].end());
 
		if(ww!=-1)
			L[ID]=(w+ww),assert(ww<=w);
		else
			L[ID]=0;
		i++;
	}
 
	reverse(edges.begin(),edges.end());
	E.clear();
	for(int i=1;i<=N;i++) adj[i].clear();
 
	i=M-1;
	for(auto [w,u,v,ID]:edges) {
		auto [ww,ii]=BFS(u,v);
		auto [WW,uu,vv]=e[ii];
		if(ww!=-1) {
			adj[uu].erase({vv,ww,ii});
			adj[vv].erase({uu,ww,ii});
			E.erase({ww,uu,vv,ii});
		}
		adj[u].insert({v,w,ID});
		adj[v].insert({u,w,ID});
		E.insert({w,u,v,ID});
		for(auto [ww,uu,vv,id]:E) {
			SF[i].push_back(id);
		}
		
		if(ww!=-1)
			R[ID]=(w+ww),assert(ww>=w);
		else
			R[ID]=2e9+1;
		i--;
	}
 
	reverse(edges.begin(),edges.end());
 
	vector<pair<int,int>> add, del;
 
	for(int i=0;i<M;i++) {
		add.push_back({L[i],i});
		del.push_back({R[i],i});
	}
 
	sort(add.begin(),add.end());
	sort(del.begin(),del.end());
 
	int pa=-1,pd=-1;
	set<int> curEdges;
 
	cin>>Q;
	for(int i=0;i<Q;i++) {
		ll x;
		cin>>x;
 
		while(pa+1<add.size() && add[pa+1].first<=2*x) {
			curEdges.insert(add[pa+1].second);
			pa++;
		} 
 
		while(pd+1<del.size() && del[pd+1].first<=2*x) {
			curEdges.erase(del[pd+1].second);
			pd++;
		}
 
		ll res=0;
		for(auto y:curEdges) res+=abs(e[y][0]-x);
 
		cout<<res<<'\n';
	}
}

Compilation message

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:170:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  170 |   while(pa+1<add.size() && add[pa+1].first<=2*x) {
      |         ~~~~^~~~~~~~~~~
reconstruction.cpp:175:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  175 |   while(pd+1<del.size() && del[pd+1].first<=2*x) {
      |         ~~~~^~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6488 KB Output is correct
13 Correct 2 ms 6492 KB Output is correct
14 Correct 2 ms 6492 KB Output is correct
15 Correct 1 ms 6488 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 6492 KB Output is correct
18 Correct 2 ms 6492 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6488 KB Output is correct
13 Correct 2 ms 6492 KB Output is correct
14 Correct 2 ms 6492 KB Output is correct
15 Correct 1 ms 6488 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 6492 KB Output is correct
18 Correct 2 ms 6492 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Correct 3686 ms 422172 KB Output is correct
21 Correct 2300 ms 422060 KB Output is correct
22 Correct 3061 ms 421960 KB Output is correct
23 Correct 3262 ms 422588 KB Output is correct
24 Correct 3459 ms 422344 KB Output is correct
25 Correct 3629 ms 422784 KB Output is correct
26 Correct 3611 ms 422248 KB Output is correct
27 Correct 3610 ms 422192 KB Output is correct
28 Correct 3830 ms 422588 KB Output is correct
29 Correct 3103 ms 419788 KB Output is correct
30 Correct 3578 ms 422160 KB Output is correct
31 Correct 3665 ms 422540 KB Output is correct
32 Correct 3570 ms 423256 KB Output is correct
33 Correct 3598 ms 422116 KB Output is correct
34 Correct 2426 ms 392884 KB Output is correct
35 Correct 3659 ms 422996 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6648 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 2 ms 6612 KB Output is correct
4 Execution timed out 5026 ms 436084 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6488 KB Output is correct
13 Correct 2 ms 6492 KB Output is correct
14 Correct 2 ms 6492 KB Output is correct
15 Correct 1 ms 6488 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 6492 KB Output is correct
18 Correct 2 ms 6492 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Correct 2138 ms 27692 KB Output is correct
21 Correct 2128 ms 27420 KB Output is correct
22 Correct 2133 ms 27488 KB Output is correct
23 Correct 2126 ms 27600 KB Output is correct
24 Correct 2125 ms 27684 KB Output is correct
25 Correct 2126 ms 27652 KB Output is correct
26 Correct 2138 ms 27588 KB Output is correct
27 Correct 2168 ms 27540 KB Output is correct
28 Correct 2124 ms 27804 KB Output is correct
29 Correct 2122 ms 27428 KB Output is correct
30 Correct 2519 ms 27448 KB Output is correct
31 Correct 2169 ms 27532 KB Output is correct
32 Correct 2212 ms 27952 KB Output is correct
33 Correct 2321 ms 27316 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6488 KB Output is correct
13 Correct 2 ms 6492 KB Output is correct
14 Correct 2 ms 6492 KB Output is correct
15 Correct 1 ms 6488 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 6492 KB Output is correct
18 Correct 2 ms 6492 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Correct 3686 ms 422172 KB Output is correct
21 Correct 2300 ms 422060 KB Output is correct
22 Correct 3061 ms 421960 KB Output is correct
23 Correct 3262 ms 422588 KB Output is correct
24 Correct 3459 ms 422344 KB Output is correct
25 Correct 3629 ms 422784 KB Output is correct
26 Correct 3611 ms 422248 KB Output is correct
27 Correct 3610 ms 422192 KB Output is correct
28 Correct 3830 ms 422588 KB Output is correct
29 Correct 3103 ms 419788 KB Output is correct
30 Correct 3578 ms 422160 KB Output is correct
31 Correct 3665 ms 422540 KB Output is correct
32 Correct 3570 ms 423256 KB Output is correct
33 Correct 3598 ms 422116 KB Output is correct
34 Correct 2426 ms 392884 KB Output is correct
35 Correct 3659 ms 422996 KB Output is correct
36 Correct 3702 ms 422640 KB Output is correct
37 Correct 2412 ms 422648 KB Output is correct
38 Correct 3169 ms 422384 KB Output is correct
39 Correct 3331 ms 422580 KB Output is correct
40 Correct 3473 ms 422608 KB Output is correct
41 Correct 3645 ms 422804 KB Output is correct
42 Correct 3650 ms 422592 KB Output is correct
43 Correct 3705 ms 422460 KB Output is correct
44 Correct 3958 ms 422784 KB Output is correct
45 Correct 3201 ms 419484 KB Output is correct
46 Correct 3671 ms 422664 KB Output is correct
47 Correct 3706 ms 422916 KB Output is correct
48 Correct 3704 ms 424048 KB Output is correct
49 Correct 3686 ms 422784 KB Output is correct
50 Correct 2481 ms 392904 KB Output is correct
51 Correct 3677 ms 423652 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6488 KB Output is correct
13 Correct 2 ms 6492 KB Output is correct
14 Correct 2 ms 6492 KB Output is correct
15 Correct 1 ms 6488 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 6492 KB Output is correct
18 Correct 2 ms 6492 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Correct 3686 ms 422172 KB Output is correct
21 Correct 2300 ms 422060 KB Output is correct
22 Correct 3061 ms 421960 KB Output is correct
23 Correct 3262 ms 422588 KB Output is correct
24 Correct 3459 ms 422344 KB Output is correct
25 Correct 3629 ms 422784 KB Output is correct
26 Correct 3611 ms 422248 KB Output is correct
27 Correct 3610 ms 422192 KB Output is correct
28 Correct 3830 ms 422588 KB Output is correct
29 Correct 3103 ms 419788 KB Output is correct
30 Correct 3578 ms 422160 KB Output is correct
31 Correct 3665 ms 422540 KB Output is correct
32 Correct 3570 ms 423256 KB Output is correct
33 Correct 3598 ms 422116 KB Output is correct
34 Correct 2426 ms 392884 KB Output is correct
35 Correct 3659 ms 422996 KB Output is correct
36 Correct 2 ms 6648 KB Output is correct
37 Correct 1 ms 6492 KB Output is correct
38 Correct 2 ms 6612 KB Output is correct
39 Execution timed out 5026 ms 436084 KB Time limit exceeded
40 Halted 0 ms 0 KB -