| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 720644 |
2023-04-08T18:14:20 Z |
n0sk1ll |
Valley (BOI19_valley) |
C++14 |
|
469 ms |
172680 KB |
#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)
using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;
//Note to self: Check for overflow
const int maxN=5000000;
int val[maxN],L[maxN],R[maxN];
int idx=0;
void add(int p, int l, int r, int s, int x)
{
val[p]+=x;
if (l==r) return;
int mid=(l+r)/2;
if (s<=mid)
{
if (!L[p]) L[p]=++idx;
add(L[p],l,mid,s,x);
}
else
{
if (!R[p]) R[p]=++idx;
add(R[p],mid+1,r,s,x);
}
}
int sled(int p, int q, int l, int r, int s)
{
if (val[p]-val[q]==0) return -1;
if (r<s) return -1;
if (l==r) return r;
int mid=(l+r)/2;
int maybe=sled(L[p],L[q],l,mid,s);
if (maybe==-1) return sled(R[p],R[q],mid+1,r,s);
return maybe;
}
int pret(int p, int q, int l, int r, int s)
{
if (val[p]-val[q]==0) return -1;
if (l>s) return -1;
if (l==r) return l;
int mid=(l+r)/2;
int maybe=pret(R[p],R[q],mid+1,r,s);
if (maybe==-1) return pret(L[p],L[q],l,mid,s);
return maybe;
}
void spoji(int a, int b, int l, int r, int n)
{
if (!val[a]) return;
if (l==r) add(b,1,n,l,val[a]);
else
{
int mid=(l+r)/2;
spoji(L[a],b,l,mid,n);
spoji(R[a],b,mid+1,r,n);
}
}
void ispisi(int p, int l, int r)
{
if (!val[p]) return;
if (l==r) cout<<"("<<l<<","<<val[p]<<")"<<endl;
else
{
int mid=(l+r)/2;
ispisi(L[p],l,mid);
ispisi(R[p],mid+1,r);
}
}
vector<pair<pii,int>> eds(100005);
vector<vector<pii>> g(100005);
int tin[100005],tout[100005],ord[100005],siz[100005];
li dub[100005]; int up[20][100005];
int VREME=0;
void dfs(int p, int q, int w)
{
dub[p]=dub[q]+w,up[0][p]=q,tin[p]=++VREME,ord[VREME]=p,siz[p]=1;
for (auto it : g[p]) if (it.xx!=q) dfs(it.xx,p,it.yy),siz[p]+=siz[it.xx];
tout[p]=VREME;
}
void build(int n)
{
ff(k,1,20) fff(i,1,n) up[k][i]=up[k-1][up[k-1][i]];
}
inline bool anc(int a, int b)
{
return tin[a]<=tin[b] && tout[a]>=tout[b];
}
int Lca(int a, int b)
{
bff(k,0,20)
if (!anc(up[k][a],b))
a=up[k][a];
if (!anc(a,b)) a=up[0][a];
return a;
}
li dist(int a, int b)
{
int c=Lca(a,b);
return dub[a]+dub[b]-2*dub[c];
}
pair<li,string> ans[100005];
vector<pii> qry[100005];
bool ishop[100005];
int root[100005]; //root za small to large (kao setovi, samo sa implicitnim umesto toga)
///glavni root je 1
void sms(int p, int q, int n, int E)
{
int gde,kolko=-1;
for (auto it : g[p])
if (it.xx!=q) sms(it.xx,p,n,E);
for (auto it : g[p])
if (it.xx!=q && (int)g[it.xx].size()>kolko)
kolko=(int)g[it.xx].size(),gde=it.xx;
if ((int)g[p].size()==1) root[p]=++idx;
else root[p]=root[gde];
if (ishop[p]) add(root[p],1,n,tin[p],1);
for (auto it : g[p])
if (it.xx!=q && it.xx!=gde)
spoji(root[it.xx],root[p],1,n,n);
for (auto [cvor,ind] : qry[p])
{
//cout<<p<<" "<<cvor<<" "<<E<<endl;
if (anc(p,cvor)==anc(p,E)) ans[ind]={-1,"escaped"};
else
{
//cout<<"pusi kurcinu: "<<p<<" "<<cvor<<endl;
if (anc(p,cvor))
{
int pp=pret(root[p],0,1,n,tin[cvor]);
int ss=sled(root[p],0,1,n,tin[cvor]);
if (pp==-1 && ss==-1) ans[ind]={-1,"oo"};
else
{
if (pp==-1) pp=pret(root[p],0,1,n,mod);
if (ss==-1) ss=sled(root[p],0,1,n,0);
ans[ind].xx=min(dist(cvor,ord[pp]),dist(cvor,ord[ss]));
}
//cout<<"jbt: "<<ind<<" odgovara "<<pp<<" "<<ss<<endl;
}
else
{
int pp=pret(1,root[p],1,n,tin[cvor]);
int ss=sled(1,root[p],1,n,tin[cvor]);
if (pp==-1 && ss==-1) ans[ind]={-1,"oo"};
else
{
if (pp==-1) pp=pret(1,root[p],1,n,mod);
if (ss==-1) ss=sled(1,root[p],1,n,0);
ans[ind].xx=min(dist(cvor,ord[pp]),dist(cvor,ord[ss]));
};
//cout<<"jbt: "<<ind<<" odgovara "<<ord[pp]<<" "<<ord[ss]<<endl;
}
}
}
/*cout<<p<<":"<<endl;
ispisi(root[p],1,n);
cout<<endl;*/
}
int main()
{
FAST;
int n,S,q,E;
cin>>n>>S>>q>>E;
ff(i,1,n)
{
int u,v,w; cin>>u>>v>>w;
g[u].pb({v,w}),g[v].pb({u,w});
eds[i]={{u,v},w};
}
dfs(1,0,0),tout[0]=VREME;
build(n);
while (S--)
{
int C; cin>>C;
ishop[C]=1;
}
++idx;
fff(i,1,n) if (ishop[i]) add(1,1,n,tin[i],1);
ff(i,0,q)
{
int ii,p; cin>>ii>>p;
if (anc(eds[ii].xx.xx,eds[ii].xx.yy)) swap(eds[ii].xx.xx,eds[ii].xx.yy);
qry[eds[ii].xx.xx].pb({p,i});
}
sms(1,0,n,E);
ff(i,0,q)
{
if (ans[i].xx==-1) cout<<ans[i].yy<<"\n";
else cout<<ans[i].xx<<"\n";
}
/*idx++;
while (true)
{
int t,x; cin>>t>>x;
if (t==1) add(1,0,1000,x,1);
else if (t==2) add(1,0,1000,x,-1);
else if (t==3) cout<<": "<<pret(1,0,1000,x)<<endl;
else if (t==4) cout<<": "<<sled(1,0,1000,x)<<endl;
}*/
}
//Note to self: Check for overflow
Compilation message
valley.cpp: In function 'void sms(int, int, int, int)':
valley.cpp:163:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
163 | for (auto [cvor,ind] : qry[p])
| ^
valley.cpp:157:26: warning: 'gde' may be used uninitialized in this function [-Wmaybe-uninitialized]
157 | else root[p]=root[gde];
| ~~~~~~~~^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
10452 KB |
Output is correct |
| 2 |
Correct |
9 ms |
10448 KB |
Output is correct |
| 3 |
Correct |
10 ms |
10452 KB |
Output is correct |
| 4 |
Correct |
8 ms |
10416 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
10452 KB |
Output is correct |
| 2 |
Correct |
9 ms |
10448 KB |
Output is correct |
| 3 |
Correct |
10 ms |
10452 KB |
Output is correct |
| 4 |
Correct |
8 ms |
10416 KB |
Output is correct |
| 5 |
Correct |
7 ms |
10452 KB |
Output is correct |
| 6 |
Incorrect |
6 ms |
10452 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
316 ms |
55016 KB |
Output is correct |
| 2 |
Correct |
387 ms |
62940 KB |
Output is correct |
| 3 |
Runtime error |
469 ms |
172680 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
10452 KB |
Output is correct |
| 2 |
Correct |
9 ms |
10448 KB |
Output is correct |
| 3 |
Correct |
10 ms |
10452 KB |
Output is correct |
| 4 |
Correct |
8 ms |
10416 KB |
Output is correct |
| 5 |
Correct |
7 ms |
10452 KB |
Output is correct |
| 6 |
Incorrect |
6 ms |
10452 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
