| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 838977 |
2023-08-28T12:09:29 Z |
sysia |
Prize (CEOI22_prize) |
C++17 |
|
0 ms |
0 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;
struct graph{
vector<vector<T>>g;
vector<vector<int>>up;
vector<int>depth, deg, par, pre, post, dist;
int n, root, tt = 0;
void init(int _n, vector<int>p){
n = _n;
g.resize(n+1);
deg.resize(n+1);
pre.resize(n+1);
post.resize(n+1);
par.assign(n+1, -1);
dist.resize(n+1);
depth.assign(n+1, 0);
par = p;
for (int i = 1; i<=n; i++){
// cin >> par[i];
if (par[i] == -1) root = i;
else g[par[i]].emplace_back(i, 0);
}
up.assign(n+1, vector<int>(K, root));
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; //jump pointery sie liczy w kolejnosci preorder hshshs
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;
depth[x] = depth[v]+1;
dfs(x, v);
}
post[v] = ++tt;
}
int lca(int a, int b){
if (depth[a] < depth[b]) swap(a, b);
for (int i = K-1; i>=0; i--){
if (depth[a] - (1<<i) >= depth[b]){
a = up[a][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 clear(){
for (int i = 1; i<=n; i++) g[i].clear();
}
void bfs(){
queue<int>q;
int v = -1;
for (int i = 1; i<=n; i++){
if (v == -1 || ((int)g[i].size() && depth[i] < depth[v])){
v = i;
}
}
debug(v);
q.push(v);
vector<bool>vis(n+1);
vis[v] = 1;
while ((int)q.size()){
int u = q.front(); q.pop();
for (auto [x, c]: g[u]){
if (!vis[x]){
dist[x] = dist[u]+c;
vis[x] = 1;
q.push(x);
}
}
}
debug(depth);
}
int get_dist(int a, int b){
debug(a, b, lca(a, b));
return dist[a] + dist[b] - 2 * dist[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;
array<graph, 2>g;
g[0].init(n), g[1].init(n);
vector<int>curr(n);
iota(curr.begin(), curr.end(), 1);
sort(curr.begin(), curr.end(), [&](auto x, auto y){
return g[0].pre[x] < g[0].pre[y];
})
while ((int)curr.size() > k) curr.pop_back();
for (auto u: curr) cout << u << " ";
cout << "\n"; cout.flush();
g[0].clear(); g[1].clear();
vector<T>edges;
for (int i = 1; i<(int)curr.size(); i++){
cout << "? " << curr[i-1] << " " << curr[i] << "\n";
edges.emplace_back(curr[i-1], curr[i]);
}
cout << "!\n"; cout.flush();
for (auto [a, b]: edges){
//b w poddrzewie a
for (int rep = 0; rep < 2; rep++){
int a1, b1; cin >> a1 >> b1;
int lca = g[rep].lca(a, b);
debug(a, b, lca, rep);
g[rep].add(a, lca, a1);
g[rep].add(b, lca, b1);
}
}
g[0].bfs(); g[1].bfs();
vector<T>que;
while (t--){
int a, b; cin >> a >> b;
que.emplace_back(a, b);
}
for (auto [a, b]: que){
cout << g[0].get_dist(a, b) << " " << g[1].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:134:13: error: no matching function for call to 'graph::init(int&)'
134 | g[0].init(n), g[1].init(n);
| ^
Main.cpp:38:7: note: candidate: 'void graph::init(int, std::vector<int>)'
38 | void init(int _n, vector<int>p){
| ^~~~
Main.cpp:38:7: note: candidate expects 2 arguments, 1 provided
Main.cpp:134:27: error: no matching function for call to 'graph::init(int&)'
134 | g[0].init(n), g[1].init(n);
| ^
Main.cpp:38:7: note: candidate: 'void graph::init(int, std::vector<int>)'
38 | void init(int _n, vector<int>p){
| ^~~~
Main.cpp:38:7: note: candidate expects 2 arguments, 1 provided
Main.cpp:139:4: error: expected ';' before 'while'
139 | })
| ^
| ;
140 | while ((int)curr.size() > k) curr.pop_back();
| ~~~~~
