//Sylwia Sapkowska
#include <bits/stdc++.h>
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 K = 20;
struct graph{
vector<vector<int>>g;
vector<vector<T>> G;
vector<vector<int>>up, sum;
vector<set<int>>children;
vector<int>depth, deg, par, pre, c, D;
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);
D.resize(n+1);
G.resize(n+1);
children.resize(n+1);
par.assign(n+1, -1);
depth.assign(n+1, 0);
up.resize(K, vector<int>(n+1));
sum.resize(K, vector<int>(n+1));
for (int i = 1; i<=n; i++){
int p; cin >> p;
if (p == -1) root = i, up[0][i] = i;
else {
par[i] = p;
g[p].emplace_back(i);
children[p].insert(i);
up[0][i] = par[i];
}
}
for (int i = 1; i<=n; i++) deg[i] = (int)children[i].size();
for(int i=1;i<K;i++) for(int j=1;j<=n;j++) up[i][j]=up[i-1][up[i-1][j]];
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;
depth[x] = depth[v]+1;
dfs(x, v);
}
}
int lca(int a, int b, int f = 1){
if (depth[a] > depth[b]) swap(a, b);
int s = 0;
for (int i = K-1; i>=0; i--){
if (depth[up[i][b]] >= depth[a]){
s += sum[i][b];
b = up[i][b];
}
}
if (a == b) return (f == 1 ? a : s);
for (int i = K-1; i>=0; i--){
if (up[i][a] != up[i][b]){
s += sum[i][a] + sum[i][b];
a = up[i][a];
b = up[i][b];
}
}
s += sum[0][b] + sum[0][a];
return f == 1 ? up[0][a] : s;
}
bool cute(int v){
return deg[v] == 0 || ((int)children[v].size() == 1);
}
void remove(int v){
int p = par[v];
if (p == -1) return;
if ((int)deg[v] == 0){ //lisc
deg[p]--;
children[p].erase(v);
} else { //z pionowej sciezki ---> jest tylko jedno dziecko,podlaczyc do rodzica v
auto x = *children[v].begin();
children[p].erase(v);
children[p].insert(x);
par[x] = p;
}
}
void make_vt(vector<int>curr){
sort(curr.begin(), curr.end(), [&](auto x, auto y){
return pre[x] < pre[y];
});
for (int i = 1; i<(int)curr.size(); i++){
int a = curr[i];
int b = lca(curr[i], curr[i-1]);
debug(b, a);
G[b].emplace_back(a, (int)edges.size());
edges.emplace_back(a, b);
}
root = curr[0];
dfs2(root, root);
}
void dfs2(int v, int pa){
for (auto [x, i]: G[v]){
if (x == pa) continue;
D[x] = D[v] + 1;
dfs2(x, v);
}
}
void redo_up(){
for (int i = 1; i<K; i++){
for (int v = 1; v<=n; v++){
up[i][v] = up[i-1][up[i-1][v]];
sum[i][v] = sum[i-1][v] + sum[i-1][up[i-1][v]];
}
}
depth = D;
depth.assign(n+1, 0);
if (!c.empty()) dfs3(root, root);
}
void dfs3(int v, int pa){
for (auto [x, i]: G[v]){
if (x == pa) continue;
depth[x] = depth[v] + c[i];
dfs3(x, v);
}
}
};
void solve(){
int n, k, q, t; cin >> n >> k >> q >> t;
graph g1(n), g2(n);
vector<bool>active(n+1, 1);
stack<int>s;
for (int i = 1; i<=n; i++){
if (g1.cute(i) && g2.cute(i)){
s.push(i);
}
}
//wystarczy usuwac same liscie
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 && g1.cute(ck) && g2.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";
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;
// assert(b1 == 0);
g1.c.emplace_back(a1);
int lca = g2.lca(a, b);
for (int rep = 0; rep < 2; rep++){
g2.up[0][a] = lca;
g2.sum[0][a] = a2;
swap(a2, b2); swap(a, b);
}
}
g1.redo_up();
g2.redo_up();
// vector<T>que;
while (t--){
int a, b; cin >> a >> b;
int l = g1.lca(a, b);
cout << g1.depth[a] + g1.depth[b] - 2 * g1.depth[l] << " " << g2.lca(a, b, 0) << "\n";
// que.emplace_back(a, b);
}
// for (auto [a, b]: que){
// }
}
int32_t main(){
cin.tie(0)->sync_with_stdio(0);
solve();
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1728 ms |
372664 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1880 ms |
376444 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1195 ms |
368584 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
2829 ms |
736920 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
3576 ms |
744752 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
