Submission #572924

#	Time	Username	Problem	Language	Result	Execution time	Memory
572924		jamezzz	Reconstruction Project (JOI22_reconstruction)	C++17	7 / 100	5047 ms	10564 KiB

reconstruction

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

#ifdef DEBUG
#define dbg(...) printf(__VA_ARGS__);
#define getchar_unlocked getchar
#else
#define dbg(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(), x.end()
#define disc(x) sort(all(x));x.resize(unique(all(x))-x.begin());
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vll;
mt19937 rng(time(0));

#define mod 1000000007

inline int add(int a,int b){
	int r=a+b;
	while(r>=mod)r-=mod;
	while(r<0)r+=mod;
	return r;
}

inline int mult(int a,int b){
	return (int)(((ll)(a*b))%mod);
}

inline int rd(){
	int x=0;
	char ch=getchar_unlocked();
	while(!(ch&16))ch=getchar();//keep reading while current character is whitespace
    while(ch&16){//this will break when ‘\n’ or ‘ ‘ is encountered
		x=(x<<3)+(x<<1)+(ch&15);
		ch=getchar_unlocked();
	}
	return x;
}

int n,m,q,par[505],rnk[505];
vector<pair<int,ii>> EL;

void init(){
	for(int i=1;i<=n;++i)rnk[i]=1,par[i]=i;
}

int fp(int i){
	return (par[i]==i)?i:par[i]=fp(par[i]);
}

void join(int x,int y){
	x=fp(x),y=fp(y);
	if(x==y)return;
	if(rnk[x]<rnk[y])par[x]=y;
	else par[y]=x;
	if(rnk[x]==rnk[y])++rnk[x];
}

int main(){
	sf("%d%d",&n,&m);
	for(int i=0;i<m;++i){
		int a,b,w;sf("%d%d%d",&a,&b,&w);
		EL.pb({w,{a,b}});
	}
	sort(all(EL));
	int cur=0;
	sf("%d",&q);
	for(int i=0;i<q;++i){
		int x;sf("%d",&x);
		while(cur!=m-1&&abs(EL[cur].fi-x)>=abs(EL[cur+1].fi-x))++cur;
		init();
		int l=cur,r=cur,take=0;
		ll ans=0;
		while(take!=n-1){
			int w,a,b;
			if(l==-1||(r!=m&&abs(EL[l].fi-x)>abs(EL[r].fi-x))){
				w=EL[r].fi;
				tie(a,b)=EL[r++].se;
			}
			else{
				w=EL[l].fi;
				tie(a,b)=EL[l--].se;
			}
			if(fp(a)==fp(b))continue;
			take++;
			join(a,b);
			ans+=abs(w-x);
		}
		dbg("ans: ");
		pf("%lld\n",ans);
	}
}

Compilation message (stderr)

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:77:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |  sf("%d%d",&n,&m);
      |    ^
reconstruction.cpp:79:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |   int a,b,w;sf("%d%d%d",&a,&b,&w);
      |               ^
reconstruction.cpp:84:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |  sf("%d",&q);
      |    ^
reconstruction.cpp:86:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |   int x;sf("%d",&x);
      |           ^

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