이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
// #define int long long
#define ll long long
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define debug(x) [](decltype(x) _x){cerr << #x << " = " << _x << endl; return _x;}(x);
using pii = pair<int, int>;
const int inf = 1 << 30;
ll pc = 0;
ll pl;
ll now() {
return chrono::system_clock().now().time_since_epoch().count();
}
void pstart() {
pl = now();
}
void pend() {
pc += now() - pl;
}
struct dsu {
short p[500];
dsu(int n) {
for(int i = 0; i < 500; i++) {
p[i] = -1;
}
}
int find(int x) {
return p[x] < 0 ? x : p[x] = find(p[x]);
}
void merge(int x, int y) {
x = find(x);
y = find(y);
if(x == y) return;
if(p[x] < p[y]) swap(x, y);
p[y] += p[x];
p[x] = y;
}
};
struct my_hash {
size_t operator()(int x) const {
return x * 31;
}
};
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
// ll start = now();
int n, m; cin >> n >> m;
struct edge {
short a, b;
int w;
};
vector<edge> el(m);
for(int i = 0; i < m; i++) {
cin >> el[i].a >> el[i].b >> el[i].w;
el[i].a--; el[i].b--;
}
sort(all(el), [&](edge a, edge b) {
return a.w < b.w;
});
int q; cin >> q;
vector<int> x(q);
for(int i = 0; i < q; i++) {
cin >> x[i];
}
auto sx = x;
sort(all(sx));
gp_hash_table<int, ll, my_hash> ans;
int cnt = 0;
function<void(int, int, vector<int>)> dnc = [&](int ql, int qr, vector<int> es) {
if(ql == qr) return;
if(es.size() == n - 1) {
cnt += qr - ql;
for(int i = ql; i < qr; i++) {
ll tot = 0;
for(auto j : es) {
tot += abs(el[j].w - sx[i]);
}
ans[sx[i]] = tot;
}
return;
}
int qm = (ql + qr) / 2;
int qw = sx[qm];
// debug(qw);
// if(qw == 8) {
// for(auto e : el) {
// cerr << e.a << " " << e.b << " " << e.w << endl;
// }
// cerr << endl;
// }
int loc = 0, eqc = 0, hic = 0;
for(auto i : es) {
if(el[i].w < qw) loc++;
else if(el[i].w > qw) hic++;
}
vector<int> lo(es.begin(), es.begin() + loc), eq(es.begin() + loc, es.end() - hic), hi(es.end() - hic, es.end());
reverse(all(lo));
int ls = lo.size(), hs = hi.size();
vector<int> lou, equ, hiu;
lou.reserve(128);
equ.reserve(128);
hiu.reserve(128);
dsu uf(n);
int ec = 0;
for(auto i : eq) {
if(uf.find(el[i].a) != uf.find(el[i].b)) {
uf.merge(el[i].a, el[i].b);
equ.push_back(i);
ec++;
}
}
int loi = 0, hii = 0;
ll tot = 0;
while(ec < n - 1) {
bool dlo = false;
if(hii == hi.size()) dlo = true;
else if(loi == lo.size()) dlo = false;
else dlo = qw - el[lo[loi]].w < el[hi[hii]].w - qw;
if(dlo) {
int i = lo[loi];
loi++;
if(uf.find(el[i].a) != uf.find(el[i].b)) {
uf.merge(el[i].a, el[i].b);
// pstart();
lou.push_back(i);
// pend();
tot += qw - el[i].w;
ec++;
}
} else {
int i = hi[hii];
hii++;
if(uf.find(el[i].a) != uf.find(el[i].b)) {
uf.merge(el[i].a, el[i].b);
// pstart();
hiu.push_back(i);
// pend();
tot += el[i].w - qw;
ec++;
}
}
}
ans[qw] = tot;
reverse(all(lo));
reverse(all(hi));
lo.reserve(lo.size() + equ.size() + hiu.size());
hi.reserve(hi.size() + equ.size() + lou.size());
for(auto i : equ) {
lo.push_back(i);
hi.push_back(i);
// if(qw == 8) cerr << i.a << " " << i.b << " " << i.w << endl;
}
for(auto i : lou) {
hi.push_back(i);
// if(qw == 8) cerr << i.a << " " << i.b << " " << i.w << endl;
}
for(auto i : hiu) {
lo.push_back(i);
// if(qw == 8) cerr << i.a << " " << i.b << " " << i.w << endl;
}
reverse(all(hi));
dnc(ql, qm, move(lo));
dnc(qm + 1, qr, move(hi));
// dnc(ql, qm, el);
// dnc(qm + 1, qr, el);
};
vector<int> id(m);
iota(all(id), 0);
dnc(0, q, id);
for(auto i : x) {
cout << ans[i] << "\n";
}
// ll end = now();
// debug((double)pc / (end - start));
// debug(cnt);
}
컴파일 시 표준 에러 (stderr) 메시지
reconstruction.cpp: In lambda function:
reconstruction.cpp:84:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
84 | if(es.size() == n - 1) {
| ~~~~~~~~~~^~~~~~~~
reconstruction.cpp:129:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
129 | if(hii == hi.size()) dlo = true;
| ~~~~^~~~~~~~~~~~
reconstruction.cpp:130:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
130 | else if(loi == lo.size()) dlo = false;
| ~~~~^~~~~~~~~~~~
reconstruction.cpp:104:18: warning: unused variable 'eqc' [-Wunused-variable]
104 | int loc = 0, eqc = 0, hic = 0;
| ^~~
reconstruction.cpp:111:9: warning: unused variable 'ls' [-Wunused-variable]
111 | int ls = lo.size(), hs = hi.size();
| ^~
reconstruction.cpp:111:25: warning: unused variable 'hs' [-Wunused-variable]
111 | int ls = lo.size(), hs = hi.size();
| ^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |