oj.uz

Submission #552494

# Submission time Handle Problem Language Result Execution time Memory
552494 2022-04-23T08:31:29 Z kshitij_sodani Reconstruction Project (JOI22_reconstruction) C++14
100 / 100
 4216 ms 63320 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;
llo n,m;
vector<pair<llo,llo>> adj[501];
vector<pair<llo,pair<llo,llo>>> ee;
llo ac=-1;
llo cc=-1;
void dfs(llo no,llo par=-1,llo ma=-1){
	if(ac==no){
		cc=ma;
	}
	for(auto j:adj[no]){
		if(j.a!=par){
			dfs(j.a,no,max(ma,j.b));
		}
	}
}
llo re[100001];
void solve(){
	for(llo i=0;i<n;i++){
		adj[i].clear();
	}
	for(llo 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<llo,llo>> ee2;
			for(llo 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];
pair<llo,llo> tree[4*100001];
void update(llo no,llo l,llo r,llo i,pair<llo,llo> j){
	if(l==r){
		tree[no]=j;
	}
	else{
		llo mid=(l+r)/2;
		if(i<=mid){
			update(no*2+1,l,mid,i,j);
		}
		else{
			update(no*2+2,mid+1,r,i,j);
		}
		tree[no].a=tree[no*2+1].a+tree[no*2+2].a;
		tree[no].b=tree[no*2+1].b+tree[no*2+2].b;
	}
}
pair<llo,llo> query(llo no,llo l,llo r,llo aa,llo bb){
	if(aa>bb or l>bb or r<aa){
		return {0,0};
	}
	if(aa<=l and r<=bb){
		return tree[no];
	}
	llo mid=(l+r)/2;
	pair<llo,llo> x=query(no*2+1,l,mid,aa,bb);
	pair<llo,llo> y=query(no*2+2,mid+1,r,aa,bb);
	return {x.a+y.a,x.b+y.b};
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin>>n>>m;
	
	for(llo i=0;i<m;i++){
		llo aa,bb,cc;
		cin>>aa>>bb>>cc;
		aa--;
		bb--;
		ee.pb({cc,{aa,bb}});
	}
	sort(ee.begin(),ee.end());
	solve();
	vector<pair<pair<llo,llo>,llo>> qq;
	for(llo 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(llo i=0;i<ee.size();i++){
		cout<<re[i]<<",";
	}
	cout<<endl;*/
	//return 0;
	reverse(ee.begin(),ee.end());
	solve();
/*	for(llo i=0;i<ee.size();i++){
		cout<<re[i]<<",";
	}
	cout<<endl;*/
	//return 0;
	for(llo 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<llo> cur;
	llo q;
	cin>>q;
	for(llo ii=0;ii<q;ii++){
		llo aa;
		cin>>aa;
		qq.pb({{aa,0},ii});
	}
	sort(qq.begin(),qq.end());
	for(llo i=0;i<4*m;i++){
		tree[i]={0,0};
	}
	for(auto j:qq){
		if(j.a.b==0){
			//llo ans=0;
			/*for(auto jj:cur){
				ans+=abs(j.a.a-jj);
			}*/
		
			llo low=-1;
			for(llo i=19;i>=0;i--){
				if(low+(1<<i)<m){
					if(ee[low+(1<<i)].a<=j.a.a){
						low+=(1<<i);
					}
				}
			}
			pair<llo,llo> x=query(0,0,m-1,0,low);
			
			pair<llo,llo> y=query(0,0,m-1,low+1,m-1);
		
			llo ans=j.a.a*x.a-x.b;
			ans+=(y.b-y.a*j.a.a);
			cout<<ans<<endl;
		}
		else if(j.a.b==-10){
			if(vis[j.b]==1){
				continue;
			}
			update(0,0,m-1,j.b,{1,ee[j.b].a});
			//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());
			update(0,0,m-1,j.b,{0,0});
			//cur.erase(jj);
		}
	}



	return 0;
}

Subtask #1
3.0 / 3.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 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 340 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 344 KB Output is correct
13 Correct 1 ms 340 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
4.0 / 4.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 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 340 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 344 KB Output is correct
13 Correct 1 ms 340 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 2572 ms 15772 KB Output is correct
21 Correct 1978 ms 15364 KB Output is correct
22 Correct 2472 ms 15384 KB Output is correct
23 Correct 2619 ms 15424 KB Output is correct
24 Correct 2473 ms 15380 KB Output is correct
25 Correct 2351 ms 15488 KB Output is correct
26 Correct 2456 ms 16276 KB Output is correct
27 Correct 2485 ms 16112 KB Output is correct
28 Correct 2398 ms 16048 KB Output is correct
29 Correct 1703 ms 16512 KB Output is correct
30 Correct 2370 ms 17372 KB Output is correct
31 Correct 2346 ms 16980 KB Output is correct
32 Correct 2405 ms 17044 KB Output is correct
33 Correct 2327 ms 15404 KB Output is correct
34 Correct 1323 ms 19316 KB Output is correct
35 Correct 2367 ms 17112 KB Output is correct

Subtask #3
7.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 Correct 3710 ms 53580 KB Output is correct
5 Correct 3930 ms 62432 KB Output is correct
6 Correct 3690 ms 62284 KB Output is correct
7 Correct 2558 ms 62996 KB Output is correct
8 Correct 2477 ms 63080 KB Output is correct
9 Correct 2481 ms 63320 KB Output is correct
10 Correct 3711 ms 63008 KB Output is correct
11 Correct 2425 ms 63232 KB Output is correct

Subtask #4
28.0 / 28.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 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 340 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 344 KB Output is correct
13 Correct 1 ms 340 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 1624 ms 37328 KB Output is correct
21 Correct 1598 ms 37324 KB Output is correct
22 Correct 1608 ms 37508 KB Output is correct
23 Correct 1557 ms 37252 KB Output is correct
24 Correct 1590 ms 37252 KB Output is correct
25 Correct 1550 ms 37312 KB Output is correct
26 Correct 1646 ms 37292 KB Output is correct
27 Correct 1556 ms 37424 KB Output is correct
28 Correct 1522 ms 36624 KB Output is correct
29 Correct 1527 ms 36848 KB Output is correct
30 Correct 1552 ms 36616 KB Output is correct
31 Correct 1525 ms 36692 KB Output is correct
32 Correct 1483 ms 37492 KB Output is correct
33 Correct 1595 ms 36404 KB Output is correct

Subtask #5
35.0 / 35.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 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 340 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 344 KB Output is correct
13 Correct 1 ms 340 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 2572 ms 15772 KB Output is correct
21 Correct 1978 ms 15364 KB Output is correct
22 Correct 2472 ms 15384 KB Output is correct
23 Correct 2619 ms 15424 KB Output is correct
24 Correct 2473 ms 15380 KB Output is correct
25 Correct 2351 ms 15488 KB Output is correct
26 Correct 2456 ms 16276 KB Output is correct
27 Correct 2485 ms 16112 KB Output is correct
28 Correct 2398 ms 16048 KB Output is correct
29 Correct 1703 ms 16512 KB Output is correct
30 Correct 2370 ms 17372 KB Output is correct
31 Correct 2346 ms 16980 KB Output is correct
32 Correct 2405 ms 17044 KB Output is correct
33 Correct 2327 ms 15404 KB Output is correct
34 Correct 1323 ms 19316 KB Output is correct
35 Correct 2367 ms 17112 KB Output is correct
36 Correct 2330 ms 17928 KB Output is correct
37 Correct 1707 ms 17900 KB Output is correct
38 Correct 2080 ms 16188 KB Output is correct
39 Correct 2215 ms 16304 KB Output is correct
40 Correct 2227 ms 16088 KB Output is correct
41 Correct 2297 ms 16052 KB Output is correct
42 Correct 2297 ms 17048 KB Output is correct
43 Correct 2345 ms 17328 KB Output is correct
44 Correct 2394 ms 17944 KB Output is correct
45 Correct 1659 ms 18072 KB Output is correct
46 Correct 2372 ms 17872 KB Output is correct
47 Correct 2317 ms 17960 KB Output is correct
48 Correct 2310 ms 17656 KB Output is correct
49 Correct 2328 ms 16096 KB Output is correct
50 Correct 1278 ms 18344 KB Output is correct
51 Correct 2296 ms 16060 KB Output is correct

Subtask #6
23.0 / 23.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 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 340 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 344 KB Output is correct
13 Correct 1 ms 340 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 2572 ms 15772 KB Output is correct
21 Correct 1978 ms 15364 KB Output is correct
22 Correct 2472 ms 15384 KB Output is correct
23 Correct 2619 ms 15424 KB Output is correct
24 Correct 2473 ms 15380 KB Output is correct
25 Correct 2351 ms 15488 KB Output is correct
26 Correct 2456 ms 16276 KB Output is correct
27 Correct 2485 ms 16112 KB Output is correct
28 Correct 2398 ms 16048 KB Output is correct
29 Correct 1703 ms 16512 KB Output is correct
30 Correct 2370 ms 17372 KB Output is correct
31 Correct 2346 ms 16980 KB Output is correct
32 Correct 2405 ms 17044 KB Output is correct
33 Correct 2327 ms 15404 KB Output is correct
34 Correct 1323 ms 19316 KB Output is correct
35 Correct 2367 ms 17112 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 1 ms 340 KB Output is correct
38 Correct 1 ms 340 KB Output is correct
39 Correct 3710 ms 53580 KB Output is correct
40 Correct 3930 ms 62432 KB Output is correct
41 Correct 3690 ms 62284 KB Output is correct
42 Correct 2558 ms 62996 KB Output is correct
43 Correct 2477 ms 63080 KB Output is correct
44 Correct 2481 ms 63320 KB Output is correct
45 Correct 3711 ms 63008 KB Output is correct
46 Correct 2425 ms 63232 KB Output is correct
47 Correct 1 ms 340 KB Output is correct
48 Correct 1624 ms 37328 KB Output is correct
49 Correct 1598 ms 37324 KB Output is correct
50 Correct 1608 ms 37508 KB Output is correct
51 Correct 1557 ms 37252 KB Output is correct
52 Correct 1590 ms 37252 KB Output is correct
53 Correct 1550 ms 37312 KB Output is correct
54 Correct 1646 ms 37292 KB Output is correct
55 Correct 1556 ms 37424 KB Output is correct
56 Correct 1522 ms 36624 KB Output is correct
57 Correct 1527 ms 36848 KB Output is correct
58 Correct 1552 ms 36616 KB Output is correct
59 Correct 1525 ms 36692 KB Output is correct
60 Correct 1483 ms 37492 KB Output is correct
61 Correct 1595 ms 36404 KB Output is correct
62 Correct 2330 ms 17928 KB Output is correct
63 Correct 1707 ms 17900 KB Output is correct
64 Correct 2080 ms 16188 KB Output is correct
65 Correct 2215 ms 16304 KB Output is correct
66 Correct 2227 ms 16088 KB Output is correct
67 Correct 2297 ms 16052 KB Output is correct
68 Correct 2297 ms 17048 KB Output is correct
69 Correct 2345 ms 17328 KB Output is correct
70 Correct 2394 ms 17944 KB Output is correct
71 Correct 1659 ms 18072 KB Output is correct
72 Correct 2372 ms 17872 KB Output is correct
73 Correct 2317 ms 17960 KB Output is correct
74 Correct 2310 ms 17656 KB Output is correct
75 Correct 2328 ms 16096 KB Output is correct
76 Correct 1278 ms 18344 KB Output is correct
77 Correct 2296 ms 16060 KB Output is correct
78 Correct 3971 ms 55008 KB Output is correct
79 Correct 3287 ms 60760 KB Output is correct
80 Correct 3732 ms 63052 KB Output is correct
81 Correct 3780 ms 63068 KB Output is correct
82 Correct 3861 ms 63064 KB Output is correct
83 Correct 3990 ms 62736 KB Output is correct
84 Correct 4024 ms 60548 KB Output is correct
85 Correct 3972 ms 52952 KB Output is correct
86 Correct 4033 ms 52864 KB Output is correct
87 Correct 3466 ms 53092 KB Output is correct
88 Correct 4216 ms 52848 KB Output is correct
89 Correct 3926 ms 52920 KB Output is correct
90 Correct 3890 ms 52868 KB Output is correct
91 Correct 3939 ms 52872 KB Output is correct
92 Correct 2589 ms 55120 KB Output is correct
93 Correct 3997 ms 52940 KB Output is correct