oj.uz

Submission #552482

# Submission time Handle Problem Language Result Execution time Memory
552482 2022-04-23T08:18:48 Z kshitij_sodani Reconstruction Project (JOI22_reconstruction) C++14
31 / 100
 5000 ms 34144 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
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){
			cur.insert(ee[j.b].a);
		}
		else if(j.a.b==10){
			auto jj=cur.find(ee[j.b].a);
			
			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 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 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 0 ms 340 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 2 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 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 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 0 ms 340 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 2 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 2567 ms 6636 KB Output is correct
21 Correct 1810 ms 5176 KB Output is correct
22 Correct 2401 ms 5184 KB Output is correct
23 Correct 2579 ms 5192 KB Output is correct
24 Correct 2667 ms 5060 KB Output is correct
25 Correct 2714 ms 5064 KB Output is correct
26 Correct 2589 ms 6824 KB Output is correct
27 Correct 2532 ms 6572 KB Output is correct
28 Correct 2511 ms 6680 KB Output is correct
29 Incorrect 1792 ms 10224 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #3
0 / 7.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 Execution timed out 5022 ms 26980 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 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 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 0 ms 340 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 2 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 4230 ms 33704 KB Output is correct
21 Correct 4235 ms 28948 KB Output is correct
22 Correct 4121 ms 33408 KB Output is correct
23 Correct 3911 ms 33932 KB Output is correct
24 Correct 3938 ms 33920 KB Output is correct
25 Correct 4022 ms 33804 KB Output is correct
26 Correct 3927 ms 33824 KB Output is correct
27 Correct 4169 ms 33748 KB Output is correct
28 Correct 4671 ms 33936 KB Output is correct
29 Correct 4621 ms 34004 KB Output is correct
30 Correct 4443 ms 33856 KB Output is correct
31 Correct 4772 ms 33720 KB Output is correct
32 Correct 4503 ms 34144 KB Output is correct
33 Correct 4905 ms 33836 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 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 0 ms 340 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 2 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 2567 ms 6636 KB Output is correct
21 Correct 1810 ms 5176 KB Output is correct
22 Correct 2401 ms 5184 KB Output is correct
23 Correct 2579 ms 5192 KB Output is correct
24 Correct 2667 ms 5060 KB Output is correct
25 Correct 2714 ms 5064 KB Output is correct
26 Correct 2589 ms 6824 KB Output is correct
27 Correct 2532 ms 6572 KB Output is correct
28 Correct 2511 ms 6680 KB Output is correct
29 Incorrect 1792 ms 10224 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 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 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 0 ms 340 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 2 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 2567 ms 6636 KB Output is correct
21 Correct 1810 ms 5176 KB Output is correct
22 Correct 2401 ms 5184 KB Output is correct
23 Correct 2579 ms 5192 KB Output is correct
24 Correct 2667 ms 5060 KB Output is correct
25 Correct 2714 ms 5064 KB Output is correct
26 Correct 2589 ms 6824 KB Output is correct
27 Correct 2532 ms 6572 KB Output is correct
28 Correct 2511 ms 6680 KB Output is correct
29 Incorrect 1792 ms 10224 KB Output isn't correct
30 Halted 0 ms 0 KB -