Submission #576204

#	Time	Username	Problem	Language	Result	Execution time	Memory
576204		jamezzz	Reconstruction Project (JOI22_reconstruction)	C++17	100 / 100	1321 ms	27192 KiB

reconstruction

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

#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;

#define maxn 505
#define maxm 100005

int n,m,par[maxn],rnk[maxn],s[maxm];
vector<iii> EL,c;
bool done[maxm];

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

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);
	
	pair<ll,ll> val;
	for(int i=0;i<m;++i){
		int a,b,w;
		sf("%d%d%d",&a,&b,&w);
		EL.pb({w,{a,b}});
		
		c.pb({w,{2,-2*w}});
	}
	sort(all(EL));
	
	for(int i=0;i<m;++i){
		if(done[i])continue;
		val.fi-=1;
		val.se+=EL[i].fi;
		int cur=i;
		while(true){
			int a,b;
			tie(a,b)=EL[cur].se;
			
			init();
			int e=cur++;
			while(cur<m){
				int x,y;
				tie(x,y)=EL[cur].se;
				join(x,y);
				if(fp(a)==fp(b))break;
				++cur;
			}
			
			done[e]=true;
			if(fp(a)!=fp(b))break;
			
			int w1=EL[e].fi,w2=EL[cur].fi;
			c.pb({(w1+w2+1)/2,{-2,w1+w2}});
		}
	}
	sort(all(c));
	
	int q;sf("%d",&q);
	int cur=0;
	for(int i=0;i<q;++i){
		int x;sf("%d",&x);
		while(cur!=sz(c)&&c[cur].fi<=x){
			val.fi+=c[cur].se.fi;
			val.se+=c[cur].se.se;
			++cur;
		}
		pf("%lld\n",val.fi*x+val.se);
	}
}

Compilation message (stderr)

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

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