oj.uz

Submission #552486

# Submission time Handle Problem Language Result Execution time Memory
552486 2022-04-23T08:20:06 Z kshitij_sodani Reconstruction Project (JOI22_reconstruction) C++14
31 / 100
 5000 ms 26836 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define a first
#define b second
#define pb push_back
const llo mod=1e9+7;
int n,m;
vector<pair<int,int>> adj[501];
vector<pair<int,pair<int,int>>> ee;
int ac=-1;
int cc=-1;
void dfs(int no,int par=-1,int ma=-1){
	if(ac==no){
		cc=ma;
	}
	for(auto j:adj[no]){
		if(j.a!=par){
			dfs(j.a,no,max(ma,j.b));
		}
	}
}
int re[100001];
void solve(){
	for(int i=0;i<n;i++){
		adj[i].clear();
	}
	for(int i=ee.size()-1;i>=0;i--){
		ac=ee[i].b.b;
		cc=-1;
		dfs(ee[i].b.a);
		if(cc==-1){
			adj[ac].pb({ee[i].b.a,i});
			adj[ee[i].b.a].pb({ac,i});
			re[i]=m;
		}
		else{
		//	cout<<22<<endl;
			vector<pair<int,int>> ee2;
			for(int j=0;j<n;j++){
				for(auto jj:adj[j]){
					if(jj.b==cc){
						continue;
					}
					ee2.pb(jj);
				}
				adj[j]=ee2;
				ee2.clear();
			}
			adj[ac].pb({ee[i].b.a,i});
			adj[ee[i].b.a].pb({ac,i});
			re[i]=cc;
		}

	}
}
llo vis[100001];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin>>n>>m;
	
	for(int i=0;i<m;i++){
		int aa,bb,cc;
		cin>>aa>>bb>>cc;
		aa--;
		bb--;
		ee.pb({cc,{aa,bb}});
	}
	sort(ee.begin(),ee.end());
	solve();
	vector<pair<pair<int,int>,int>> qq;
	for(int i=0;i<m;i++){
		//if query>(x+y)/2
		if(re[i]<m){
			qq.pb({{(ee[i].a+ee[re[i]].a)/2,10},i});
		}
	}
	/*for(auto j:ee){
		cout<<j.a<<":"<<j.b.a<<":"<<j.b.b<<endl;
	}
	for(int i=0;i<ee.size();i++){
		cout<<re[i]<<",";
	}
	cout<<endl;*/
	//return 0;
	reverse(ee.begin(),ee.end());
	solve();
/*	for(int i=0;i<ee.size();i++){
		cout<<re[i]<<",";
	}
	cout<<endl;*/
	//return 0;
	for(int i=0;i<m;i++){
		//if query>(x+y)/2
		if(re[i]<m){
			qq.pb({{(ee[i].a+ee[re[i]].a+2)/2,-10},m-i-1});
		}
		else{
			qq.pb({{-10,-10},m-i-1});
		}
	}
	reverse(ee.begin(),ee.end());
	multiset<int> cur;
	int q;
	cin>>q;
	for(int ii=0;ii<q;ii++){
		int aa;
		cin>>aa;
		qq.pb({{aa,0},ii});
	}
	sort(qq.begin(),qq.end());
	for(auto j:qq){
		if(j.a.b==0){
			llo ans=0;
			for(auto jj:cur){
				ans+=abs(j.a.a-jj);
			}
			cout<<ans<<endl;
		}
		else if(j.a.b==-10){
			if(vis[j.b]==1){
				continue;
			}
			cur.insert(ee[j.b].a);
		}
		else if(j.a.b==10){

			auto jj=cur.find(ee[j.b].a);
			vis[j.b]=1;
			if(jj==cur.end()){
			//	cout<<-1<<endl;
				continue;
			}
			assert(jj!=cur.end());
			cur.erase(jj);
		}
	}



	return 0;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 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 340 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 344 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 340 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 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 344 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 340 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 344 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 340 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 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 Correct 2472 ms 6792 KB Output is correct
21 Correct 1803 ms 5296 KB Output is correct
22 Correct 2258 ms 5196 KB Output is correct
23 Correct 2544 ms 5204 KB Output is correct
24 Correct 2685 ms 5184 KB Output is correct
25 Correct 2966 ms 5188 KB Output is correct
26 Correct 2818 ms 6472 KB Output is correct
27 Correct 2700 ms 6568 KB Output is correct
28 Correct 2605 ms 6656 KB Output is correct
29 Incorrect 1786 ms 6584 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Execution timed out 5076 ms 26836 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 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 340 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 344 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 340 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 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 Correct 4263 ms 26608 KB Output is correct
21 Correct 4097 ms 26784 KB Output is correct
22 Correct 4058 ms 26536 KB Output is correct
23 Correct 4051 ms 25900 KB Output is correct
24 Correct 4024 ms 25788 KB Output is correct
25 Correct 3936 ms 26040 KB Output is correct
26 Correct 3851 ms 25748 KB Output is correct
27 Correct 3804 ms 25128 KB Output is correct
28 Correct 4006 ms 24548 KB Output is correct
29 Correct 3988 ms 24500 KB Output is correct
30 Correct 4165 ms 24484 KB Output is correct
31 Correct 3905 ms 24592 KB Output is correct
32 Correct 3633 ms 25172 KB Output is correct
33 Correct 4078 ms 24396 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 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 340 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 344 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 340 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 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 Correct 2472 ms 6792 KB Output is correct
21 Correct 1803 ms 5296 KB Output is correct
22 Correct 2258 ms 5196 KB Output is correct
23 Correct 2544 ms 5204 KB Output is correct
24 Correct 2685 ms 5184 KB Output is correct
25 Correct 2966 ms 5188 KB Output is correct
26 Correct 2818 ms 6472 KB Output is correct
27 Correct 2700 ms 6568 KB Output is correct
28 Correct 2605 ms 6656 KB Output is correct
29 Incorrect 1786 ms 6584 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 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 340 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 344 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 340 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 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 Correct 2472 ms 6792 KB Output is correct
21 Correct 1803 ms 5296 KB Output is correct
22 Correct 2258 ms 5196 KB Output is correct
23 Correct 2544 ms 5204 KB Output is correct
24 Correct 2685 ms 5184 KB Output is correct
25 Correct 2966 ms 5188 KB Output is correct
26 Correct 2818 ms 6472 KB Output is correct
27 Correct 2700 ms 6568 KB Output is correct
28 Correct 2605 ms 6656 KB Output is correct
29 Incorrect 1786 ms 6584 KB Output isn't correct
30 Halted 0 ms 0 KB -