oj.uz

Submission #568868

# Submission time Handle Problem Language Result Execution time Memory
568868 2022-05-26T09:46:10 Z errorgorn Reconstruction Project (JOI22_reconstruction) C++17
70 / 100
 3402 ms 790184 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<int,int>
#define fi first
#define se second
#define endl '\n'

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct UFDS{
	int p[505];
	int s[505];
	vector<ii> roll;
	
	UFDS(){
		rep(x,0,505) p[x]=x,s[x]=1;
		roll.clear();
	}
	
	int par(int i){
		while (p[i]!=i) i=p[i];
		return i;
	}
	
	bool unions(int i,int j){
		i=par(i),j=par(j);
		if (i==j) return false;
		
		if (s[i]>s[j]) swap(i,j);
		p[i]=j;
		s[j]+=s[i];
		roll.pub({i,j});
		
		return true;
	}
	
	void rollback(int ss){
		while (sz(roll)>ss){
			int i,j;
			tie(i,j)=roll.back(); roll.pob();
			
			p[i]=i;
			s[j]-=s[i];
		}
	}
} ufds;

struct UFDS2{
	int p[505];
	
	void reset(){
		rep(x,0,505) p[x]=x;
	}
	
	int par(int i){
		if (p[i]==i) return i;
		else return p[i]=par(p[i]);
	}
	
	bool unions(int i,int j){
		i=par(i),j=par(j);
		if (i==j) return false;
		p[i]=j;
		return true;
	}
} ufds2;

int n,m,q;
struct E{
	int u,v;
	int w;
};

E ee[100005];

void fix(vector<int> &v){
	vector<int> temp;
	
	ufds2.reset();
	while (!v.empty()){
		if (ufds2.unions(ee[v.back()].u,ee[v.back()].v)){
			temp.pub(v.back());
		}
		v.pob();
	}
	
	v=temp;
	reverse(all(v));
}

vector<int> f[100005];
vector<int> b[100005];

int qu[1000005];
int split[1000005];
long long ans[1000005];

void solve(int l,int r,vector<int> vl,vector<int> vr,ll cans,ll lu,ll ru){
	int m=l+r>>1;
	
	int ss=sz(ufds.roll);
	
	vector<int> vl1,vl2;
	vector<int> vr1,vr2;
	
	ll lans=0,rans=0;
	ll lu2=lu,ru2=ru;
	
	while (!vl.empty() || !vr.empty()){
		if (vr.empty() ||
			(!vl.empty() && qu[m]-ee[vl.back()].w<=ee[vr.back()].w-qu[m])){
			
			if (ufds.unions(ee[vl.back()].u,ee[vl.back()].v)){
				lans+=-ee[vl.back()].w;
				lu2++;
				
				vl1.pub(vl.back());
			}
			else{
				vl2.pub(vl.back());
			}
			vl.pob();
		}
		else{
			if (ufds.unions(ee[vr.back()].u,ee[vr.back()].v)){
				rans+=ee[vr.back()].w;
				ru2++;
				
				vr1.pub(vr.back());
			}
			else{
				vr2.pub(vr.back());
			}
			vr.pob();
		}
	}
	
	ans[m]=cans+lans+rans+lu2*qu[m]-ru2*qu[m];
	
	reverse(all(vl1)),reverse(all(vl2));
	reverse(all(vr1)),reverse(all(vr2));
	
	//cout<<"debug: "<<l<<" "<<m<<" "<<r<<endl;
	//for (auto it:vl1) cout<<it<<" "; cout<<endl;
	//for (auto it:vl2) cout<<it<<" "; cout<<endl;
	//for (auto it:vr1) cout<<it<<" "; cout<<endl;
	//for (auto it:vr2) cout<<it<<" "; cout<<endl;
	
	//vl1,vr1 are those things added at this stage
	ufds.rollback(ss);
	if (l!=m){
		for (auto it:vl1) ufds.unions(ee[it].u,ee[it].v);
		solve(l,m-1,vl2,vr1,cans+lans,lu2,ru);
		ufds.rollback(ss);
	}
	if (m!=r){
		for (auto it:vr1) ufds.unions(ee[it].u,ee[it].v);
		solve(m+1,r,vl1,vr2,cans+rans,lu,ru2);
		ufds.rollback(ss);
	}
}

namespace subtask3{
	vector<int> w[100005];
	int idx[100005];
	
	void solve(){
		int a,b,c;
		rep(x,0,m){
			w[ee[x].u].pub(ee[x].w);
		}
		
		rep(x,1,n) sort(all(w[x]));
		
		rep(i,0,q){
			long long ans=0;
			rep(x,1,n){
				while (idx[x]+1<sz(w[x]) && abs(w[x][idx[x]+1]-qu[i])<abs(w[x][idx[x]]-qu[i])){
					idx[x]++;
				}
				ans+=abs(w[x][idx[x]]-qu[i]);
			}
			
			cout<<ans<<endl;
		}
	}
}

