Submission #745392

#	Time	Username	Problem	Language	Result	Execution time	Memory
745392		arthur_nascimento	Reconstruction Project (JOI22_reconstruction)	C++14	3 / 100	5044 ms	19008 KiB

reconstruction

#include <bits/stdc++.h>

using namespace std;

 

#define maxn 1010
#define maxE 100100

#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;
	}
	edge(int a=0,int b=0,int w=0) : a(a), b(b), w(w) {}
}

E[maxE];

int n,m;

int mst[2][maxn][maxn];
int mst_len[2][maxn];

int par[maxn];

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

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

void bd(int dir,int ini,int lst){

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

	join(E[ini].a, E[ini].b);
	mst[dir][ini][mst_len[dir][ini]++] = ini;

	for(int i=0;i<mst_len[dir][lst];i++){
		int a = E[mst[dir][lst][i]].a;
		int b = E[mst[dir][lst][i]].b;
		if(find(a) == find(b)) continue;
		mst[dir][ini][mst_len[dir][ini]++] = mst[dir][lst][i];
		join(a,b);
	}

}

ll get(vector<int> dir, vector<int> ini ,int X){

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

	ll ans = 0;

	vector<int> pos (2,0);
	vector<int> len = {mst_len[dir[0]][ini[0]], mst_len[dir[1]][ini[1]] };
	int * arr[] = {mst[dir[0]][ini[0]], mst[dir[1]][ini[1]]};

	debug("esq is %d len %d, dir is %d len %d\n",ini[0],len[0],ini[1],len[1]);

	while(pos[0] < len[0] || pos[1] < len[1]){

		int go = 0;
		if(pos[0] == len[0])
			go = 1;

		if(pos[0] < len[0] && pos[1] < len[1]){

			if( abs(E[arr[0][pos[0]]].w - X) < abs(E[arr[1][pos[1]]].w - X) )
				go = 0;
			else
				go = 1;
				
		}
		
		int a = E[arr[go][pos[go]]].a;
		int b = E[arr[go][pos[go]]].b;
		int w = E[arr[go][pos[go]]].w;
		debug("proc (%d,%d)\n",a,b);

		pos[go]++;

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

		debug("added (%d,%d), w = %d\n",a,b,w);

		join(a,b);

		ans += abs(w-X);

	}

	return ans;

}


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);

	mst[0][0][0] = 0;
	mst_len[0][0] = 1;

	for(int i=1;i<m;i++)
		bd(0,i,i-1);

	mst[1][m-1][0] = m-1;
	mst_len[1][m-1] = 1;

	for(int i=m-2;i>=0;i--)
		bd(1,i,i+1);

	int q;
	scanf("%d",&q);

	while(q--){

		int X;
		scanf("%d",&X);

		int up = lower_bound(E,E+m,edge(0,0,X)) - E;
		int lo = up; if(lo) lo--;

		printf("%lld\n",get({0,1},{lo,up},X));

	}

}

Compilation message (stderr)

reconstruction.cpp: In function 'long long int get(std::vector<int>, std::vector<int>, int)':
reconstruction.cpp:76:8: warning: left operand of comma operator has no effect [-Wunused-value]
   76 |  debug("esq is %d len %d, dir is %d len %d\n",ini[0],len[0],ini[1],len[1]);
      |        ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:96:9: warning: left operand of comma operator has no effect [-Wunused-value]
   96 |   debug("proc (%d,%d)\n",a,b);
      |         ^~~~~~~~~~~~~~~~
reconstruction.cpp:96:28: warning: right operand of comma operator has no effect [-Wunused-value]
   96 |   debug("proc (%d,%d)\n",a,b);
      |                            ^
reconstruction.cpp:103:9: warning: left operand of comma operator has no effect [-Wunused-value]
  103 |   debug("added (%d,%d), w = %d\n",a,b,w);
      |         ^~~~~~~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:103:37: warning: right operand of comma operator has no effect [-Wunused-value]
  103 |   debug("added (%d,%d), w = %d\n",a,b,w);
      |                                     ^
reconstruction.cpp:103:39: warning: right operand of comma operator has no effect [-Wunused-value]
  103 |   debug("added (%d,%d), w = %d\n",a,b,w);
      |                                       ^
reconstruction.cpp: At global scope:
reconstruction.cpp:116:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  116 | main(){
      | ^~~~
reconstruction.cpp: In function 'int main()':
reconstruction.cpp:118:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |  scanf("%d%d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
reconstruction.cpp:121:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |   scanf("%d%d%d",&E[i].a,&E[i].b,&E[i].w), E[i].a--, E[i].b--;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:139:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  139 |  scanf("%d",&q);
      |  ~~~~~^~~~~~~~~
reconstruction.cpp:144:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |   scanf("%d",&X);
      |   ~~~~~^~~~~~~~~

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