제출 #1034023

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1034023		1L1YA	Reconstruction Project (JOI22_reconstruction)	C++17	0 / 100	637 ms	37564 KiB

reconstruction

//1L1YA

#include<bits/stdc++.h>
using namespace std;

//#pragma GCC optimize ("O3,unrool-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

typedef long long       ll;
typedef pair<ll,ll>     pll;
typedef pair<int,int>   pii;

#define Pb              push_back
#define F               first
#define S               second
#define endl            '\n'
#define sep             ' '
#define all(x)          x.begin(),x.end()
#define al(x,n)         x+1,x+n+1
#define SZ(x)           ((int)x.size())
#define lc              (id<<1)
#define rc              (lc|1)
#define mid             (l+r>>1)
#define dokme(x)        cout << x << endl, exit(0)
#define sik(x)          cout << x << endl;continue;
#define FastIO          ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define FileIO          freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);

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

const ll oo=1e18;
const int mod=1e9+7;
const int inf=1e9+111;
const int N=1e6+11;
const int lg=23;

int n,m,q,l[N],r[N],sz[N],ps1[N],ps2[N],par[N];
vector<pair<int,pii>> E;
vector<int> Q;

int getpar(int v){
	return par[v]==v?v:par[v]=getpar(par[v]);
}

bool Union(int u,int v){
	u=getpar(u);v=getpar(v);
	if(u==v)	return 0;
	if(sz[u]>sz[v])	swap(u,v);
	sz[v]+=sz[u];
	par[u]=v;
	return 1;
}

int main(){
	FastIO

	cin >> n >> m;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin >> u >> v >> w;
		E.Pb({w,{u,v}});
	}
	E.Pb({0,{0,0}});
	sort(all(E));
	cin >> q;
	for(int i=1;i<=q;i++){
		int x;cin >> x;
		Q.Pb(x);
	}
	fill(r,r+m+1,m+1);
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++)	par[j]=j,sz[j]=1;
		int j=i-1;
		while(j){
			Union(E[j].S.F,E[j].S.S);
			if(getpar(E[i].S.F)==getpar(E[i].S.S))	break;
			j--;
		}
		l[i]=j;
		r[j]=i;
	}
	for(int i=1;i<=m;i++){
		int L=0;
		if(l[i])	L=lower_bound(all(Q),(E[l[i]].F+E[i].F+1)/2)-Q.begin();
		int k=lower_bound(all(Q),E[i].F)-Q.begin();
		int R=q;
		if(r[i]!=m+1)	R=lower_bound(all(Q),(E[i].F+E[r[i]].F-1)/2+1)-Q.begin();
		ps1[L]+=E[i].F;
		ps1[k]-=E[i].F*2;
		ps1[R]+=E[i].F;
		ps2[L]--;
		ps2[k]+=2;
		ps2[R]--;
	}
	for(int i=0;i<q;i++){
		cout << ps1[i]+ps2[i]*Q[i] << endl;
		ps1[i+1]+=ps1[i];ps2[i+1]+=ps2[i];
	}

	return 0;
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 4
• Subtask 3: 0 / 7
• Subtask 4: 0 / 28
• Subtask 5: 0 / 35
• Subtask 6: 0 / 23