This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#define fio ios_base::sync_with_stdio(0);cin.tie(0);
#define ll long long
#define en cin.close();return 0;
#define pb push_back
#define fi first//printf("%lli\n",cur);
#define se second//scanf("%lli",&n);
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 1e6+5;
const int LOG = log2(N)+2;
vector<int> g[N];
bool good[N];
int par[N][LOG], dis[N];
int tin[N], tout[N], tt;
int k;
vector<int> ve;
vector<pair<int,int> > qu;
void dfs(int u)
{
good[u]=1;
ve.pb(u);
k--;
tin[u]=++tt;
for(int i = 1;i<LOG;i++)
par[u][i]=par[par[u][i-1]][i-1];
for(auto v:g[u])
{
if(k>0)
{
qu.pb({u,v});
par[v][0]=u;
dfs(v);
}
}
tout[u]=tt;
}
void dfs2(int u)
{
for(auto v:g[u])
if(good[v])
dis[v]+=dis[u],
dfs2(v);
}
bool isanc(int u, int v)
{
return (tin[u]<=tin[v]&&tout[v]<=tout[u]);
}
int getlca(int u, int v)
{
if(isanc(u,v))
return u;
if(isanc(v,u))
return v;
for(int i = LOG-1;i>=0;i--)
if(!isanc(par[u][i],v))
u=par[u][i];
return par[u][0];
}
int getdist(int u, int v)
{
int lca = getlca(u,v);
return dis[u]+dis[v]-2*dis[lca];
}
int main()
{
fio
// ifstream cin("in.in");
int n, q, t;
cin >> n >> k >> q >> t;
int r;
for(int i = 1;i<=n;i++)
{
int p;
cin >> p;
if(p==-1)
r=i;
else
g[p].pb(i);
}
for(int i = 1,p;i<=n;i++)
cin >> p;
par[r][0]=r;
dfs(r);
for(auto x:ve)
cout << x << " ";
cout << "\n";
for(auto x:qu)
cout << "? " << x.fi << " " << x.se << "\n";
cout << "!" << endl;
for(auto x:qu)
{
int x1, x2, x3, x4;
cin >> x1 >> x2 >> x3 >> x4;
dis[x.se]=x1+x2;
}
dfs2(r);
for(int i = 0;i<t;i++)
{
int u, v;
cin >> u >> v;
int dist = getdist(u,v);
cout << dist << " " << dist << "\n";
}
// cin.close();
return 0;
}
Compilation message (stderr)
Main.cpp: In function 'int main()':
Main.cpp:99:9: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
99 | dfs2(r);
| ~~~~^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |