oj.uz

Submission #568866

# Submission time Handle Problem Language Result Execution time Memory
568866 2022-05-26T09:43:59 Z errorgorn Reconstruction Project (JOI22_reconstruction) C++17
70 / 100
 3401 ms 790256 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(x,0,q){
			long long ans=0;
			rep(x,1,n){
				while (idx[x]+1<sz(w[x]) && abs(w[x][idx[x]+1]-qu[x])<abs(w[x][idx[x]]-qu[x])){
					idx[x]++;
				}
				ans+=abs(w[x][idx[x]]-qu[x]);
			}
			
			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 5 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 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 5 ms 7336 KB Output is correct
8 Correct 6 ms 7380 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 5 ms 7412 KB Output is correct
11 Correct 4 ms 7380 KB Output is correct
12 Correct 4 ms 7380 KB Output is correct
13 Correct 4 ms 7380 KB Output is correct
14 Correct 4 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 7408 KB Output is correct
18 Correct 4 ms 7380 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 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 5 ms 7336 KB Output is correct
8 Correct 6 ms 7380 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 5 ms 7412 KB Output is correct
11 Correct 4 ms 7380 KB Output is correct
12 Correct 4 ms 7380 KB Output is correct
13 Correct 4 ms 7380 KB Output is correct
14 Correct 4 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 7408 KB Output is correct
18 Correct 4 ms 7380 KB Output is correct
19 Correct 4 ms 7380 KB Output is correct
20 Correct 2614 ms 789072 KB Output is correct
21 Correct 1872 ms 749084 KB Output is correct
22 Correct 1972 ms 780828 KB Output is correct
23 Correct 2016 ms 787640 KB Output is correct
24 Correct 2262 ms 788724 KB Output is correct
25 Correct 2736 ms 789212 KB Output is correct
26 Correct 2645 ms 789312 KB Output is correct
27 Correct 2617 ms 789412 KB Output is correct
28 Correct 2621 ms 789476 KB Output is correct
29 Correct 2647 ms 789484 KB Output is correct
30 Correct 2608 ms 789316 KB Output is correct
31 Correct 2554 ms 789388 KB Output is correct
32 Correct 2624 ms 789404 KB Output is correct
33 Correct 2780 ms 789440 KB Output is correct
34 Correct 2615 ms 789588 KB Output is correct
35 Correct 2603 ms 789688 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 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Incorrect 2529 ms 25120 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 5 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 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 5 ms 7336 KB Output is correct
8 Correct 6 ms 7380 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 5 ms 7412 KB Output is correct
11 Correct 4 ms 7380 KB Output is correct
12 Correct 4 ms 7380 KB Output is correct
13 Correct 4 ms 7380 KB Output is correct
14 Correct 4 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 7408 KB Output is correct
18 Correct 4 ms 7380 KB Output is correct
19 Correct 4 ms 7400 KB Output is correct
20 Correct 533 ms 41992 KB Output is correct
21 Correct 515 ms 42220 KB Output is correct
22 Correct 538 ms 42220 KB Output is correct
23 Correct 528 ms 42216 KB Output is correct
24 Correct 517 ms 42280 KB Output is correct
25 Correct 504 ms 42216 KB Output is correct
26 Correct 422 ms 42208 KB Output is correct
27 Correct 235 ms 42204 KB Output is correct
28 Correct 520 ms 42300 KB Output is correct
29 Correct 530 ms 42300 KB Output is correct
30 Correct 382 ms 42284 KB Output is correct
31 Correct 407 ms 42176 KB Output is correct
32 Correct 241 ms 42672 KB Output is correct
33 Correct 288 ms 41908 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 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 5 ms 7336 KB Output is correct
8 Correct 6 ms 7380 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 5 ms 7412 KB Output is correct
11 Correct 4 ms 7380 KB Output is correct
12 Correct 4 ms 7380 KB Output is correct
13 Correct 4 ms 7380 KB Output is correct
14 Correct 4 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 7408 KB Output is correct
18 Correct 4 ms 7380 KB Output is correct
19 Correct 4 ms 7380 KB Output is correct
20 Correct 2614 ms 789072 KB Output is correct
21 Correct 1872 ms 749084 KB Output is correct
22 Correct 1972 ms 780828 KB Output is correct
23 Correct 2016 ms 787640 KB Output is correct
24 Correct 2262 ms 788724 KB Output is correct
25 Correct 2736 ms 789212 KB Output is correct
26 Correct 2645 ms 789312 KB Output is correct
27 Correct 2617 ms 789412 KB Output is correct
28 Correct 2621 ms 789476 KB Output is correct
29 Correct 2647 ms 789484 KB Output is correct
30 Correct 2608 ms 789316 KB Output is correct
31 Correct 2554 ms 789388 KB Output is correct
32 Correct 2624 ms 789404 KB Output is correct
33 Correct 2780 ms 789440 KB Output is correct
34 Correct 2615 ms 789588 KB Output is correct
35 Correct 2603 ms 789688 KB Output is correct
36 Correct 3319 ms 790088 KB Output is correct
37 Correct 2498 ms 750288 KB Output is correct
38 Correct 2655 ms 780800 KB Output is correct
39 Correct 2672 ms 788228 KB Output is correct
40 Correct 3066 ms 789708 KB Output is correct
41 Correct 3401 ms 789784 KB Output is correct
42 Correct 3297 ms 790024 KB Output is correct
43 Correct 3262 ms 790040 KB Output is correct
44 Correct 2734 ms 790132 KB Output is correct
45 Correct 2585 ms 790256 KB Output is correct
46 Correct 3224 ms 790160 KB Output is correct
47 Correct 3298 ms 790080 KB Output is correct
48 Correct 3227 ms 790120 KB Output is correct
49 Correct 3193 ms 790076 KB Output is correct
50 Correct 2585 ms 790032 KB Output is correct
51 Correct 2578 ms 790056 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 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 5 ms 7336 KB Output is correct
8 Correct 6 ms 7380 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 5 ms 7412 KB Output is correct
11 Correct 4 ms 7380 KB Output is correct
12 Correct 4 ms 7380 KB Output is correct
13 Correct 4 ms 7380 KB Output is correct
14 Correct 4 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 7408 KB Output is correct
18 Correct 4 ms 7380 KB Output is correct
19 Correct 4 ms 7380 KB Output is correct
20 Correct 2614 ms 789072 KB Output is correct
21 Correct 1872 ms 749084 KB Output is correct
22 Correct 1972 ms 780828 KB Output is correct
23 Correct 2016 ms 787640 KB Output is correct
24 Correct 2262 ms 788724 KB Output is correct
25 Correct 2736 ms 789212 KB Output is correct
26 Correct 2645 ms 789312 KB Output is correct
27 Correct 2617 ms 789412 KB Output is correct
28 Correct 2621 ms 789476 KB Output is correct
29 Correct 2647 ms 789484 KB Output is correct
30 Correct 2608 ms 789316 KB Output is correct
31 Correct 2554 ms 789388 KB Output is correct
32 Correct 2624 ms 789404 KB Output is correct
33 Correct 2780 ms 789440 KB Output is correct
34 Correct 2615 ms 789588 KB Output is correct
35 Correct 2603 ms 789688 KB Output is correct
36 Correct 5 ms 7380 KB Output is correct
37 Correct 4 ms 7380 KB Output is correct
38 Correct 4 ms 7380 KB Output is correct
39 Incorrect 2529 ms 25120 KB Output isn't correct
40 Halted 0 ms 0 KB -