Submission #745376

#	Time	Username	Problem	Language	Result	Execution time	Memory
745376		arthur_nascimento	Reconstruction Project (JOI22_reconstruction)	C++14	35 / 100	5061 ms	17088 KiB

reconstruction

#include <bits/stdc++.h>

using namespace std;

 

#define maxn 1001000

#define pb push_back

#define debug 

#define pii pair<int,int>

#define ll long long

#define mod 998244353

#define inf (1<<30)


struct edge {
	int a,b,w;
	bool operator < (edge comp){
		return w < comp.w;
	}
}

E[maxn];

int n,m;

int used[2][maxn];

int Q[maxn];

int par[maxn];

int find(int x){
	return par[x] = (x == par[x]) ? x : find(par[x]);
}

void merge(int a,int b){
	par[find(a)] = find(b);
}

void mst(int X,int id){

	debug("mst %d id %d\n",X,id);

	int ini = 0;
	for(int i=1;i<m;i++)
		if(abs(E[i].w-X) < abs(E[ini].w-X))
			ini = i;

	for(int i=0;i<m;i++) used[id][i] = 0;
	for(int i=0;i<n;i++) par[i] = i;

	merge(E[ini].a, E[ini].b);
	used[id][ini] = 1;
	debug("ini %d, %d %d\n",ini,E[ini].a,E[ini].b);

	int L = ini-1, R = ini+1;

	while(L >= 0 || R <= m-1){

		int get = L;

		if(L < 0) get = R;

		if(L >= 0 && R <= m-1){
			if(abs(E[L].w - X) < abs(E[R].w - X))
				get = L;
			else
				get = R;
		}

		int a = E[get].a, b = E[get].b, w = E[get].w;

		if(get == L) L--;
		else R++;

		if(find(a) == find(b)) continue;

		used[id][get] = 1;

		merge(a,b);

		debug("+ %d %d\n",a,b);

	}

	debug("ok\n");

}

main(){

	scanf("%d%d",&n,&m);

	for(int i=0;i<m;i++){
		scanf("%d%d%d",&E[i].a,&E[i].b,&E[i].w);
		E[i].a--, E[i].b--;
	}

	sort(E,E+m);

	int q;
	scanf("%d",&q);
	for(int i=0;i<q;i++)
		scanf("%d",Q+i);


	int ptr = 0;
	while(ptr < q){

		mst(Q[ptr],0);

		int ini = ptr, fim = q-1;

		debug("ptr %d\n",ptr);
		
		while(ini < fim){
		
			int mid = (ini+fim+1)/2;
			mst(Q[mid],1);
			int eq = 1;

			for(int i=0;i<m;i++)
				if(used[0][i] != used[1][i])
					eq = 0;

			if(eq)
				ini = mid;
			else	
				fim = mid-1;

		}

		vector<int> mst_edges;

		int esq = 0;
		int mult = -(n-1);
		ll sum = 0;

		debug("oi\n");
		for(int i=0;i<m;i++)
			if(used[0][i]){
				mst_edges.pb(i);
				debug("edge %d (%d-%d)\n",i,1+E[i].a,1+E[i].b);
				sum += E[i].w;
			}
		
		for(int i=ptr;i<=fim;i++){
			while(esq < n-1 && E[mst_edges[esq]].w < Q[i]){
				mult+=2;
				sum -= 2 * E[mst_edges[esq]].w;
				esq++;
			}
			printf("%lld\n",(ll)Q[i]*mult + sum);
		}
		
		ptr = fim+1;

	}

	printf("\n");

}

Compilation message (stderr)

reconstruction.cpp: In function 'void mst(int, int)':
reconstruction.cpp:49:8: warning: left operand of comma operator has no effect [-Wunused-value]
   49 |  debug("mst %d id %d\n",X,id);
      |        ^~~~~~~~~~~~~~~~
reconstruction.cpp:49:27: warning: right operand of comma operator has no effect [-Wunused-value]
   49 |  debug("mst %d id %d\n",X,id);
      |                           ^~
reconstruction.cpp:61:8: warning: left operand of comma operator has no effect [-Wunused-value]
   61 |  debug("ini %d, %d %d\n",ini,E[ini].a,E[ini].b);
      |        ^~~~~~~~~~~~~~~~~
reconstruction.cpp:61:37: warning: right operand of comma operator has no effect [-Wunused-value]
   61 |  debug("ini %d, %d %d\n",ini,E[ini].a,E[ini].b);
      |                                     ^
reconstruction.cpp:61:37: warning: right operand of comma operator has no effect [-Wunused-value]
   61 |  debug("ini %d, %d %d\n",ini,E[ini].a,E[ini].b);
      |                              ~~~~~~~^
reconstruction.cpp:89:9: warning: left operand of comma operator has no effect [-Wunused-value]
   89 |   debug("+ %d %d\n",a,b);
      |         ^~~~~~~~~~~
reconstruction.cpp:89:23: warning: right operand of comma operator has no effect [-Wunused-value]
   89 |   debug("+ %d %d\n",a,b);
      |                       ^
reconstruction.cpp:78:35: warning: unused variable 'w' [-Wunused-variable]
   78 |   int a = E[get].a, b = E[get].b, w = E[get].w;
      |                                   ^
reconstruction.cpp:93:8: warning: statement has no effect [-Wunused-value]
   93 |  debug("ok\n");
      |       ~^~~~~~~
reconstruction.cpp: At global scope:
reconstruction.cpp:97:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   97 | main(){
      | ^~~~
reconstruction.cpp: In function 'int main()':
reconstruction.cpp:121:9: warning: left operand of comma operator has no effect [-Wunused-value]
  121 |   debug("ptr %d\n",ptr);
      |         ^~~~~~~~~~
reconstruction.cpp:146:9: warning: statement has no effect [-Wunused-value]
  146 |   debug("oi\n");
      |        ~^~~~~~~
reconstruction.cpp:150:11: warning: left operand of comma operator has no effect [-Wunused-value]
  150 |     debug("edge %d (%d-%d)\n",i,1+E[i].a,1+E[i].b);
      |           ^~~~~~~~~~~~~~~~~~~
reconstruction.cpp:150:40: warning: right operand of comma operator has no effect [-Wunused-value]
  150 |     debug("edge %d (%d-%d)\n",i,1+E[i].a,1+E[i].b);
      |                                        ^
reconstruction.cpp:150:34: warning: right operand of comma operator has no effect [-Wunused-value]
  150 |     debug("edge %d (%d-%d)\n",i,1+E[i].a,1+E[i].b);
      |                                 ~^~~~~~~
reconstruction.cpp:99:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |  scanf("%d%d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
reconstruction.cpp:102:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |   scanf("%d%d%d",&E[i].a,&E[i].b,&E[i].w);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:109:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |  scanf("%d",&q);
      |  ~~~~~^~~~~~~~~
reconstruction.cpp:111:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |   scanf("%d",Q+i);
      |   ~~~~~^~~~~~~~~~

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