Submission #670799

#	Time	Username	Problem	Language	Result	Execution time	Memory
670799		groshi	Valley (BOI19_valley)	C++17	100 / 100	172 ms	34364 KiB

valley

#include<iostream>
#include<vector>
#define int long long
using namespace std;
int n,s,q,e;
struct wi{
    vector<int> Q;
    int pre=0,post=0;
    int odl=0;
    int poz=0;
    bool jest=0;
    int real=0;
}*w;
pair<int,int> co[200000];
vector<pair<int,int> > zap[200000];
int pree=1,postt=1;
int drzewo[1000000];
int wyn[200000];
int pot=1;
void dfs(int x,int ojc)
{
    w[x].poz=w[ojc].poz+1;
    w[x].pre=pree;
    pree++;
    w[x].real=1e18;
    if(w[x].jest)
        w[x].real=0;
    for(int i=0;i<w[x].Q.size();i+=2)
    {
        int pom=w[x].Q[i];
        if(pom==ojc)
            continue;
        w[pom].odl=w[x].odl+w[x].Q[i+1];
        dfs(pom,x);
        w[x].real=min(w[x].real,w[pom].real+w[x].Q[i+1]);
    }
    w[x].post=postt;
    postt++;
}
void ustaw(int x,int co)
{
    x+=pot;
    drzewo[x]=co;
    x/=2;
    while(x>0)
    {
        drzewo[x]=min(drzewo[x*2],drzewo[x*2+1]);
        x/=2;
    }
}
int zapp(int x,int y)
{
    if(y<x)
        swap(x,y);
    x+=pot;
    y+=pot;
    int wynik=min(drzewo[x],drzewo[y]);
    while(x/2!=y/2)
    {
        if(x%2==0)
            wynik=min(wynik,drzewo[x+1]);
        if(y%2==1)
            wynik=min(wynik,drzewo[y-1]);
        x/=2;
        y/=2;
    }
    return wynik;
}
void dfs2(int x,int ojc)
{
    ustaw(w[x].poz,w[x].real-w[x].odl);
    for(int i=0;i<zap[x].size();i++)
    {
        int kto=zap[x][i].first;
        int gdzie=zap[x][i].second;
        int dol;
        if(w[co[gdzie].first].poz<w[co[gdzie].second].poz)
            dol=co[gdzie].second;
        else dol=co[gdzie].first;
        if(!(w[x].pre>=w[dol].pre && w[x].post<=w[dol].post))
        {
            wyn[kto]=-1;
            continue;
        }
        wyn[kto]=zapp(w[x].poz,w[dol].poz)+w[x].odl;
    }
    for(int i=0;i<w[x].Q.size();i+=2)
    {
        int pom=w[x].Q[i];
        if(pom==ojc)
            continue;
        dfs2(pom,x);
    }
    ustaw(w[x].poz,1e18);
}
int32_t main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    int x,y,z;
    cin>>n>>s>>q>>e;
    w=new wi[n+3];
    while(pot<=n)
        pot*=2;
    pot--;
    for(int i=1;i<n;i++)
    {
        cin>>x>>y>>z;
        w[x].Q.push_back(y);
        w[x].Q.push_back(z);
        w[y].Q.push_back(x);
        w[y].Q.push_back(z);
        co[i]={x,y};
    }
    for(int i=1;i<=s;i++)
    {
        cin>>x;
        w[x].jest=1;
    }
    for(int i=1;i<=q;i++)
    {
        cin>>x>>y;
        zap[y].push_back({i,x});
    }
    dfs(e,0);
    for(int i=1;i<=pot*2+1;i++)
        drzewo[i]=1e18;
    dfs2(e,0);
    for(int i=1;i<=q;i++)
    {
        if(wyn[i]==-1)
            cout<<"escaped\n";
        else if(wyn[i]>=1e18)
            cout<<"oo\n";
        else cout<<wyn[i]<<"\n";
    }
    return 0;
}

Compilation message (stderr)

valley.cpp: In function 'void dfs(long long int, long long int)':
valley.cpp:28:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(int i=0;i<w[x].Q.size();i+=2)
      |                 ~^~~~~~~~~~~~~~
valley.cpp: In function 'void dfs2(long long int, long long int)':
valley.cpp:72:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for(int i=0;i<zap[x].size();i++)
      |                 ~^~~~~~~~~~~~~~
valley.cpp:87:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     for(int i=0;i<w[x].Q.size();i+=2)
      |                 ~^~~~~~~~~~~~~~

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