QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#243796 | #6404. Shuttle Tour | ucup-team1198# | RE | 1634ms | 202348kb | C++20 | 6.1kb | 2023-11-08 17:28:14 | 2023-11-08 17:28:15 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define ld long double
#define all(a) (a).begin(), (a).end()
const int INF = 1e9;
pair<int, int> combine(const pair<int, int>& a, const pair<int, int>& b) {
return make_pair(min(a.first, b.first), max(a.second, b.second));
}
struct Tree {
vector<int> ids;
vector<int> mns;
vector<int> mxs;
int N;
void init(const vector<int>& _ids) {
ids = _ids;
N = 1;
while (N < ids.size())
N *= 2;
mns.resize(2 * N, INF);
mxs.resize(2 * N, -INF);
}
void reset(int i) {
i += N;
if (mns[i] == INF) {
mns[i] = ids[i - N];
mxs[i] = ids[i - N];
} else {
mns[i] = INF;
mxs[i] = -INF;
}
while (i > 1) {
i >>= 1;
mns[i] = min(mns[2 * i], mns[2 * i + 1]);
mxs[i] = max(mxs[2 * i], mxs[2 * i + 1]);
}
}
pair<int, int> get(int x, int y) {
x += N;
y += N - 1;
pair<int, int> ans(INF, -INF);
while (x <= y) {
if (x & 1) {
ans.first = min(ans.first, mns[x]);
ans.second = max(ans.second, mxs[x]);
}
if (!(y & 1)) {
ans.first = min(ans.first, mns[y]);
ans.second = max(ans.second, mxs[y]);
}
x = (x + 1) >> 1;
y = (y - 1) >> 1;
}
return ans;
}
};
const int MAXN = 200200;
vector<pair<int, int>> G[MAXN];
vector<int> paths_v[MAXN];
vector<long long> paths_pref[MAXN];
int path_cnt = 0;
void dfs(int v, int p, int path_id) {
if (G[v].size() > 2) {
for (auto [u, w] : G[v]) {
if (u == p)
continue;
int cur_path = path_cnt;
++path_cnt;
paths_v[cur_path].emplace_back(v);
paths_pref[cur_path].emplace_back(0);
paths_v[cur_path].emplace_back(u);
paths_pref[cur_path].emplace_back(w);
dfs(u, v, cur_path);
}
} else {
for (auto [u, w] : G[v]) {
if (u == p)
continue;
paths_v[path_id].emplace_back(u);
paths_pref[path_id].push_back(paths_pref[path_id].back() + w);
dfs(u, v, path_id);
}
}
}
vector<int> sorted_v[MAXN];
const int MAXK = 100;
int indices[MAXK][MAXN];
int first_at_least[MAXK][MAXN];
Tree trees[MAXK];
pair<int, int> segms[MAXK];
const pair<int, int> NONE(INF, -INF);
vector<pair<int, int>> G2[MAXN];
pair<long long, long long> go_dfs(int v, int p) {
long long dist_to = -1;
long long sum = 0;
for (auto [u, id] : G2[v]) {
if (id == p)
continue;
auto tmp = go_dfs(u, id);
if (segms[id] == NONE && tmp.first == -1)
continue;
long long dist_to1 = 0;
long long sum1 = 0;
if (segms[id] != NONE) {
dist_to1 = paths_pref[id][segms[id].first];
sum1 += paths_pref[id][segms[id].second] - paths_pref[id][segms[id].first];
if (tmp.first != -1) {
sum1 += paths_pref[id].back() - paths_pref[id][segms[id].second];
sum1 += tmp.first + tmp.second;
}
} else {
dist_to1 = paths_pref[id].back() + tmp.first;
sum1 = tmp.second;
}
sum += sum1;
if (dist_to == -1) {
dist_to = dist_to1;
} else {
sum += dist_to + dist_to1;
dist_to = 0;
}
}
//cout << v << ' ' << dist_to << ' ' << sum << '\n';
return make_pair(dist_to, sum);
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, q;
cin >> n >> q;
string s;
cin >> s;
for (int i = 1; i < n; ++i) {
int a, b, c;
cin >> a >> b >> c;
G[a - 1].emplace_back(b - 1, c);
G[b - 1].emplace_back(a - 1, c);
}
int root = 0;
while (G[root].size() != 1)
++root;
++path_cnt;
paths_v[0].emplace_back(root);
paths_pref[0].emplace_back(0);
dfs(root, -1, 0);
int K = path_cnt;
for (int i = 0; i < K; ++i) {
fill(indices[i], indices[i] + n, -1);
sorted_v[i] = paths_v[i];
sort(sorted_v[i].begin(), sorted_v[i].end());
for (int j = 0; j < sorted_v[i].size(); ++j)
indices[i][sorted_v[i][j]] = j;
first_at_least[i][n] = sorted_v[i].size();
for (int j = n - 1; j >= 0; --j) {
first_at_least[i][j] = indices[i][j] == -1 ? first_at_least[i][j + 1] : indices[i][j];
}
G2[paths_v[i][0]].emplace_back(paths_v[i].back(), i);
G2[paths_v[i].back()].emplace_back(paths_v[i][0], i);
map<int, int> kek;
for (int j = 0; j < paths_v[i].size(); ++j) {
kek[paths_v[i][j]] = j;
}
vector<int> cur_ind(paths_v[i].size());
for (int j = 0; j < sorted_v[i].size(); ++j) {
cur_ind[j] = kek[sorted_v[i][j]];
}
trees[i].init(cur_ind);
/*cout << "path " << i << ": ";
for (int v : paths_v[i])
cout << v << ' ';
cout << '\n';*/
}
for (int i = 0; i < n; ++i) {
if (s[i] == '1') {
for (int j = 0; j < K; ++j) {
if (indices[j][i] != -1)
trees[j].reset(indices[j][i]);
}
}
}
while (q--) {
int t;
cin >> t;
if (t == 1) {
int i;
cin >> i;
--i;
for (int j = 0; j < K; ++j) {
if (indices[j][i] != -1)
trees[j].reset(indices[j][i]);
}
} else {
int l, r;
cin >> l >> r;
--l;
for (int j = 0; j < K; ++j) {
segms[j] = trees[j].get(first_at_least[j][l], first_at_least[j][r]);
}
auto tmp = go_dfs(root, -1);
//cout << tmp.first << ',' << tmp.second << '\n';
if (tmp.first == -1)
cout << -1 << '\n';
else
cout << 2 * tmp.second << '\n';
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 31924kb
input:
5 6 10110 1 2 1 1 3 10 2 4 100 3 5 1000 2 1 5 1 3 2 1 5 2 2 4 2 5 5 2 1 1
output:
222 202 0 -1 0
result:
ok 5 number(s): "222 202 0 -1 0"
Test #2:
score: 0
Accepted
time: 60ms
memory: 81028kb
input:
50 200000 00100100100001101010110100000111100011101110011010 14 47 940241413 11 43 331483591 37 38 496247070 47 46 832459694 7 15 16479291 1 30 402388666 30 8 513064064 46 50 739311480 5 4 761894947 32 41 631669659 17 24 715786564 35 20 763151642 32 33 492466005 39 11 186023146 9 7 805081251 3 42 25...
output:
17149847378 -1 26540740138 29613692754 21307948558 27003443184 11893407374 18332625722 20412196350 20281573062 29727468956 9593307160 9380710234 23682775470 16688997988 2856655228 14982588156 0 -1 9140136614 26193602866 22558599316 24807163344 19126284190 8533875940 7695830712 18079494744 0 27004673...
result:
ok 100000 numbers
Test #3:
score: 0
Accepted
time: 66ms
memory: 85348kb
input:
50 200000 10010001110011101101101011010011100101101010111001 1 25 560163135 2 7 696374536 33 39 14485266 39 22 456690113 4 5 267811886 18 6 657680382 3 43 865617406 25 14 885515220 41 34 919525052 42 50 410634144 8 3 487403277 3 30 701549676 2 43 54223104 7 34 691078766 14 23 323352590 26 48 4936558...
output:
17177676326 31373486130 15290175638 8192974494 22734716092 27802380120 6315957348 0 15780401446 15929384564 26423899248 9639532596 21199366790 26413065782 -1 29063665908 29925313598 28651879288 17144176262 16526083688 28206620550 26873163342 14840246174 32414950818 29985336496 0 11937422088 11131990...
result:
ok 100000 numbers
Test #4:
score: 0
Accepted
time: 64ms
memory: 81024kb
input:
50 200000 01011001001010000100001101100111011001101011101000 34 29 654100339 33 5 947063765 45 25 962067151 11 13 509130797 26 47 988757358 49 22 75267557 7 11 431530851 46 1 531969122 22 43 449891945 34 6 526679193 50 17 499004364 22 23 226725950 26 48 203414490 11 44 900725507 10 29 451714017 35 2...
output:
24080362406 0 0 21418182584 28358635244 28257750030 24520294678 21418182584 0 15335211126 28621468542 18664505530 19335499776 32374868794 23618866752 26801803500 24116134918 27676993638 30222353942 25612316674 20504702130 28400398734 29472795250 24400110084 20586186786 25612316674 0 30067400886 1297...
result:
ok 100000 numbers
Test #5:
score: 0
Accepted
time: 0ms
memory: 31892kb
input:
2 10 01 1 2 340134039 2 1 2 1 1 2 1 2 1 2 2 1 1 1 2 2 2 2 1 2 2 2 2 1 1
output:
0 680268078 0 0 -1
result:
ok 5 number(s): "0 680268078 0 0 -1"
Test #6:
score: 0
Accepted
time: 161ms
memory: 92628kb
input:
200000 100 1100001001001101010000111111011011101010001011011011011010101111010001111010101100101001010000110100100011111010011100101010010001011010111100101110010000101010000100111100000011001100111101110011000011010011011011100101100111101010111101110111001111111010001010010000110110100000111000111...
output:
187263442365796 187267199881816 187176203274470 187269896250018 187239740690858 186974761323092 187257776119514 187269896250018 187035239640930 186911636122472 187263030332128 187121605387264 187264313877130 187263442365796 187269896250018 187249588971104 187263442365796 187263442365796 187264313877...
result:
ok 50 numbers
Test #7:
score: 0
Accepted
time: 146ms
memory: 76556kb
input:
200000 100 1000100001000101011000010111101000110001110111010000000010100100001110001110011001001011000010001000101111000111000100111101111111011111101101011110010101110000011011000101010000101110000100101000101110011111110000010011010010001001010001101000001111001001011111110100100011011100010100101...
output:
187406582272754 187713357625510 187713357625510 187710409039730 187708440524170 187705546874918 187675370061160 187696435101958 187704004975728 187708440524170 187708440524170 187490194913408 186797006090958 187708440524170 187708440524170 187694259450196 187691068337432 187699562335668 187708440524...
result:
ok 50 numbers
Test #8:
score: 0
Accepted
time: 152ms
memory: 200596kb
input:
200000 100 1101110101111010101100101110111101001010101100011111011010101101001011000101011011110110110001000000110000100110101010001011100110100101010110001111000100011010101011100011111010111001011110110001001010000001010100000000100010010000110100101010000111010100100111001011101001000011010101011...
output:
187071935465024 186902015424650 186944515923806 187083386398370 187083386398370 186176053533638 187210565613960 186840136921858 187059112646348 186963648681914 187157614978100 187171857507720 186687953621656 187037985042418 184267618052908 185811051686090 186716949587794 186666528269428 186754258305...
result:
ok 50 numbers
Test #9:
score: 0
Accepted
time: 1634ms
memory: 202072kb
input:
200000 200000 1010011001010010101000001000111111110110111100000011000110010101000001101110111000100011010101100011001011101100010100000010100000100110100001000111010000011001010111001001000000111001100110010100101010111000000000011110101110010101110110110101100001011001101010101001000010000010000000...
output:
185874943612396 186901189463748 185325592077116 187007806200644 185723936146376 186683200699722 186830061692652 186256265895174 186860903405924 186810412385682 186744028102060 186994420108608 186831837842360 180459525430870 186966649455016 186952309712742 185810351127924 186849618327982 186494273101...
result:
ok 100000 numbers
Test #10:
score: 0
Accepted
time: 1606ms
memory: 202348kb
input:
200000 200000 1101100101010001011001101010110111010000001100111000100010001111101101110111001101000001101011010000001110101101001010011000001011000101010111001101100100101001100111010001101010011100101100010110000011110101101011000011101101010111101000000111100100011101000110011100011000010010001011...
output:
187559700459682 187535810670694 187366757549978 187509694959444 186405180245408 187572993046976 186802217032708 186278525122374 187171989295434 187404069323808 187366390326582 184670301024044 186230793287498 187530780070456 187597311483370 187406310330638 187384636670170 187047338416520 187544270920...
result:
ok 100000 numbers
Test #11:
score: 0
Accepted
time: 1583ms
memory: 201080kb
input:
200000 200000 0011111000111101101011111111000010101011010000100000110110010110010000011010101011101001100001001001000001100110010100101101001111000111010011110100000100000001111111000001000101000011110001101101111000101001100010010011001101100111110000110001100001100011110011001100100010000010001101...
output:
187057082821034 187050489592834 185798962075874 186490497612254 185547643085476 185839649755426 186731725449660 186845143722558 186446910671932 186830913714546 186903848544526 186827856700414 187012840145598 187030896936824 186738571374322 186338959389628 186977751482606 187075649881228 186978915850...
result:
ok 100000 numbers
Test #12:
score: -100
Runtime Error
input:
1 3 0 2 1 1 1 1 2 1 1