oj.uz

Submission #552172

# Submission time Handle Problem Language Result Execution time Memory
552172 2022-04-22T15:03:48 Z Antekb Reconstruction Project (JOI22_reconstruction) C++14
3 / 100
 4468 ms 36404 KB 
#include<bits/stdc++.h>
//#pragma GCC optimize("trapv")
#define st first
#define nd second
#define pb(x) push_back(x)
#define pp(x) pop_back(x)
#define mp(a, b) make_pair(a, b)
#define all(x) (x).begin(), (x).end()
#define rev(x) reverse(all(x))
#define sor(x) sort(all(x))
#define sz(x) (int)(x).size()
#define rsz(x) resize(x)

using namespace std;

///~~~~~~~~~~~~~~~~~~~~~~~~~~

void debug(){cerr<<"\n";}
template <typename H, typename... T>
void debug(H h, T... t) {cerr<<h; if (sizeof...(t)) cerr << ", "; debug(t...);}
#define deb(x...) cerr<<#x<<" = ";debug(x);

///~~~~~~~~~~~~~~~~~~~~~~~~~

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii > vii;
typedef vector<ll> vl;
typedef vector<pll> vll;
typedef string str;

#define BOOST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

const int N=1e5+5, INF=1e9+5, mod=1e9+7;
vector<pair<int, pii> > edg;
int r[N], siz[N];
vector<pair<pii, pair<pii, int> > > Q;
vector<pii> upd;
vector<bool> ans;
int find(int v){
	if(r[v]==v)return v;
	return find(r[v]);
}
void Union(int a, int b){
	a=find(a);
	b=find(b);
	if(a==b){
		upd.pb(mp(0, 0));
		return;
	}
	//if(siz[a]>siz[b])swap(a, b);
	r[a]=b;
	//siz[b]+=siz[a];
	upd.pb(mp(a, b));
}
void Union2(int a, int b){
	
	r[a]=a;
	//siz[b]-=siz[a];
	upd.pp();
}
int L1[N], R1[N], L2[N], R2[N];//[L1, R1] - pierwszy na prawo, ktory moze byc zamiast tej kraw
int K=200;
void solve(){
	sort(Q.begin(), Q.end(), [](pair<pii, pair<pii, int> > a, pair<pii, pair<pii, int> >  b){
		if(a.st.st/K!=b.st.st/K)return a.st.st<b.st.st;
		return a.st.nd<b.st.nd;
	});
	int a=K;
	int b=a;
	vector<pair<pii, pair<pii, int> > > Q2;
	for(int i=0; i<Q.size(); i++){
		if(i && Q[i].st.st/K!=Q[i-1].st.st/K){
			while(upd.size())Union2(upd.back().st, upd.back().nd);
			//for(int j=1; j<=4; j++)assert(r[j]==j && siz[j]==1);
			a=K*(Q[i].st.st/K+1);
			b=a;
		}
		//cout<<upd.size();
		if(b-1>Q[i].st.nd){
			Q2.pb(Q[i]);
			continue;
		}
		while(b<=Q[i].st.nd){
			Union(edg[b].nd.st, edg[b].nd.nd);
			b++;
		}
		for(int j=a-1; j>=Q[i].st.st; j--){
			Union(edg[j].nd.st,edg[j].nd.nd);
		}
		ans[Q[i].nd.nd]=(find(Q[i].nd.st.st)==find(Q[i].nd.st.nd));
		//cout<<upd.size();
		for(int j=Q[i].st.st; j<a; j++){
			Union2(upd.back().st, upd.back().nd);
		}
	}
	while(upd.size())Union2(upd.back().st, upd.back().nd);
	for(auto i:Q2){
		for(int j=i.st.st; j<=i.st.nd; j++){
			Union(edg[j].nd.st, edg[j].nd.nd);
		}
		ans[i.nd.nd]=(find(i.nd.st.st)==find(i.nd.st.nd));		
		for(int j=i.st.nd; j>=i.st.st; j--){
			Union2(upd.back().st, upd.back().nd);
		}
	}
}
void rec(){
	Q.clear();
	for(int i=0; i<edg.size(); i++){
		int m;
		if(L1[i]!=R1[i]){
			m=(L1[i]+R1[i]+1)/2;
			if(R1[i]==-1)m=-1;
			if(m!=-1)Q.pb(mp(mp(m, i-1), mp(edg[i].nd, 2*i)));
		}
		if(L2[i]!=R2[i]){
			m=(L2[i]+R2[i])/2;
			if(m!=edg.size())Q.pb(mp(mp(i+1, m), mp(edg[i].nd, 2*i+1)));
		}
	}
	solve();
	for(int i=0; i<edg.size(); i++){
		int m;
		if(L1[i]!=R1[i]){
			m=(L1[i]+R1[i]+1)/2;
			if(R1[i]==-1)m=-1;
			if(m!=-1){
				if(ans[2*i])L1[i]=m;
				else R1[i]=m-1;
			}
		}
		if(L2[i]!=R2[i]){
			m=(L2[i]+R2[i])/2;
			if(m!=edg.size()){
				if(ans[2*i+1])R2[i]=m;
				else L2[i]=m+1;
			}
		}
	}
}
const int L=500;
int main(){
	BOOST;
	int n, m;
	cin>>n>>m;
	edg.rsz(m);
	for(auto &i:edg)cin>>i.nd.st>>i.nd.nd>>i.st;
	sor(edg);
	for(int i=1; i<=n; i++)siz[i]=1, r[i]=i;
	ans.rsz(2*m);
	for(int i=0; i<m; i++){
		L1[i]=-1;
		R1[i]=i-1;
		for(int j=i-1; j>=-1 && j>i-L; j--){
			if(j!=-1)Union(edg[j].nd.st, edg[j].nd.nd);
			if(j==-1 || find(edg[i].nd.st)==find(edg[i].nd.nd)){
				L1[i]=R1[i]=j;
				break;
			}
		}
		while(upd.size())Union2(upd.back().st, upd.back().nd);
		L2[i]=i+1;
		R2[i]=m;
		for(int j=i+1; j<=m && j<i+L; j++){
			if(j!=m)Union(edg[j].nd.st, edg[j].nd.nd);
			if(j==m || find(edg[i].nd.st)==find(edg[i].nd.nd)){
				L2[i]=R2[i]=j;
				break;
			}
		}
		while(upd.size())Union2(upd.back().st, upd.back().nd);
	}
	//for(int i=0; i<17; i++)rec();
	/*for(int i=0; i<m; i++){
		cout<<edg[i].nd.st<<" "<<edg[i].nd.nd<<" "<<edg[i].st<<"\n";
		cout<<L1[i]<<" "<<R1[i]<<" "<<L2[i]<<" "<<R2[i]<<"\n";
	}*/
	/*Q.clear();
	Q.push_back(mp(mp(0, -1), mp(mp(1 , 2), 0)));
	solve();
	cout<<ans[0];*/
	vector<pair<int, pii>> V;
	for(int i=0; i<m; i++){
		if(L1[i]!=-1)V.pb(mp(edg[L1[i]].st+edg[i].st, mp(1, edg[i].st)));
		else V.pb(mp(-2*INF, mp(1, edg[i].st)));
		V.pb(mp(2*edg[i].st, mp(-2, edg[i].st)));
		if(L2[i]!=m)V.pb(mp(edg[L2[i]].st+edg[i].st, mp(1, edg[i].st)));
	}
	sort(all(V));
	long long sum=0;
	int q;
	cin>>q;
	vector<pii> Q(q);
	for(int i=0; i<q; i++){
		cin>>Q[i].st;
		Q[i].st*=2;
		Q[i].nd=i;
	}
	sort(Q.begin(), Q.end());
	vector<ll> ans2(q);
	int ile=0, wsk=0;
	for(int i=0; i<V.size(); i++){
		while(wsk<q && Q[wsk].st<=V[i].st){
			//cout<<sum<<" "<<ile<<" "<<Q[wsk].st/2<<"\n";
			ans2[Q[wsk].nd]=sum-ile*1ll*(Q[wsk].st/2);
			//cout<<Q[wsk].nd<<" "<<ans2[Q[wsk].nd]<<"\n";
			wsk++;
		}
		ile+=V[i].nd.st;
		sum+=V[i].nd.st*1ll*V[i].nd.nd;
	}
	while(wsk<q){
		ans2[Q[wsk].nd]=sum-ile*1ll*(Q[wsk].st/2);
		wsk++;
	}
	for(ll i:ans2){
		cout<<i<<"\n";
	}
}

