| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 727318 |
2023-04-20T11:53:51 Z |
amunduzbaev |
Prize (CEOI22_prize) |
C++17 |
|
3500 ms |
646452 KB |
#include "bits/stdc++.h"
using namespace std;
#define ar array
typedef long long ll;
#define int ll
const int N = 1e6 + 5;
vector<int> G[2][N];
int tin[2][N], tout[2][N], par[2][N][20];
vector<int> pos[N];
int P[N];
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int n, k, q, T; cin >> n >> k >> q >> T;
int R[2] {};
for(int i=1;i<=n;i++){
int p; cin >> p;
if(~p){
G[0][p].push_back(i);
} else {
R[0] = i;
}
}
for(int i=1;i<=n;i++){
int p; cin >> p;
if(~p){
G[1][p].push_back(i);
} else {
R[1] = i;
}
}
for(int c=0;c<2;c++){
int t = 0;
tout[c][0] = N;
function<void(int)> dfs = [&](int u){
tin[c][u] = ++t;
for(int j=1;j<20;j++){
par[c][u][j] = par[c][par[c][u][j-1]][j-1];
}
for(auto x : G[c][u]){
par[c][x][0] = u;
dfs(x);
}
tout[c][u] = t;
};
dfs(R[c]);
}
vector<int> p;
function<void(int)> dfs = [&](int u){
if(tin[0][u] <= k){
p.push_back(u);
}
for(auto x : G[0][u]){
dfs(x);
}
};
dfs(R[0]);
for(auto x : p){
cout<<x<<" ";
} cout<<endl;
auto is = [&](int t, int a, int b){
return (tin[t][a] <= tin[t][b] && tin[t][b] <= tout[t][a]);
};
auto Lca = [&](int t, int a, int b){
if(is(t, a, b)) return a;
if(is(t, b, a)) return b;
for(int j=19;~j;j--){
if(!is(t, par[t][a][j], b)) a = par[t][a][j];
}
return par[t][a][0];
};
sort(p.begin(), p.end(), [&](int a, int b){
return tin[1][a] < tin[1][b];
});
for(int i=0;i<k;i++){
P[p[i]] = i;
}
for(int i=1;i<k;i++){
cout<<"? "<<p[i-1]<<" "<<p[i]<<endl;
}
vector<ar<int, 2>> ed;
cout<<"! "<<endl;
vector<int> d(n + 1);
int add = 0;
for(int i=1;i<k;i++){
int dc, dd, da, db; cin >> dc >> dd >> da >> db;
pos[Lca(1, p[i-1], p[i])].push_back(i - 1);
ed.push_back({da, db});
d[p[i]] = d[p[i-1]] - dc + dd;
if(p[i] == R[0]) add = -d[p[i]];
}
for(auto x : p){
d[x] += add;
}
int sz = ed.size();
vector<int> pref(sz);
for(int i=0;i<sz;i++){
if(i){
pref[i] = pref[i-1];
}
pref[i] += (ed[i][0] - ed[i][1]);
}
vector<ar<int, 2>> Q;
for(int i=0;i<T;i++){
int a, b; cin >> a >> b;
Q.push_back({a, b});
}
auto get = [&](int l, int r){
if(l > r) return 0ll;
return pref[r] - (l ? pref[l-1] : 0);
};
for(int i=1;i<=n;i++){
for(auto j : pos[i]){
assert(Lca(1, p[j], p[j + 1]) == i);
}
}
for(auto [a, b] : Q){
if(tin[1][a] > tin[1][b]) swap(a, b);
int lca = Lca(1, a, b);
int l = P[a], r = P[b];
//~ assert(lower_bound(pos[lca].begin(), pos[lca].end(), l) != pos[lca].end());
int pp = *lower_bound(pos[lca].begin(), pos[lca].end(), l);
bool ok = 0;
for(auto j : pos[lca]){
if(j >= l){
ok = 1;
//~ assert(j == pp);
break;
}
}
assert(ok);
//~ assert(Lca(1, p[pp], p[pp + 1]) == lca);
//~ int res = get(l, j - 1) + ed[j][0] + ed[j][1] - get(j + 1, r - 1);
int is = 0, res = 0;
for(int j=l;j<r;j++){
int tmp = Lca(1, p[j], p[j + 1]);
if(tmp == lca && !is){
//~ assert(pp == j);
res += ed[j][0] + ed[j][1];
is = 1;
} else {
if(!is) res += (ed[j][0] - ed[j][1]);
else res -= (ed[j][0] - ed[j][1]);
}
}
lca = Lca(0, a, b);
cout<<d[a] + d[b] - d[lca] * 2<<" "<<res<<endl;
}
cout.flush();
}
/*
4 4 3 2
-1 1 2 3
-1 1 2 2
0 14 0 3
0 9 0 3
0 6 3 4
1 3
4 3
7 6 5 5
-1 1 1 3 2 4 4
-1 1 2 3 1 5 3
1 5
4 5
2 5
5 7
4 7
9 3 4 3
2 -1 2 1 1 5 1 4 5
9 4 5 5 7 3 -1 3 7
10 0 0 1
0 3 13 5
1 2
2 4
1 4
9 3 2 3
2 -1 2 1 1 5 1 4 5
2 -1 2 1 1 5 1 4 5
3 0 3 0
3 1 3 1
1 2
2 3
1 3
*/
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:139:7: warning: unused variable 'pp' [-Wunused-variable]
139 | int pp = *lower_bound(pos[lca].begin(), pos[lca].end(), l);
| ^~
Main.cpp:123:7: warning: variable 'get' set but not used [-Wunused-but-set-variable]
123 | auto get = [&](int l, int r){
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3534 ms |
327492 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3543 ms |
330000 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1498 ms |
646452 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3434 ms |
569260 KB |
Output is correct |
| 2 |
Execution timed out |
3547 ms |
569344 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3618 ms |
580440 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
