結果

問題 No.1212 Second Path
ユーザー yosupot
提出日時 2020-08-30 14:33:04
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 664 ms / 3,000 ms
コード長 10,861 bytes
コンパイル時間 2,198 ms
コンパイル使用メモリ 136,288 KB
最終ジャッジ日時 2025-01-13 21:50:38
ジャッジサーバーID
(参考情報)
judge1 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx")
//#undef LOCAL
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <complex>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;
#include <unistd.h>
struct Scanner {
int fd = -1;
char line[(1 << 15) + 1];
size_t st = 0, ed = 0;
void reread() {
memmove(line, line + st, ed - st);
ed -= st;
st = 0;
ed += ::read(fd, line + ed, (1 << 15) - ed);
line[ed] = '\0';
}
bool succ() {
while (true) {
if (st == ed) {
reread();
if (st == ed) return false;
}
while (st != ed && isspace(line[st])) st++;
if (st != ed) break;
}
if (ed - st <= 50) {
bool sep = false;
for (size_t i = st; i < ed; i++) {
if (isspace(line[i])) {
sep = true;
break;
}
}
if (!sep) reread();
}
return true;
}
template <class T, enable_if_t<is_same<T, string>::value, int> = 0>
bool read_single(T& ref) {
if (!succ()) return false;
while (true) {
size_t sz = 0;
while (st + sz < ed && !isspace(line[st + sz])) sz++;
ref.append(line + st, sz);
st += sz;
if (!sz || st != ed) break;
reread();
}
return true;
}
template <class T, enable_if_t<is_integral<T>::value>* = nullptr>
bool read_single(T& ref) {
if (!succ()) return false;
bool neg = false;
if (line[st] == '-') {
neg = true;
st++;
}
ref = T(0);
while (isdigit(line[st])) {
ref = 10 * ref + (line[st++] & 0xf);
}
if (neg) ref = -ref;
return true;
}
template <class T> bool read_single(V<T>& ref) {
for (auto& d : ref) {
if (!read_single(d)) return false;
}
return true;
}
void read() {}
template <class H, class... T> void read(H& h, T&... t) {
bool f = read_single(h);
assert(f);
read(t...);
}
int read_unsafe() { return 0; }
template <class H, class... T> int read_unsafe(H& h, T&... t) {
bool f = read_single(h);
if (!f) return 0;
return 1 + read_unsafe(t...);
}
Scanner(FILE* fp) : fd(fileno(fp)) {}
};
struct Printer {
public:
template <bool F = false> void write() {}
template <bool F = false, class H, class... T>
void write(const H& h, const T&... t) {
if (F) write_single(' ');
write_single(h);
write<true>(t...);
}
template <class... T> void writeln(const T&... t) {
write(t...);
write_single('\n');
}
Printer(FILE* _fp) : fp(_fp) {}
~Printer() { flush(); }
private:
static constexpr size_t SIZE = 1 << 15;
FILE* fp;
char line[SIZE], small[50];
size_t pos = 0;
void flush() {
fwrite(line, 1, pos, fp);
pos = 0;
}
void write_single(const char& val) {
if (pos == SIZE) flush();
line[pos++] = val;
}
template <class T, enable_if_t<is_integral<T>::value>* = nullptr>
void write_single(T val) {
if (pos > (1 << 15) - 50) flush();
if (val == 0) {
write_single('0');
return;
}
if (val < 0) {
write_single('-');
val = -val; // todo min
}
size_t len = 0;
while (val) {
small[len++] = char(0x30 | (val % 10));
val /= 10;
}
for (size_t i = 0; i < len; i++) {
line[pos + i] = small[len - 1 - i];
}
pos += len;
}
void write_single(__int128 val) {
if (pos > (1 << 15) - 50) flush();
if (val == 0) {
write_single('0');
return;
}
if (val < 0) {
write_single('-');
val = -val; // todo min
}
size_t len = 0;
while (val) {
small[len++] = char(0x30 | (val % 10));
val /= 10;
}
for (size_t i = 0; i < len; i++) {
line[pos + i] = small[len - 1 - i];
}
pos += len;
}
void write_single(const string& s) {
for (char c : s) write_single(c);
}
void write_single(const char* s) {
size_t len = strlen(s);
for (size_t i = 0; i < len; i++) write_single(s[i]);
}
template <class T> void write_single(const V<T>& val) {
auto n = val.size();
for (size_t i = 0; i < n; i++) {
if (i) write_single(' ');
write_single(val[i]);
}
}
};
Scanner sc = Scanner(stdin);
Printer pr = Printer(stdout);
struct TTNode {
using NP = TTNode*;
bool rev = false;
array<array<NP, 2>, 2> ch = {}; // tree, light-tree
NP p = nullptr, lt = nullptr;
struct D {
ll top = TEN(18), last = TEN(18), all_min = TEN(18), dist = 0;
// l is parent of r
static D merge_h(const D& l, const D& r) {
return {l.top, r.last, min(l.all_min, r.all_min), l.dist + r.dist};
}
// l and r is parallel
static D merge_w(const D& l, const D& r) {
return {min(l.top, r.top), -1, -1, -1};
}
// add parent for r(subtrees)
static D join(const D& l, const D& r) {
return {l.top, l.last, min(l.all_min, r.top), l.dist};
}
D rev() { return D{last, top, all_min, dist}; }
D to_subs() { return D{top, -1, -1, -1}; }
};
D single = D(), sub = D(), subs = D();
void init_node(ll x) {
single = D{x, x, TEN(18), x == TEN(18) ? 0 : x};
update();
}
void update_subs() {
subs = sub.to_subs();
if (ch[1][0]) subs = D::merge_w(ch[1][0]->subs, subs);
if (ch[1][1]) subs = D::merge_w(subs, ch[1][1]->subs);
}
void update() {
assert(!rev);
sub = single;
if (lt) sub = D::join(single, lt->subs);
if (ch[0][0]) sub = D::merge_h(ch[0][0]->sub, sub);
if (ch[0][1]) sub = D::merge_h(sub, ch[0][1]->sub);
update_subs();
}
void revdata() {
rev ^= true;
swap(ch[0][0], ch[0][1]); // Important
sub = sub.rev();
update_subs();
}
void push() {
if (rev) {
if (ch[0][0]) ch[0][0]->revdata();
if (ch[0][1]) ch[0][1]->revdata();
rev = false;
}
}
// optimize? : template<int ty>
int pos(int ty) {
if (p) {
if (p->ch[ty][0] == this) return 0;
if (p->ch[ty][1] == this) return 1;
}
return -1;
}
static void con(NP p, NP& cp, NP ch) {
cp = ch;
if (ch) ch->p = p;
}
void rot(int ty) {
int ps = pos(ty);
NP _p = p, q = p->p;
if (ty == 0) {
ch[1] = _p->ch[1];
_p->ch[1].fill(nullptr);
for (auto& x : ch[1])
if (x) x->p = this;
}
con(_p, _p->ch[ty][ps], ch[ty][1 - ps]);
con(this, ch[ty][1 - ps], _p);
_p->update();
update();
p = q;
if (!q) return;
if (q->lt == _p) q->lt = this;
for (auto& v : q->ch)
for (auto& x : v)
if (x == _p) x = this;
q->update();
}
void splay(int ty) {
int ps;
while ((ps = pos(ty)) != -1) {
int pps = p->pos(ty);
if (pps == -1) {
rot(ty);
} else if (ps == pps) {
p->rot(ty);
rot(ty);
} else {
rot(ty);
rot(ty);
}
}
}
void expose() {
supush();
splay(0);
splay(1);
if (NP z = ch[0][1]) {
z->push();
con(z, z->ch[1][1], lt);
lt = z;
ch[0][1] = nullptr;
z->update();
update();
}
NP u = p;
while (u) {
u->splay(0);
u->splay(1);
NP ur = u->lt;
if (auto r = u->ch[0][1]) {
// swap ur, r
r->push();
r->ch[1] = ur->ch[1];
ur->ch[1].fill(nullptr);
for (auto& x : r->ch[1])
if (x) x->p = r;
r->update();
u->lt = r;
} else if (!ur->ch[1][0]) {
// use ur->ch[1][1]
con(u, u->lt, ur->ch[1][1]);
} else {
// use prev(ur) in light-tree
NP q = ur->ch[1][0];
con(u, u->lt, q);
q->push();
while (q->ch[1][1]) {
q = q->ch[1][1];
q->push();
}
q->splay(1);
con(q, q->ch[1][1], ur->ch[1][1]);
q->update();
}
ur->ch[1].fill(nullptr);
ur->update();
u->ch[0][1] = ur;
u->update();
u = u->p;
}
splay(0);
}
void supush() {
if (p) p->supush();
push();
}
void link(NP r) {
evert();
r->expose();
assert(!r->ch[0][1]);
con(r, r->ch[0][1], this);
r->update();
}
void cut() {
expose();
assert(ch[0][0]);
ch[0][0]->p = nullptr;
ch[0][0] = nullptr;
update();
}
void evert() {
expose();
revdata();
expose();
}
};
int main() {
int n;
sc.read(n);
V<TTNode> node(2 * n - 1);
for (int i = 0; i < n; i++) {
node[i].init_node(TEN(18));
}
for (int i = 0; i < n - 1; i++) {
int u, v; ll w;
sc.read(u, v, w); u--; v--;
node[n + i].init_node(w);
node[u].link(&(node[n + i]));
node[n + i].link(&(node[v]));
}
int q;
sc.read(q);
for (int i = 0; i < q; i++) {
int u, v;
sc.read(u, v); u--; v--;
node[u].evert();
node[v].expose();
auto x = node[v].sub;
;
if (x.all_min == TEN(18)) {
pr.writeln(-1);
} else {
pr.writeln(x.all_min * 2 + x.dist);
}
}
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0