| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1054960 |
2024-08-12T13:22:10 Z |
hotboy2703 |
Prize (CEOI22_prize) |
C++17 |
|
699 ms |
286424 KB |
#include<bits/stdc++.h>
using ll = int;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
const ll MAXN = 5e5+100;
const ll MAXK = 19;
ll n,k,q,t;
struct tree{
vector <ll> g[MAXN];
ll depth[MAXN];
ll sp[MAXN][MAXK];
vector <pll> adj[MAXN];
ll dp[MAXN];
vector <ll> choose;
ll in[MAXN],timeDFS;
void dfs(ll u,ll p){
sp[u][0] = p;
in[u] = ++timeDFS;
for (ll j = 1;j < MAXK;j ++){
sp[u][j] = sp[sp[u][j-1]][j-1];
}
depth[u] = depth[p]+1;
choose.push_back(u);
for (auto v:g[u]){
if (v==p)continue;
dfs(v,u);
}
}
ll lca(ll u,ll v){
if (depth[u] > depth[v])swap(u,v);
for (ll j = MAXK-1;j >= 0;j --){
if (depth[sp[v][j]] >= depth[u])v = sp[v][j];
}
if (u==v)return u;
for (ll j = MAXK-1;j >= 0;j--){
if (sp[v][j] != sp[u][j])u = sp[u][j],v = sp[v][j];
}
return u;
}
ll root=-1;
void add(ll u,ll v,ll wu,ll wv){
ll LCA = lca(u,v);
if (root==-1||depth[LCA]<depth[root])root=LCA;
adj[LCA].push_back(MP(u,wu));
adj[u].push_back(MP(LCA,wu));
adj[LCA].push_back(MP(v,wv));
adj[v].push_back(MP(LCA,wv));
}
void solve(){
// for (ll i = 1;i <= n;i ++){
// if (dp[i] == 0){
queue <ll> q;
q.push(root);
while (!q.empty()){
ll u = q.front();
q.pop();
for (auto [v,w]:adj[u]){
if (v != u && dp[v] == 0){
dp[v] = dp[u] + (depth[u] > depth[v] ? -1 : + 1) * w;
q.push(v);
}
}
}
// }
// }
}
ll query(ll u,ll v){
ll LCA = lca(u,v);
return dp[u] + dp[v] - dp[LCA]*2;
}
} a1,a2;
int main(){
ios_base::sync_with_stdio(0);cin.tie(nullptr);
cin>>n>>k>>q>>t;
ll r1,r2;
for (ll i = 1;i <= n;i ++){
ll x;
cin>>x;
if (x!=-1){
a1.g[x].push_back(i);
a1.g[i].push_back(x);
}
else r1 = i;
}
// cout<<"OK"<<endl;
for (ll i = 1;i <= n;i ++){
ll x;
cin>>x;
if (x!=-1){
a2.g[x].push_back(i);
a2.g[i].push_back(x);
}
else r2 = i;
}
// cout<<"OK"<<endl;
a1.dfs(r1,r1);
a2.dfs(r2,r2);
// cout<<"WAT"<<endl;
// return 0;
vector <ll> c = a1.choose;
c.resize(k);
sort(c.begin(),c.end(),[](ll x,ll y){return a2.in[x] < a2.in[y];});
for (auto x:c)cout<<x<<' ';
cout<<'\n';
for (ll j = 0;j + 1 < sz(c);j ++)cout<<"? "<<c[j]<<' '<<c[j+1]<<'\n';
cout<<'!'<<endl;
for (ll j = 0;j + 1 < sz(c);j ++){
ll u1,v1,u2,v2;
cin>>u1>>v1>>u2>>v2;
a1.add(c[j],c[j+1],u1,v1);
a2.add(c[j],c[j+1],u2,v2);
}
// return 0;
a1.solve(),a2.solve();
// return 0;
while (t--){
ll x,y;
cin>>x>>y;
cout<<a1.query(x,y)<<' '<<a2.query(x,y)<<'\n';
}
cout.flush();
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:103:8: warning: 'r1' may be used uninitialized in this function [-Wmaybe-uninitialized]
103 | a1.dfs(r1,r1);
| ~~~~~~^~~~~~~
Main.cpp:104:8: warning: 'r2' may be used uninitialized in this function [-Wmaybe-uninitialized]
104 | a2.dfs(r2,r2);
| ~~~~~~^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
682 ms |
192480 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
699 ms |
195120 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
481 ms |
186536 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
541 ms |
286424 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
516 ms |
286408 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