signed main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	cin>>n>>m;
	rep(x,1,m+1) cin>>ee[x].u>>ee[x].v>>ee[x].w;
	cin>>q;
	rep(x,0,q) cin>>qu[x];
	
	if (m>1000 && q>20000){
		subtask3::solve();
		return 0;
	}
	
	sort(ee+1,ee+m+1,[](E i,E j){
		return i.w<j.w;
	});
	
	rep(x,1,m+1){
		f[x].pub(x);
		fix(f[x]);
		f[x+1]=f[x];
	}
	rep(x,m+1,1){
		b[x].pub(x);
		fix(b[x]);
		b[x-1]=b[x];
	}
	
	//rep(x,1,m+1) cout<<x<<" "; cout<<endl;
	//rep(x,1,m+1) cout<<ee[x].u<<" "; cout<<endl;
	//rep(x,1,m+1) cout<<ee[x].v<<" "; cout<<endl;
	
	//rep(x,1,m+1){
		//cout<<x<<": "; for (auto it:f[x]) cout<<it<<" "; cout<<endl;
	//}
	
	split[0]=1;
	rep(x,0,q){
		while (split[x]<=m && ee[split[x]].w<=qu[x]) split[x]++;
		split[x+1]=split[x];
	}
	
	//rep(x,0,q) cout<<split[x]<<" "; cout<<endl;
	
	rep(x,1,m+2){
		int l=lb(split,split+q,x)-split;
		int r=ub(split,split+q,x)-split-1;
		
		if (l<=r) solve(l,r,f[x-1],b[x],0,0,0);
	}
	
	rep(x,0,q) cout<<ans[x]<<endl;
}

Compilation message

reconstruction.cpp: In function 'void solve(int, int, std::vector<int>, std::vector<int>, long long int, long long int, long long int)':
reconstruction.cpp:112:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  112 |  int m=l+r>>1;
      |        ~^~
reconstruction.cpp: In function 'void subtask3::solve()':
reconstruction.cpp:181:7: warning: unused variable 'a' [-Wunused-variable]
  181 |   int a,b,c;
      |       ^
reconstruction.cpp:181:9: warning: unused variable 'b' [-Wunused-variable]
  181 |   int a,b,c;
      |         ^
reconstruction.cpp:181:11: warning: unused variable 'c' [-Wunused-variable]
  181 |   int a,b,c;
      |           ^

