Submission #720642

#	Time	Username	Problem	Language	Result	Execution time	Memory
720642		n0sk1ll	Valley (BOI19_valley)	C++14	9 / 100	1060 ms	262144 KiB

valley

#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=16666666;
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 (stderr)

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];
      |                  ~~~~~~~~^

• Subtask 1: 9 / 9
• Subtask 2: 0 / 27
• Subtask 3: 0 / 23
• Subtask 4: 0 / 41