Compilation message

reconstruction.cpp: In function 'void solve()':
reconstruction.cpp:77:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<std::pair<int, int>, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |  for(int i=0; i<Q.size(); i++){
      |               ~^~~~~~~~~
reconstruction.cpp: In function 'void rec()':
reconstruction.cpp:115:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |  for(int i=0; i<edg.size(); i++){
      |               ~^~~~~~~~~~~
reconstruction.cpp:124:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |    if(m!=edg.size())Q.pb(mp(mp(i+1, m), mp(edg[i].nd, 2*i+1)));
      |       ~^~~~~~~~~~~~
reconstruction.cpp:128:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |  for(int i=0; i<edg.size(); i++){
      |               ~^~~~~~~~~~~
reconstruction.cpp:140:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |    if(m!=edg.size()){
      |       ~^~~~~~~~~~~~
reconstruction.cpp: In function 'int main()':
reconstruction.cpp:208:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  208 |  for(int i=0; i<V.size(); i++){
      |               ~^~~~~~~~~

Subtask #1
3.0 / 3.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 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct

Subtask #2
0 / 4.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 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Incorrect 4468 ms 9388 KB Output isn't correct
21 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 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Incorrect 1251 ms 36404 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.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 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Incorrect 233 ms 28516 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 35.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 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Incorrect 4468 ms 9388 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 23.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 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Incorrect 4468 ms 9388 KB Output isn't correct
21 Halted 0 ms 0 KB -