| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 838806 |
2023-08-27T18:55:19 Z |
sysia |
Prize (CEOI22_prize) |
C++17 |
|
3500 ms |
438840 KB |
//Sylwia Sapkowska
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;
void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << "'" << x << "'";}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
void ckmin(int &a, int b) {a = min(a, b);}
typedef pair<int, int> T;
const int oo2 = 1e9+7;
const int K = 20;
vector<bool>active;
struct graph{
vector<vector<T>>g;
vector<vector<int>>up;
vector<int>depth, deg, par, pre, post;
int n, root, tt = 0;
vector<T>edges;
graph(int nn){
n = nn;
g.resize(n+1);
deg.resize(n+1);
pre.resize(n+1);
post.resize(n+1);
par.assign(n+1, -1);
depth.assign(n+1, 0);
up.resize(n+1, vector<int>(K));
for (int i = 1; i<=n; i++){
int p; cin >> p;
if (p == -1) root = i;
else {
par[i] = p;
g[p].emplace_back(i, 0);
}
}
for (int i = 1; i<=n; i++) deg[i] = (int)g[i].size();
dfs(root, root);
}
void dfs(int v, int pa){
pre[v] = ++tt;
up[v][0] = pa;
for (int i = 1; i<K; i++) up[v][i] = up[up[v][i-1]][i-1];
for (auto [x, __]: g[v]){
if (x == pa) continue;
dfs(x, v);
}
post[v] = ++tt;
}
int lca(int a, int b){
if (!subtree(a, b)) swap(a, b);
for (int i = K-1; i>=0; i--){
if (subtree(a, up[b][i])){
b = up[b][i];
}
}
if (a == b) return a;
for (int i = K-1; i>=0; i--){
if (up[a][i] != up[b][i]){
a = up[a][i];
b = up[b][i];
}
}
return up[a][0];
}
void remove(int v){
int p = par[v];
if (p == -1) return;
if ((int)deg[v] == 0){ //lisc
deg[p]--;
} else { //z pionowej sciezki ---> jest tylko jedno dziecko,podlaczyc do rodzica v
while (!active[g[v].back().first]) g[v].pop_back();
assert(!g[v].empty());
auto x = g[v].back().first;
g[p].emplace_back(x, 0);
par[x] = p;
}
}
bool subtree(int a, int b){ //czy b w poddrzewie a
return (pre[a] <= pre[b] && post[a] >= post[b]);
}
void make_vt(vector<int>curr){
stable_sort(curr.begin(), curr.end(), [&](auto x, auto y){
return pre[x] < pre[y];
});
for (int i = 1; i<=n; i++) g[i].clear();
vector<int>s = {curr[0]};
for (int i = 1; i<(int)curr.size(); i++){
while (!subtree(s.back(), curr[i])){
//czyli curr[i] poza poddrzewem
s.pop_back();
}
assert(!s.empty());
edges.emplace_back(curr[i], s.back());
s.emplace_back(curr[i]);
}
debug(edges);
root = curr[0];
}
void bfs(){
queue<int>q;
q.push(root);
vector<bool>vis(n+1);
vis[root] = 1;
while ((int)q.size()){
int v = q.front(); q.pop();
for (auto [x, c]: g[v]){
if (!vis[x]){
depth[x] = depth[v]+c;
vis[x] = 1;
q.push(x);
}
}
}
for (int i = 1; i<=n; i++){
if (active[i]){
debug(i, depth[i]);
}
}
}
int get_dist(int a, int b){
return depth[a] + depth[b] - 2 * depth[lca(a, b)];
}
void add(int a, int l, int c){
if (c) {
g[a].emplace_back(l, -c);
g[l].emplace_back(a, c);
}
}
};
void solve(){
int n, k, q, t; cin >> n >> k >> q >> t;
graph g1(n), g2(n);
active.assign(n+1, 1);
stack<int>s;
auto cute = [&](int v){
return g1.deg[v] <= 1 && g2.deg[v] <= 1 && active[v];
};
for (int i = 1; i<=n; i++) if (cute(i)) s.push(i);
for (int rep = 0; rep<n-k; rep++){
while ((int)s.size() && !active[s.top()]) s.pop();
assert(!s.empty());
int v = s.top(); s.pop();
debug(v);
active[v] = 0;
g1.remove(v);
g2.remove(v);
for (auto ck: {g1.par[v], g2.par[v]}){
if (ck != -1 && cute(ck)) {
s.push(ck);
}
}
}
vector<int>curr;
for (int i = 1; i<=n; i++) if (active[i]) curr.emplace_back(i);
for (auto u: curr) cout << u << " ";
cout << "\n"; cout.flush();
g1.make_vt(curr);
g2.make_vt(curr);
for (auto [a, b]: g1.edges){
cout << "? " << a << " " << b << "\n";
}
cout << "!\n"; cout.flush();
for (auto [a, b]: g1.edges){
int a1, b1, a2, b2; cin >> a1 >> b1 >> a2 >> b2;
//b w poddrzewie a
assert(b1 == 0);
g1.add(a, b, a1); //a, lca, w
int lca = g2.lca(a, b);
debug(a, lca, a2);
debug(b, lca, b2);
g2.add(a, lca, a2);
g2.add(b, lca, b2);
}
g1.bfs();
g2.bfs();
vector<T>que;
while (t--){
int a, b; cin >> a >> b;
que.emplace_back(a, b);
}
for (auto [a, b]: que){
int l = g1.lca(a, b);
cout << g1.get_dist(a, b) << " " << g2.get_dist(a, b) << "\n";
}
cout.flush();
}
int32_t main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
Compilation message
Main.cpp: In function 'void solve()':
Main.cpp:213:7: warning: unused variable 'l' [-Wunused-variable]
213 | int l = g1.lca(a, b);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2093 ms |
214196 KB |
Output is correct |
| 2 |
Correct |
2130 ms |
214652 KB |
Output is correct |
| 3 |
Runtime error |
812 ms |
189160 KB |
Execution killed with signal 13 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2348 ms |
220392 KB |
Output is correct |
| 2 |
Correct |
2340 ms |
219928 KB |
Output is correct |
| 3 |
Runtime error |
899 ms |
190200 KB |
Execution killed with signal 13 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1626 ms |
219404 KB |
Output is correct |
| 2 |
Correct |
1607 ms |
219528 KB |
Output is correct |
| 3 |
Runtime error |
695 ms |
186372 KB |
Execution killed with signal 13 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3569 ms |
438560 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3556 ms |
438840 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
