제출 #1032417

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1032417		Shayan86	Reconstruction Project (JOI22_reconstruction)	C++14	42 / 100	5084 ms	24356 KiB

reconstruction

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

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

#define pb push_back
#define F first
#define S second
#define sep ' '
#define endl '\n'
#define all(x)      (x).begin(),(x).end()
#define fast_io     ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define set_dec(x)  cout << fixed << setprecision(x);

const ll N = 507;
const ll M = 1e5 + 10;
const ll Q = 1e6 + 10;
const ll S = 507;
const ll S2	= 200;

int n, m, q, x[Q], c, sz[N], par[N];

vector<pair<int, pii>> edge, block[S], g, lft, rit;

vector<int> qu[S];

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 false;
	if(sz[v] < sz[u]) swap(u, v);
	sz[v] += sz[u]; par[u] = v;
	return true;
}

int main(){
	fast_io;

	cin >> n >> m;

	for(int i = 1; i <= m; i++){
		int u, v, w;
		cin >> u >> v >> w;
		edge.pb({w, {u, v}});
	}
	sort(all(edge));

	for(int i = 0; i < m; i++) block[i/S2].pb(edge[i]);
	c = (m + S2 - 1) / S2;

	cin >> q;

	for(int i = 0; i < q; i++) cin >> x[i];

	int cur = 0;
	for(int i = 0; i < q; i++){
		while(cur < c && x[i] >= block[cur][0].F) cur++;
		qu[cur].pb(x[i]);
	}

	for(int i = 0; i <= c; i++){
		lft.clear();
		rit.clear();

		for(int j = 1; j <= n; j++){
			sz[j] = 1; par[j] = j;
		}
		for(int j = i; j < c; j++){
			for(auto [w, e]: block[j]){
				if(Union(e.F, e.S)) rit.pb({w, e});
			}
		}
		for(int j = 1; j <= n; j++){
			sz[j] = 1; par[j] = j;
		}
		for(int j = i-2; j >= 0; j--){
			int SZ = block[j].size();
			for(int k = SZ-1; k >= 0; k--){
				auto y = block[j][k];
				auto w = y.F;
				auto e = y.S;
				if(Union(e.F, e.S)) lft.pb({w, e});
			}
		}

		for(int j: qu[i]){
			g.clear();
			for(auto [w, e]: lft) g.pb({j-w, e});
			for(auto [w, e]: rit) g.pb({w-j, e});
			for(auto [w, e]: block[i-1]) g.pb({abs(w-j), e});
			sort(all(g));

			for(int k = 1; k <= n; k++){
				sz[k] = 1; par[k] = k;
			}
			ll sum = 0;
			for(auto [w, e]: g) if(Union(e.F, e.S)) sum += w;
			cout << sum << endl;
		}

	}


}

/*

5 10
1 2 8
1 3 13
1 4 5
1 5 11
1 5 3
2 3 7
2 4 15
3 4 6
3 5 6
4 5 2
6
3
6
8
10
13
17

*/

컴파일 시 표준 에러 (stderr) 메시지

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:76:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   76 |    for(auto [w, e]: block[j]){
      |             ^
reconstruction.cpp:95:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   95 |    for(auto [w, e]: lft) g.pb({j-w, e});
      |             ^
reconstruction.cpp:96:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   96 |    for(auto [w, e]: rit) g.pb({w-j, e});
      |             ^
reconstruction.cpp:97:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   97 |    for(auto [w, e]: block[i-1]) g.pb({abs(w-j), e});
      |             ^
reconstruction.cpp:104:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  104 |    for(auto [w, e]: g) if(Union(e.F, e.S)) sum += w;
      |             ^

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