| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 773881 |
2023-07-05T09:16:37 Z |
doowey |
Prize (CEOI22_prize) |
C++17 |
|
1884 ms |
362492 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N = (int)1e6 + 10;
const int LOG = 20;
int n, k;
struct outp{
int d1, d2, d3, d4;
};
vector<pii> qq;
vector<outp> rr;
vector<int> oo;
struct tree{
int idx;
vector<int> T[N];
int root = -1;
int tt;
int tin[N];
int tout[N];
int up[LOG][N];
void dfs(int u, int pa){
tt ++ ;
tin[u] = tt;
up[0][u] = pa;
for(int ln = 1; ln < LOG; ln ++ ){
up[ln][u]=up[ln-1][up[ln-1][u]];
}
if(oo.size() < k)
oo.push_back(u);
for(auto x : T[u]){
dfs(x, u);
}
tout[u] = tt;
}
void input(){
int p;
for(int i = 1; i <= n; i ++ ){
cin >> p;
if(p == -1) root = i;
else T[p].push_back(i);
}
dfs(root, root);
}
bool is_anc(int u, int v){
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int lca(int u, int v){
if(is_anc(u, v)) return u;
for(int ln = LOG - 1; ln >= 0 ; ln -- ){
if(!is_anc(up[ln][u], v)) u = up[ln][u];
}
return up[0][u];
}
vector<int> lis;
vector<int> comp;
void make_queries(vector<int> _s){
lis = _s;
sort(lis.begin(), lis.end(), [&](int x, int y){return tin[x] < tin[y];});
comp = lis;
for(int i = 0 ;i + 1 < lis.size(); i ++ ){
if(idx == 1)
qq.push_back(mp(lis[i], lis[i + 1]));
comp.push_back(lca(lis[i], lis[i + 1]));
}
sort(comp.begin(), comp.end(), [&](int x, int y){return tin[x] < tin[y];});
comp.resize(unique(comp.begin(), comp.end()) - comp.begin());
}
vector<pii> ss[N]; // dep_v = dep_u + x.se
int dep[N];
void add_edge(int u, int v, int w){
ss[u].push_back(mp(v, w));
ss[v].push_back(mp(u, -w));
}
void f(int u){
for(auto x : ss[u]){
if(dep[x.fi] == -1){
dep[x.fi]=dep[u]+x.se;
f(x.fi);
}
}
}
void compute(){
int big;
vector<int> stek;
for(auto x : comp){
while(!stek.empty() && is_anc(x, stek.back())) stek.pop_back();
stek.push_back(x);
}
big = stek[0];
int di, dj;
for(int i = 0 ; i < qq.size(); i ++ ){
int cur = lca(qq[i].fi, qq[i].se);
if(idx == 0){
di = rr[i].d1;
dj = rr[i].d2;
}
else{
di = rr[i].d3;
dj = rr[i].d4;
}
add_edge(cur, qq[i].fi, di);
add_edge(cur, qq[i].se, dj);
}
for(auto x : comp){
dep[x] = -1;
}
dep[big] = 0;
f(big);
}
int get_dist(int i, int j){
int cur = lca(i, j);
return dep[i] + dep[j] - 2 * dep[cur];
}
};
tree ai, bi;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int q, t;
cin >> n >> k >> q >> t;
ai.input();
bi.input();
ai.idx = 0;
bi.idx = 1;
ai.make_queries(oo);
bi.make_queries(oo);
for(auto x : oo) cout << x << " ";
cout << "\n";
fflush(stdout);
for(auto x : qq){
cout << "? " << x.fi << " " << x.se << "\n";
}
cout << "!\n";
fflush(stdout);
rr.resize(qq.size());
for(int i = 0 ; i < qq.size(); i ++ ){
cin >> rr[i].d1 >> rr[i].d2 >> rr[i].d3 >> rr[i].d4;
}
ai.compute();
bi.compute();
vector<pii> qwe;
int u, v;
for(int it = 1; it <= t; it ++ ){
cin >> u >> v;
qwe.push_back(mp(u, v));
}
for(auto x : qwe){
cout << ai.get_dist(x.fi, x.se) << " " << bi.get_dist(x.fi, x.se) << "\n";
}
fflush(stdout);
return 0;
}
Compilation message
Main.cpp: In member function 'void tree::dfs(int, int)':
Main.cpp:42:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
42 | if(oo.size() < k)
| ~~~~~~~~~~^~~
Main.cpp: In member function 'void tree::make_queries(std::vector<int>)':
Main.cpp:75:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for(int i = 0 ;i + 1 < lis.size(); i ++ ){
| ~~~~~~^~~~~~~~~~~~
Main.cpp: In member function 'void tree::compute()':
Main.cpp:106:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | for(int i = 0 ; i < qq.size(); i ++ ){
| ~~^~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:154:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
154 | for(int i = 0 ; i < qq.size(); i ++ ){
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
837 ms |
229904 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1048 ms |
231404 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
744 ms |
225908 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1866 ms |
356976 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1884 ms |
362492 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