Subtask #1
3.0 / 3.0

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

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 5 ms 7356 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 4 ms 7400 KB Output is correct
11 Correct 5 ms 7340 KB Output is correct
12 Correct 4 ms 7380 KB Output is correct
13 Correct 4 ms 7380 KB Output is correct
14 Correct 5 ms 7380 KB Output is correct
15 Correct 4 ms 7380 KB Output is correct
16 Correct 4 ms 7380 KB Output is correct
17 Correct 4 ms 7392 KB Output is correct
18 Correct 5 ms 7380 KB Output is correct
19 Correct 4 ms 7380 KB Output is correct
20 Correct 2496 ms 790184 KB Output is correct
21 Correct 1821 ms 749012 KB Output is correct
22 Correct 1984 ms 780760 KB Output is correct
23 Correct 1947 ms 787596 KB Output is correct
24 Correct 2162 ms 788892 KB Output is correct
25 Correct 2580 ms 789216 KB Output is correct
26 Correct 2456 ms 789372 KB Output is correct
27 Correct 2539 ms 789452 KB Output is correct
28 Correct 2471 ms 789440 KB Output is correct
29 Correct 2450 ms 789492 KB Output is correct
30 Correct 2429 ms 789484 KB Output is correct
31 Correct 2447 ms 789368 KB Output is correct
32 Correct 2463 ms 789372 KB Output is correct
33 Correct 2437 ms 789232 KB Output is correct
34 Correct 2423 ms 788988 KB Output is correct
35 Correct 2451 ms 789048 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7380 KB Output is correct
2 Correct 5 ms 7380 KB Output is correct
3 Correct 4 ms 7400 KB Output is correct
4 Incorrect 2376 ms 24116 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 5 ms 7356 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 4 ms 7400 KB Output is correct
11 Correct 5 ms 7340 KB Output is correct
12 Correct 4 ms 7380 KB Output is correct
13 Correct 4 ms 7380 KB Output is correct
14 Correct 5 ms 7380 KB Output is correct
15 Correct 4 ms 7380 KB Output is correct
16 Correct 4 ms 7380 KB Output is correct
17 Correct 4 ms 7392 KB Output is correct
18 Correct 5 ms 7380 KB Output is correct
19 Correct 4 ms 7380 KB Output is correct
20 Correct 516 ms 41428 KB Output is correct
21 Correct 506 ms 41244 KB Output is correct
22 Correct 505 ms 41304 KB Output is correct
23 Correct 487 ms 41320 KB Output is correct
24 Correct 500 ms 41308 KB Output is correct
25 Correct 530 ms 41356 KB Output is correct
26 Correct 437 ms 41284 KB Output is correct
27 Correct 242 ms 41216 KB Output is correct
28 Correct 506 ms 41404 KB Output is correct
29 Correct 545 ms 41380 KB Output is correct
30 Correct 406 ms 41328 KB Output is correct
31 Correct 394 ms 41324 KB Output is correct
32 Correct 248 ms 41836 KB Output is correct
33 Correct 240 ms 40888 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 5 ms 7356 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 4 ms 7400 KB Output is correct
11 Correct 5 ms 7340 KB Output is correct
12 Correct 4 ms 7380 KB Output is correct
13 Correct 4 ms 7380 KB Output is correct
14 Correct 5 ms 7380 KB Output is correct
15 Correct 4 ms 7380 KB Output is correct
16 Correct 4 ms 7380 KB Output is correct
17 Correct 4 ms 7392 KB Output is correct
18 Correct 5 ms 7380 KB Output is correct
19 Correct 4 ms 7380 KB Output is correct
20 Correct 2496 ms 790184 KB Output is correct
21 Correct 1821 ms 749012 KB Output is correct
22 Correct 1984 ms 780760 KB Output is correct
23 Correct 1947 ms 787596 KB Output is correct
24 Correct 2162 ms 788892 KB Output is correct
25 Correct 2580 ms 789216 KB Output is correct
26 Correct 2456 ms 789372 KB Output is correct
27 Correct 2539 ms 789452 KB Output is correct
28 Correct 2471 ms 789440 KB Output is correct
29 Correct 2450 ms 789492 KB Output is correct
30 Correct 2429 ms 789484 KB Output is correct
31 Correct 2447 ms 789368 KB Output is correct
32 Correct 2463 ms 789372 KB Output is correct
33 Correct 2437 ms 789232 KB Output is correct
34 Correct 2423 ms 788988 KB Output is correct
35 Correct 2451 ms 789048 KB Output is correct
36 Correct 3402 ms 789644 KB Output is correct
37 Correct 2532 ms 749956 KB Output is correct
38 Correct 2630 ms 780588 KB Output is correct
39 Correct 2654 ms 788060 KB Output is correct
40 Correct 2866 ms 789420 KB Output is correct
41 Correct 3266 ms 789676 KB Output is correct
42 Correct 3164 ms 789908 KB Output is correct
43 Correct 3107 ms 790008 KB Output is correct
44 Correct 2666 ms 790016 KB Output is correct
45 Correct 2487 ms 789992 KB Output is correct
46 Correct 3085 ms 789876 KB Output is correct
47 Correct 3078 ms 790104 KB Output is correct
48 Correct 3108 ms 789840 KB Output is correct
49 Correct 3073 ms 789856 KB Output is correct
50 Correct 2447 ms 789952 KB Output is correct
51 Correct 2515 ms 789888 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 5 ms 7356 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 4 ms 7400 KB Output is correct
11 Correct 5 ms 7340 KB Output is correct
12 Correct 4 ms 7380 KB Output is correct
13 Correct 4 ms 7380 KB Output is correct
14 Correct 5 ms 7380 KB Output is correct
15 Correct 4 ms 7380 KB Output is correct
16 Correct 4 ms 7380 KB Output is correct
17 Correct 4 ms 7392 KB Output is correct
18 Correct 5 ms 7380 KB Output is correct
19 Correct 4 ms 7380 KB Output is correct
20 Correct 2496 ms 790184 KB Output is correct
21 Correct 1821 ms 749012 KB Output is correct
22 Correct 1984 ms 780760 KB Output is correct
23 Correct 1947 ms 787596 KB Output is correct
24 Correct 2162 ms 788892 KB Output is correct
25 Correct 2580 ms 789216 KB Output is correct
26 Correct 2456 ms 789372 KB Output is correct
27 Correct 2539 ms 789452 KB Output is correct
28 Correct 2471 ms 789440 KB Output is correct
29 Correct 2450 ms 789492 KB Output is correct
30 Correct 2429 ms 789484 KB Output is correct
31 Correct 2447 ms 789368 KB Output is correct
32 Correct 2463 ms 789372 KB Output is correct
33 Correct 2437 ms 789232 KB Output is correct
34 Correct 2423 ms 788988 KB Output is correct
35 Correct 2451 ms 789048 KB Output is correct
36 Correct 5 ms 7380 KB Output is correct
37 Correct 5 ms 7380 KB Output is correct
38 Correct 4 ms 7400 KB Output is correct
39 Incorrect 2376 ms 24116 KB Output isn't correct
40 Halted 0 ms 0 KB -