| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 805482 |
2023-08-03T17:01:39 Z |
rnl42 |
Prize (CEOI22_prize) |
C++14 |
|
1741 ms |
301960 KB |
#include <bits/stdc++.h>
using namespace std;
string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
bool first = true;
string res = "[";
for (const auto &x : v) {
if (!first)
res += ", ";
first = false;
res += to_string(x);
}
res += "]";
return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
cout << ' ' << to_string(H);
dbg_out(T...);
}
#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
struct Tree {
int root = 0;
vector<int> parent;
vector<vector<int>> adj;
void resize(size_t N) {
parent.resize(N);
adj.resize(N);
}
};
struct LCA {
vector<int> first;
vector<int> tourtree;
vector<int> height;
int tree_shift = 0;
void init(Tree& t) {
tree_shift = (1<<__lg(4*(int)t.parent.size()-1+10))+3;
first.resize(tree_shift);
height.resize(tree_shift);
tourtree.assign(2*tree_shift, tree_shift-1);
height[tree_shift-1] = 1e9;
int tour_i = 0;
function<void(int)> dfs = [&](const int u) {
first[u] = tour_i;
//dbg(u, tour_i);
tourtree[tree_shift+tour_i++] = u;
for (int v : t.adj[u]) {
height[v] = height[u]+1;
dfs(v);
tourtree[tree_shift+tour_i++] = u;
}
};
dfs(t.root);
for (int i = tree_shift-1; i > 0; i--) {
tourtree[i] = min(make_pair(height[tourtree[2*i]], tourtree[2*i]), make_pair(height[tourtree[2*i+1]], tourtree[2*i+1])).second;
}
}
int lca(int l, int r) {
if (first[l] > first[r]) swap(l, r);
/*cerr << "\n-----------\n";
for (int i = 0; i < tree_shift; i++) {
cerr << tourtree[tree_shift+i] << " ";
}
cerr << "\n\n-----------\n" << endl;
dbg(tree_shift);*/
l = first[l]+tree_shift, r = first[r]+tree_shift+1;
//cerr << "lr " << l << " " << r << endl;
pair<int,int> ret(1e9, 1e9);
for (; l < r; l >>= 1, r >>= 1) {
if (l&1) {
ret = min(ret, make_pair(height[tourtree[l]], tourtree[l]));
//dbg(tourtree[l], height[tourtree[l]]);
l++;
}
if (r&1) {
--r;
ret = min(ret, make_pair(height[tourtree[r]], tourtree[r]));
}
}
return ret.second;
}
};
istream& operator>>(istream& in, Tree& tree) {
for (size_t i = 0; i < tree.parent.size(); i++) {
in >> tree.parent[i], tree.parent[i]--;
if (tree.parent[i] == -2) {
tree.parent[i] = -1;
tree.root = i;
} else {
tree.adj[tree.parent[i]].push_back(i);
}
}
return in;
}
int N, K, Q, T;
Tree trees[2];
vector<int> chosen_set;
LCA lca[2];
namespace com {
void choose_set(vector<int>& v) {
for (int i = 0; i < K; i++) {
cout << v[i]+1 << (i == K-1 ? '\n' : ' ');
}
cout << flush;
}
void query(int u, int v) {
cout << "? " << u+1 << " " << v+1 << '\n';
Q++;
}
pair<vector<array<int,4>>,vector<pair<int,int>>> read_response() {
cout << "!\n" << flush;
vector<array<int,4>> resp(Q);
vector<pair<int,int>> queries(T);
for (int i = 0; i < Q; i++)
for (int j = 0; j < 4; j++)
cin >> resp[i][j];
for (int i = 0; i < T; i++)
cin >> queries[i].first >> queries[i].second, queries[i].first--, queries[i].second--;
return make_pair(resp, queries);
}
void answer(int d1, int d2) {
cout << d1 << " " << d2 << '\n';
}
}
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> N >> K >> Q >> T;
Q = 0;
for (int i = 0; i < 2; i++) {
trees[i].resize(N);
cin >> trees[i];
}
function<void(int)> dfs = [&](const int u) {
if ((int)chosen_set.size() < K) chosen_set.push_back(u);
for (int v : trees[0].adj[u]) dfs(v);
};
dfs(trees[0].root);
sort(chosen_set.begin(), chosen_set.end());
com::choose_set(chosen_set);
lca[1].init(trees[1]);
lca[0].init(trees[0]);
sort(chosen_set.begin(), chosen_set.end(), [](const int a, const int b) {
return lca[1].first[a] < lca[1].first[b];
});
vector<int> elems;
vector<int> poselem(N, -1);
vector<int> cumulsum = {0};
for (int i = 0; i < K-1; i++) {
elems.push_back(chosen_set[i]);
poselem[elems.back()] = elems.size()-1;
//dbg(i, elems.back());
//dbg(chosen_set[i], chosen_set[i+1], lca[1].lca(chosen_set[i], chosen_set[i+1]));
elems.push_back(lca[1].lca(chosen_set[i], chosen_set[i+1]));
poselem[elems.back()] = elems.size()-1;
//dbg(i, elems.back());
com::query(chosen_set[i], chosen_set[i+1]);
}
elems.push_back(chosen_set.back());
poselem[elems.back()] = elems.size()-1;
/*cout << "\n\n\n";
dbg(chosen_set);
dbg(elems);
cout << "\n\n\n";*/
//vector<pair<int,int>> infotree0(N);
//for (int i = 0; i < N; i++) infotree0[i] = make_pair(i, 0);
//vector<int> sumuntilroot(N);
//vector<int> w_edge(N);
auto [resp, queries] = com::read_response();
vector<vector<pair<int,int>>> newadj(N);
vector<int> sumuntilroot(N, -1);
for (int i = 0; i < Q; i++) {
cumulsum.push_back(cumulsum.back()+resp[i][2]);
cumulsum.push_back(cumulsum.back()-resp[i][3]);
int a = lca[0].lca(elems[2*i], elems[2*i+2]);
//cerr << "pair " << a << " " << elems[2*i] << " " << resp[i][0] << endl;
newadj[a].emplace_back(elems[2*i], resp[i][0]);
newadj[elems[2*i]].emplace_back(a, -resp[i][0]);
newadj[a].emplace_back(elems[2*i+2], resp[i][1]);
newadj[elems[2*i+2]].emplace_back(a, -resp[i][1]);
}
// à vérifier
function<void(int)> dfs2 = [&](const int u) {
for (auto [v, sumw] : newadj[u]) {
if (sumuntilroot[v] == -1) {
sumuntilroot[v] = sumuntilroot[u]+sumw;
dfs2(v);
}
}
};
sumuntilroot[trees[0].root] = 0;
dfs2(trees[0].root);
/*for (int u = 0; u < N; u++) {
if (newadj[u].size()) cerr << "sumuntil " << u << " = " << newadj[u][0].first << ":" << newadj[u][0].second << endl;
}*/
for (int i = 0; i < T; i++) {
auto& q = queries[i];
int d1 = -2*sumuntilroot[lca[0].lca(q.first, q.second)]+sumuntilroot[q.first]+sumuntilroot[q.second];
//dbg(q.first, q.second);
//dbg(poselem[q.first], poselem[q.second]);
int d2 = 2*cumulsum[poselem[lca[1].lca(q.first, q.second)]]-cumulsum[poselem[q.first]]-cumulsum[poselem[q.second]];
com::answer(d1, d2);
}
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:190:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
190 | auto [resp, queries] = com::read_response();
| ^
Main.cpp: In lambda function:
Main.cpp:206:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
206 | for (auto [v, sumw] : newadj[u]) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
917 ms |
152860 KB |
Output is correct |
| 2 |
Correct |
953 ms |
155032 KB |
Output is correct |
| 3 |
Correct |
710 ms |
99604 KB |
Output is correct |
| 4 |
Correct |
546 ms |
98824 KB |
Output is correct |
| 5 |
Correct |
658 ms |
100872 KB |
Output is correct |
| 6 |
Correct |
711 ms |
111292 KB |
Output is correct |
| 7 |
Correct |
762 ms |
111236 KB |
Output is correct |
| 8 |
Correct |
698 ms |
111032 KB |
Output is correct |
| 9 |
Correct |
562 ms |
99552 KB |
Output is correct |
| 10 |
Correct |
697 ms |
100416 KB |
Output is correct |
| 11 |
Correct |
597 ms |
97992 KB |
Output is correct |
| 12 |
Correct |
651 ms |
100048 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
887 ms |
155300 KB |
Output is correct |
| 2 |
Correct |
770 ms |
151984 KB |
Output is correct |
| 3 |
Correct |
674 ms |
99420 KB |
Output is correct |
| 4 |
Correct |
654 ms |
101308 KB |
Output is correct |
| 5 |
Correct |
599 ms |
100220 KB |
Output is correct |
| 6 |
Correct |
779 ms |
109424 KB |
Output is correct |
| 7 |
Correct |
808 ms |
111828 KB |
Output is correct |
| 8 |
Correct |
815 ms |
112124 KB |
Output is correct |
| 9 |
Correct |
722 ms |
110292 KB |
Output is correct |
| 10 |
Correct |
762 ms |
110912 KB |
Output is correct |
| 11 |
Correct |
679 ms |
107844 KB |
Output is correct |
| 12 |
Correct |
687 ms |
110660 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
653 ms |
147136 KB |
Output is correct |
| 2 |
Correct |
673 ms |
147152 KB |
Output is correct |
| 3 |
Correct |
446 ms |
92940 KB |
Output is correct |
| 4 |
Correct |
504 ms |
92844 KB |
Output is correct |
| 5 |
Correct |
407 ms |
92840 KB |
Output is correct |
| 6 |
Correct |
515 ms |
104152 KB |
Output is correct |
| 7 |
Correct |
501 ms |
104292 KB |
Output is correct |
| 8 |
Correct |
579 ms |
104160 KB |
Output is correct |
| 9 |
Correct |
459 ms |
102040 KB |
Output is correct |
| 10 |
Correct |
470 ms |
102004 KB |
Output is correct |
| 11 |
Correct |
425 ms |
102084 KB |
Output is correct |
| 12 |
Correct |
538 ms |
102060 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1670 ms |
293952 KB |
Output is correct |
| 2 |
Correct |
1518 ms |
293960 KB |
Output is correct |
| 3 |
Correct |
1120 ms |
185472 KB |
Output is correct |
| 4 |
Correct |
1214 ms |
185576 KB |
Output is correct |
| 5 |
Correct |
1090 ms |
185612 KB |
Output is correct |
| 6 |
Correct |
1365 ms |
208116 KB |
Output is correct |
| 7 |
Correct |
1351 ms |
208164 KB |
Output is correct |
| 8 |
Correct |
1350 ms |
208396 KB |
Output is correct |
| 9 |
Correct |
1218 ms |
204028 KB |
Output is correct |
| 10 |
Correct |
1171 ms |
203900 KB |
Output is correct |
| 11 |
Correct |
1162 ms |
203924 KB |
Output is correct |
| 12 |
Correct |
1238 ms |
204132 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1737 ms |
301960 KB |
Output is correct |
| 2 |
Correct |
1741 ms |
301428 KB |
Output is correct |
| 3 |
Correct |
1498 ms |
190800 KB |
Output is correct |
| 4 |
Correct |
1589 ms |
193540 KB |
Output is correct |
| 5 |
Correct |
1314 ms |
190008 KB |
Output is correct |
| 6 |
Correct |
1646 ms |
216348 KB |
Output is correct |
| 7 |
Correct |
1728 ms |
213036 KB |
Output is correct |
| 8 |
Correct |
1638 ms |
215064 KB |
Output is correct |
| 9 |
Correct |
1316 ms |
210496 KB |
Output is correct |
| 10 |
Correct |
1298 ms |
210172 KB |
Output is correct |
| 11 |
Correct |
1397 ms |
210176 KB |
Output is correct |
| 12 |
Correct |
1349 ms |
211476 KB |
Output is correct |
