oj.uz

Submission #491463

# Submission time Handle Problem Language Result Execution time Memory
491463 2021-12-02T15:39:16 Z stefantaga Valley (BOI19_valley) C++14
100 / 100
 250 ms 51012 KB 
#include <bits/stdc++.h>
#define INF 10000000000000000
using namespace std;
typedef long long ll;
ll dist[200005],rmq[200005][20],din[200005][20];
bool viz[200005];
int niv[200005];
vector <pair <int,int>> v[200005];
void dfs(int x,int tata)
{
    if (viz[x]==1)
    {
        din[x][0]=dist[x];
    }
    else
    {
        din[x][0]=INF;
    }
    rmq[x][0]=tata;
    niv[x]=niv[tata]+1;
    for (int i=0;i<v[x].size();i++)
    {
        if (v[x][i].first==tata)
        {
            continue;
        }
        int nod = v[x][i].first;
        dist[nod]=dist[x]+v[x][i].second;
        dfs(nod,x);
        din[x][0]=min(din[x][0],din[nod][0]);
    }
}
struct wow
{
    int x,y,cost;
}muchie[200005];
int s,q,e,i,x,n,lg;
int lca (int x,int y)
{
    if (niv[x]<niv[y])
    {
        return lca(y,x);
    }
    if (x==y)
    {
        return x;
    }
    int dif=niv[x]-niv[y],p=1;
    for (int i=0;i<=lg;i++)
    {
        if ((dif&p))
        {
            x=rmq[x][i];
        }
        p=p*2;
    }
    if (x!=y)
    {
        for (int i=lg;i>=0;i--)
        {
            if (rmq[x][i]!=rmq[y][i])
            {
                x=rmq[x][i];
                y=rmq[y][i];
            }
        }
        x=rmq[x][0];
    }
    return x;
}
int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(0);
    #ifdef HOME
    ifstream cin("date.in");
    ofstream cout("date.out");
    #endif // HOME
    cin>>n>>s>>q>>e;
    for (i=1;i<=n-1;i++)
    {
        int x,y,cost;
        cin>>muchie[i].x>>muchie[i].y>>muchie[i].cost;
        x=muchie[i].x;
        y=muchie[i].y;
        cost=muchie[i].cost;
        v[x].push_back({y,cost});
        v[y].push_back({x,cost});
    }
    for (i=1;i<=s;i++)
    {
        cin>>x;
        viz[x]=1;
    }
    dfs(e,0);
    lg=log2(n);
    for (int j=1;j<=n;j++)
    {
        if (din[j][0]==INF)
        {
            continue;
        }
        din[j][0]=din[j][0]-2*dist[j];
    }
    for (i=1;i<=lg;i++)
    {
        for (int j=1;j<=n;j++)
        {
            din[j][i]=min(din[j][i-1],din[rmq[j][i-1]][i-1]);
            rmq[j][i]=rmq[rmq[j][i-1]][i-1];
        }
    }
    for (i=1;i<=q;i++)
    {
        int poz,x,y,ind;
        cin>>ind>>poz;
        x=muchie[ind].x;
        y=muchie[ind].y;
        if (niv[x]<niv[y])
        {
            swap(x,y);
        }
        if (lca(poz,x)!=x)
        {
            cout<<"escaped"<<'\n';
            continue;
        }
        ll minim=din[poz][0];
        int dif=niv[poz]-niv[x]+1;
        int p=1,initialito=poz;
        for (int j=0;j<=lg;j++)
        {
            if ((dif&p))
            {
                minim=min(minim,din[poz][j]);
                poz=rmq[poz][j];
            }
            p=p*2;
        }
        if (minim==INF)
        {
            cout<<"oo"<<'\n';
            continue;
        }
        cout<<minim+dist[initialito]<<'\n';
    }
    return 0;
}

Compilation message

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

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5196 KB Output is correct
2 Correct 7 ms 5200 KB Output is correct
3 Correct 6 ms 5200 KB Output is correct
4 Correct 5 ms 5200 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5196 KB Output is correct
2 Correct 7 ms 5200 KB Output is correct
3 Correct 6 ms 5200 KB Output is correct
4 Correct 5 ms 5200 KB Output is correct
5 Correct 3 ms 5456 KB Output is correct
6 Correct 4 ms 5456 KB Output is correct
7 Correct 3 ms 5424 KB Output is correct
8 Correct 3 ms 5340 KB Output is correct
9 Correct 3 ms 5456 KB Output is correct
10 Correct 4 ms 5456 KB Output is correct
11 Correct 4 ms 5456 KB Output is correct
12 Correct 4 ms 5456 KB Output is correct
13 Correct 4 ms 5456 KB Output is correct
14 Correct 4 ms 5456 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 47236 KB Output is correct
2 Correct 173 ms 46832 KB Output is correct
3 Correct 196 ms 46744 KB Output is correct
4 Correct 223 ms 48508 KB Output is correct
5 Correct 234 ms 48712 KB Output is correct
6 Correct 240 ms 50504 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5196 KB Output is correct
2 Correct 7 ms 5200 KB Output is correct
3 Correct 6 ms 5200 KB Output is correct
4 Correct 5 ms 5200 KB Output is correct
5 Correct 3 ms 5456 KB Output is correct
6 Correct 4 ms 5456 KB Output is correct
7 Correct 3 ms 5424 KB Output is correct
8 Correct 3 ms 5340 KB Output is correct
9 Correct 3 ms 5456 KB Output is correct
10 Correct 4 ms 5456 KB Output is correct
11 Correct 4 ms 5456 KB Output is correct
12 Correct 4 ms 5456 KB Output is correct
13 Correct 4 ms 5456 KB Output is correct
14 Correct 4 ms 5456 KB Output is correct
15 Correct 172 ms 47236 KB Output is correct
16 Correct 173 ms 46832 KB Output is correct
17 Correct 196 ms 46744 KB Output is correct
18 Correct 223 ms 48508 KB Output is correct
19 Correct 234 ms 48712 KB Output is correct
20 Correct 240 ms 50504 KB Output is correct
21 Correct 156 ms 46632 KB Output is correct
22 Correct 169 ms 46144 KB Output is correct
23 Correct 181 ms 46172 KB Output is correct
24 Correct 215 ms 48184 KB Output is correct
25 Correct 237 ms 51012 KB Output is correct
26 Correct 165 ms 46588 KB Output is correct
27 Correct 157 ms 46356 KB Output is correct
28 Correct 194 ms 46272 KB Output is correct
29 Correct 250 ms 47688 KB Output is correct
30 Correct 229 ms 49072 KB Output is correct
31 Correct 153 ms 46696 KB Output is correct
32 Correct 158 ms 46384 KB Output is correct
33 Correct 193 ms 46456 KB Output is correct
34 Correct 216 ms 48168 KB Output is correct
35 Correct 219 ms 50920 KB Output is correct
36 Correct 203 ms 48372 KB Output is correct