oj.uz

Submission #974733

# Submission time Handle Problem Language Result Execution time Memory
974733 2024-05-03T17:32:30 Z happy_node Reconstruction Project (JOI22_reconstruction) C++17
70 / 100
 5000 ms 439348 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<pair<int,int>> adj[MX];

const int inf=2e9;

array<int,3> bfs(int S, int T) {
	queue<int> q;
	q.push(S);
	
	vector<array<int,3>> dist(N+1,{-1,-1,-1});
	dist[S]={inf,inf,inf};

	while(!q.empty()) {
		auto v=q.front(); q.pop();
		for(auto [u,w]:adj[v]) {
			if(dist[u][0]!=-1) continue;

			array<int,3> cur={w,min(u,v),max(u,v)};
			dist[u]=min(cur,dist[v]);
			q.push(u);
		}
	}

	return dist[T];
}

array<int,3> BFS(int S, int T) {
	queue<int> q;
	q.push(S);
	
	vector<array<int,3>> dist(N+1,{-1,-1,-1});
	dist[S]={0,0,0};

	while(!q.empty()) {
		auto v=q.front(); q.pop();
		for(auto [u,w]:adj[v]) {
			if(dist[u][0]!=-1) continue;

			array<int,3> cur={w,min(u,v),max(u,v)};
			dist[u]=max(cur,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,uu,vv]=bfs(u,v);
		if(ww!=-1) {
			adj[uu].erase({vv,ww});
			adj[vv].erase({uu,ww});
			E.erase({ww,uu,vv,id[{ww,uu,vv}]});
		}
		adj[u].insert({v,w});
		adj[v].insert({u,w});
		E.insert({w,u,v,id[{w,u,v}]});
		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,uu,vv]=BFS(u,v);
		if(ww!=-1) {
			adj[uu].erase({vv,ww});
			adj[vv].erase({uu,ww});
			E.erase({ww,uu,vv,id[{ww,uu,vv}]});
		}
		adj[u].insert({v,w});
		adj[v].insert({u,w});
		E.insert({w,u,v,id[{w,u,v}]});
		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 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 1 ms 6488 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 2 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 2 ms 6488 KB Output is correct
12 Correct 2 ms 6744 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 2 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 6488 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 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 1 ms 6488 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 2 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 2 ms 6488 KB Output is correct
12 Correct 2 ms 6744 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 2 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 6488 KB Output is correct
18 Correct 2 ms 6492 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Correct 4029 ms 421076 KB Output is correct
21 Correct 2589 ms 422992 KB Output is correct
22 Correct 3336 ms 422648 KB Output is correct
23 Correct 3608 ms 423452 KB Output is correct
24 Correct 3851 ms 423044 KB Output is correct
25 Correct 3943 ms 423644 KB Output is correct
26 Correct 3998 ms 422868 KB Output is correct
27 Correct 3988 ms 422924 KB Output is correct
28 Correct 4192 ms 423440 KB Output is correct
29 Correct 3158 ms 420552 KB Output is correct
30 Correct 3988 ms 422792 KB Output is correct
31 Correct 4078 ms 422980 KB Output is correct
32 Correct 3998 ms 423940 KB Output is correct
33 Correct 4000 ms 423032 KB Output is correct
34 Correct 2331 ms 393024 KB Output is correct
35 Correct 4089 ms 423976 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Execution timed out 5072 ms 439348 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 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 1 ms 6488 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 2 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 2 ms 6488 KB Output is correct
12 Correct 2 ms 6744 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 2 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 6488 KB Output is correct
18 Correct 2 ms 6492 KB Output is correct
19 Correct 2 ms 6492 KB Output is correct
20 Correct 2081 ms 31872 KB Output is correct
21 Correct 2035 ms 32336 KB Output is correct
22 Correct 2076 ms 32504 KB Output is correct
23 Correct 2058 ms 32240 KB Output is correct
24 Correct 2041 ms 32220 KB Output is correct
25 Correct 2063 ms 32108 KB Output is correct
26 Correct 2079 ms 32036 KB Output is correct
27 Correct 2098 ms 32056 KB Output is correct
28 Correct 2098 ms 32312 KB Output is correct
29 Correct 2067 ms 31904 KB Output is correct
30 Correct 2326 ms 32284 KB Output is correct
31 Correct 2073 ms 31852 KB Output is correct
32 Correct 2117 ms 32580 KB Output is correct
33 Correct 2206 ms 31824 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 1 ms 6488 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 2 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 2 ms 6488 KB Output is correct
12 Correct 2 ms 6744 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 2 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 6488 KB Output is correct
18 Correct 2 ms 6492 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Correct 4029 ms 421076 KB Output is correct
21 Correct 2589 ms 422992 KB Output is correct
22 Correct 3336 ms 422648 KB Output is correct
23 Correct 3608 ms 423452 KB Output is correct
24 Correct 3851 ms 423044 KB Output is correct
25 Correct 3943 ms 423644 KB Output is correct
26 Correct 3998 ms 422868 KB Output is correct
27 Correct 3988 ms 422924 KB Output is correct
28 Correct 4192 ms 423440 KB Output is correct
29 Correct 3158 ms 420552 KB Output is correct
30 Correct 3988 ms 422792 KB Output is correct
31 Correct 4078 ms 422980 KB Output is correct
32 Correct 3998 ms 423940 KB Output is correct
33 Correct 4000 ms 423032 KB Output is correct
34 Correct 2331 ms 393024 KB Output is correct
35 Correct 4089 ms 423976 KB Output is correct
36 Correct 4118 ms 423236 KB Output is correct
37 Correct 2646 ms 422956 KB Output is correct
38 Correct 3433 ms 423136 KB Output is correct
39 Correct 3671 ms 422936 KB Output is correct
40 Correct 3926 ms 423184 KB Output is correct
41 Correct 4041 ms 423744 KB Output is correct
42 Correct 4117 ms 423328 KB Output is correct
43 Correct 3927 ms 423852 KB Output is correct
44 Correct 4268 ms 423196 KB Output is correct
45 Correct 3030 ms 420324 KB Output is correct
46 Correct 3943 ms 423412 KB Output is correct
47 Correct 4078 ms 423460 KB Output is correct
48 Correct 4021 ms 424368 KB Output is correct
49 Correct 4041 ms 423080 KB Output is correct
50 Correct 2391 ms 393724 KB Output is correct
51 Correct 4034 ms 424384 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 1 ms 6488 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 2 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 2 ms 6488 KB Output is correct
12 Correct 2 ms 6744 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 2 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 6488 KB Output is correct
18 Correct 2 ms 6492 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Correct 4029 ms 421076 KB Output is correct
21 Correct 2589 ms 422992 KB Output is correct
22 Correct 3336 ms 422648 KB Output is correct
23 Correct 3608 ms 423452 KB Output is correct
24 Correct 3851 ms 423044 KB Output is correct
25 Correct 3943 ms 423644 KB Output is correct
26 Correct 3998 ms 422868 KB Output is correct
27 Correct 3988 ms 422924 KB Output is correct
28 Correct 4192 ms 423440 KB Output is correct
29 Correct 3158 ms 420552 KB Output is correct
30 Correct 3988 ms 422792 KB Output is correct
31 Correct 4078 ms 422980 KB Output is correct
32 Correct 3998 ms 423940 KB Output is correct
33 Correct 4000 ms 423032 KB Output is correct
34 Correct 2331 ms 393024 KB Output is correct
35 Correct 4089 ms 423976 KB Output is correct
36 Correct 1 ms 6492 KB Output is correct
37 Correct 1 ms 6492 KB Output is correct
38 Correct 1 ms 6492 KB Output is correct
39 Execution timed out 5072 ms 439348 KB Time limit exceeded
40 Halted 0 ms 0 KB -