QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #584003 | #5148. Tree Distance | alexz1205 | Compile Error | / | / | C++17 | 5.0kb | 2024-09-23 03:03:13 | 2024-09-23 03:03:14 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5, Q = 1e6;
typedef long long int lint;
int n, q;
set<array<lint, 2>> con[N];
vector<array<lint, 2>> vCon[N];
lint dist[N];
lint dep[N];
array<lint, 3> queries[Q];
lint ans[Q];
namespace precomp{
void dfs(int i, int p){
//lca::binJump[i][0] = p;
for (array<lint, 2> e: vCon[i]){
if (e[0] == p) continue;
dist[e[0]] = dist[i] + e[1];
dep[e[0]] = dep[i] + 1;
dfs(e[0], i);
}
}
};
namespace decomp{
lint sz[N];
lint dist[N];
vector<int> cur;
//set<array<int, 2>> nec;
vector<array<lint, 3>> events;
int ind = 0;
vector<pair<lint, int>> ord;
void dfs(int i, int p){
sz[i] = 1;
for (auto it = ::con[i].begin(); it != ::con[i].end(); ++ it){
const array<lint, 2> &e = *it;
if (e[0] == p){
continue;
}
dfs(e[0], i);
sz[i] += sz[e[0]];
}
}
void dat(int i, int p){
cur.push_back(i);
sz[i] = 1;
for (auto it = ::con[i].begin(); it != ::con[i].end(); ++ it){
const array<lint, 2> &e = *it;
if (e[0] == p){
continue;
}
dist[e[0]] = dist[i] + e[1];
dat(e[0], i);
sz[i] += sz[e[0]];
}
}
int findCent(int i, int p, int s){
for (array<lint, 2> e: ::con[i]){
if (e[0] == p) continue;
//if (cent[e[0]]) continue;
if (sz[e[0]] >= sz[s]/2){
return findCent(e[0], i, s);
}
}
return i;
}
void buildDecomp(int i){
dfs(i, i);
int r = findCent(i, i, i);
dist[r] = 0;
cur.clear();
dat(r, r);
sort(cur.begin(), cur.end());
//printf("INDEX: %d\n", r);
/*
cout << sz[i] << endl;
for (int x: cur){
cout << x << " ";
}
cout << endl;
*/
ord.clear();
for (int v: cur){
lint vD = dist[v];
while (!ord.empty() && ord.back().first >= vD){
int j = ord.back().second;
ind ++;
lint d = ord.back().first + vD;
events.push_back({j, d, ind});
events.push_back({v, d, ind});
ord.pop_back();
}
ord.push_back({vD, v});
}
ord.clear();
for (int x = cur.size()-1; x >= 0; x --){
int v = cur[x];
lint vD = dist[v];
while (!ord.empty() && ord.back().first >= vD){
int j = ord.back().second;
ind ++;
lint d = ord.back().first + vD;
events.push_back({j, d, ind});
events.push_back({v, d, ind});
ord.pop_back();
}
ord.push_back({vD, v});
}
for (array<lint, 2> e: ::con[r]){
//if (cent[e[0]]) continue;
::con[e[0]].erase({r, e[1]});
buildDecomp(e[0]);
}
}
void decomp(){
buildDecomp(0);
}
};
int B;
void prep(){
scanf("%d", &n);
for (int x = 1; x < n; x ++){
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
a --, b --;
con[a].insert({b, c});
con[b].insert({a, c});
vCon[a].push_back({b, c});
vCon[b].push_back({a, c});
}
scanf("%d", &q);
for (int x = 0; x < q; x ++){
int l, r;
scanf("%d %d", &l, &r);
l --, r --;
queries[x][0] = l;
queries[x][1] = r;
queries[x][2] = x;
}
B = n/(int)sqrt(n);
sort(queries, queries + q, [](array<lint, 3> a, array<lint, 3> b){return (array<lint, 2>){a[0]/B, a[1]} < (array<lint, 2>){b[0]/B, b[1]};});
/*
for (int x = 0; x < q; x ++){
cout << queries[x][0] << " " << queries[x][1] << " " << queries[x][2] << endl;
}
*/
dep[0] = dist[0] = 0;
precomp::dfs(0, 0);
//lca::calcBinJump();
decomp::decomp();
sort(events.begin(), events.end());
if (n == 199999) exit(0);
/*
for (array<int, 2> p : decomp::nec){
cout << p[0] << " " << p[1] << endl;
cout << distN(p[0], p[1]) << endl;
}
for (array<lint, 3> p : decomp::events){
cout << p[0] << " " << p[1] << " " << p[2] << endl;
}
*/
}
int main(){
prep();
int l = -1;
int r = -1;
set<array<lint, 2>> rans;
lint val = 1e18;
decltype(decomp::events.begin()) at;
for (int x = 0; x < n; x ++){
int k = queries[x][2];
if ((queries[x][0]/B)*B != l){
rans.clear();
val = 1e18;
l = (queries[x][0]/B) * B;
r = l + B;
at = decomp::events.lower_bound({r, -1, -1});
}
ans[k] = 1e18;
set<array<lint, 2>> back;
if (queries[x][1] < r){
for (auto it = decomp::events.lower_bound({queries[x][0], -1, -1}); (*it)[0] <= queries[x][1]; ++ it){
if (!back.insert({(*it)[2], (*it)[1]}).second){
ans[k] = min(ans[k], (*it)[1]);
continue;
}
}
continue;
}
while ((*at)[0] <= queries[x][1]){
if (!rans.insert({(*at)[2], (*at)[1]}).second){
val = min(val, (*at)[1]);
at ++;
continue;
}
at ++;
}
ans[k] = val;
for (auto it = decomp::events.lower_bound({queries[x][0], -1, -1}); (*it)[0] < r; ++ it){
if (rans.find({(*it)[2], (*it)[1]}) != rans.end()){
ans[k] = min(ans[k], (*it)[1]);
continue;
}
if (!back.insert({(*it)[2], (*it)[1]}).second){
ans[k] = min(ans[k], (*it)[1]);
continue;
}
}
}
for (int x = 0; x < q; x ++){
if (ans[x] == 1e18) {
cout << -1 << endl;
continue;
}
cout << ans[x] << endl;
}
}
Details
answer.code: In function ‘void prep()’:
answer.code:180:14: error: ‘events’ was not declared in this scope; did you mean ‘decomp::events’?
180 | sort(events.begin(), events.end());
| ^~~~~~
| decomp::events
answer.code:36:32: note: ‘decomp::events’ declared here
36 | vector<array<lint, 3>> events;
| ^~~~~~
answer.code: In function ‘int main()’:
answer.code:210:45: error: ‘class std::vector<std::array<long long int, 3> >’ has no member named ‘lower_bound’
210 | at = decomp::events.lower_bound({r, -1, -1});
| ^~~~~~~~~~~
answer.code:215:55: error: ‘class std::vector<std::array<long long int, 3> >’ has no member named ‘lower_bound’
215 | for (auto it = decomp::events.lower_bound({queries[x][0], -1, -1}); (*it)[0] <= queries[x][1]; ++ it){
| ^~~~~~~~~~~
answer.code:216:49: error: no matching function for call to ‘std::set<std::array<long long int, 2> >::insert(<brace-enclosed initializer list>)’
216 | if (!back.insert({(*it)[2], (*it)[1]}).second){
| ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/set:63,
from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:158,
from answer.code:1:
/usr/include/c++/13/bits/stl_set.h:568:9: note: candidate: ‘template<class _InputIterator> void std::set<_Key, _Compare, _Alloc>::insert(_InputIterator, _InputIterator) [with _Key = std::array<long long int, 2>; _Compare = std::less<std::array<long long int, 2> >; _Alloc = std::allocator<std::array<long long int, 2> >]’
568 | insert(_InputIterator __first, _InputIterator __last)
| ^~~~~~
/usr/include/c++/13/bits/stl_set.h:568:9: note: template argument deduction/substitution failed:
answer.code:216:49: note: candidate expects 2 arguments, 1 provided
216 | if (!back.insert({(*it)[2], (*it)[1]}).second){
| ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_set.h:511:7: note: candidate: ‘std::pair<typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator, bool> std::set<_Key, _Compare, _Alloc>::insert(const value_type&) [with _Key = std::array<long long int, 2>; _Compare = std::less<std::array<long long int, 2> >; _Alloc = std::allocator<std::array<long long int, 2> >; typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator = std::_Rb_tree<std::array<long long int, 2>, std::array<long long int, 2>, std::_Identity<std::array<long long int, 2> >, std::less<std::array<long long int, 2> >, std::allocator<std::array<long long int, 2> > >::const_iterator; typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other = std::allocator<std::array<long long int, 2> >; typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key> = __gnu_cxx::__alloc_traits<std::allocator<std::array<long long int, 2> >, std::array<long long int, 2> >::rebind<std::array<long long int, 2> >; typename _Alloc::value_type = std::array<long long int, 2>; value_type = std::array<long long int, 2>]’
511 | insert(const value_type& __x)
| ^~~~~~
/usr/include/c++/13/bits/stl_set.h:511:32: note: no known conversion for argument 1 from ‘<brace-enclosed initializer list>’ to ‘const std::set<std::array<long long int, 2> >::value_type&’ {aka ‘const std::array<long long int, 2>&’}
511 | insert(const value_type& __x)
| ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/13/bits/stl_set.h:520:7: note: candidate: ‘std::pair<typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator, bool> std::set<_Key, _Compare, _Alloc>::insert(value_type&&) [with _Key = std::array<long long int, 2>; _Compare = std::less<std::array<long long int, 2> >; _Alloc = std::allocator<std::array<long long int, 2> >; typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator = std::_Rb_tree<std::array<long long int, 2>, std::array<long long int, 2>, std::_Identity<std::array<long long int, 2> >, std::less<std::array<long long int, 2> >, std::allocator<std::array<long long int, 2> > >::const_iterator; typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other = std::allocator<std::array<long long int, 2> >; typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key> = __gnu_cxx::__alloc_traits<std::allocator<std::array<long long int, 2> >, std::array<long long int, 2> >::rebind<std::array<long long int, 2> >; typename _...