| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 836503 |
2023-08-24T12:01:19 Z |
elkernos |
Prize (CEOI22_prize) |
C++17 |
|
1600 ms |
388544 KB |
// clang-format off
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
using namespace std;
// using namespace __gnu_pbds;
// template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef XOX
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) { ris << "(" << d.first << ", " << d.second << ")"; }
sim dor(rge<c> d) { *this << "["; for (auto it = d.b; it != d.e; ++it) *this << ", " + 2 * (it == d.b) << *it; ris << "]"; }
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
struct { template <class T> operator T() { T x; cin >> x; return x; } } in;
#define endl '\n'
#define pb emplace_back
#define vt vector
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using i64 = long long;
// #define int long long
// clang-format on
const int nax = 1e6 + 7;
struct Tree {
vector<int> g[nax];
vector<pair<int, int>> gp[nax];
int par[20][nax], dep[nax], real_dep[nax];
int tin[nax], tout[nax];
int timer;
int root;
void init(vector<int> p) {
int n = (int)p.size();
for(int i = 1; i < n; i++) {
if(p[i] == -1) {
root = i;
par[0][i] = i;
}
else {
par[0][i] = p[i];
g[p[i]].push_back(i);
}
}
for(int i = 1; i < 20; i++)
for(int j = 1; j < n; j++)
par[i][j] = par[i - 1][ par[i - 1][j] ];
dfs(root);
}
void dfs(int u) {
tin[u] = ++timer;
for(int to : g[u]) {
dep[to] = dep[u] + 1;
dfs(to);
}
tout[u] = timer;
}
int lca(int u, int v) {
if(dep[u] > dep[v]) swap(u, v);
int delta = dep[v] - dep[u];
for(int i = 0; delta; i++) {
if(delta % 2) v = par[i][v];
delta /= 2;
}
if(u == v) return u;
for(int i = 19; i >= 0; i--) {
if(par[i][u] != par[i][v]) {
u = par[i][u];
v = par[i][v];
}
}
return par[0][u];
}
int dist(int a, int b) {
debug() << imie(real_dep[a]) imie(real_dep[b]);
return real_dep[a] + real_dep[b] - 2 * real_dep[lca(a, b)];
}
void wsadz(int a, int b, int da, int db) {
int l = lca(a, b);
if(a != l) gp[l].emplace_back(a, da), gp[a].emplace_back(l, -da);
if(b != l) gp[l].emplace_back(b, db), gp[b].emplace_back(l, -db);
}
bool vis[nax];
void licz() {
pair<int, int> p = {1e9, -1};
for(int i = 1; i < nax; i++) if(gp[i].size())
p = min(p, {dep[i], i});
queue<int> q;
q.push(p.second);
debug() << imie(p);
while(q.size()) {
int u = q.front();
q.pop();
debug() << imie(u) imie(gp[u]);
for(auto [to, wei] : gp[u]) {
real_dep[to] = real_dep[u] + wei;
if(!vis[to]) vis[to] = 1, q.push(to);
}
}
}
};
Tree tree[2];
int32_t main()
{
cin.tie(0)->sync_with_stdio(0);
int n = in, k = in, t = in, q = in;
vector<vector<int>> par(2, vector<int>(n + 1));
for(int r : {0, 1})
for(int i = 1; i <= n; i++) par[r][i] = in;
for(int i : {0, 1}) tree[i].init(par[i]);
vector<int> chosen;
queue<int> que;
que.push(tree[0].root);
while((int)chosen.size() != k) {
int u = que.front();
que.pop();
chosen.push_back(u);
for(int to : tree[0].g[u]) que.push(to);
}
for(int i : chosen) cout << i << " ";
cout << endl;
sort(chosen.begin(), chosen.end(), [&](int a, int b) {
return tree[1].tin[a] < tree[1].tin[b];
});
for(int i = 0; i + 1 < (int)chosen.size(); i++)
cout << "? " << chosen[i] << " " << chosen[i + 1] << endl;
cout << "!" << endl;
cout.flush();
for(int i = 0; i + 1 < (int)chosen.size(); i++) {
int a = in, b = in, c = in, d = in;
tree[0].wsadz(chosen[i], chosen[i + 1], a, b);
tree[1].wsadz(chosen[i], chosen[i + 1], c, d);
}
for(int i : {0, 1}) tree[i].licz();
for(int i = 0; i < q; i++) {
int a = in, b = in;
cout << tree[0].dist(a, b) << " " << tree[1].dist(a, b) << endl;
}
}
Compilation message
Main.cpp: In function 'int32_t main()':
Main.cpp:122:25: warning: unused variable 't' [-Wunused-variable]
122 | int n = in, k = in, t = in, q = in;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
687 ms |
242940 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
861 ms |
244808 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
536 ms |
237924 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1255 ms |
383428 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1600 ms |
388544 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
