Submission #1110553

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110553		vivo2006	Valley (BOI19_valley)	C++14	0 / 100	90 ms	75408 KiB

valley

#include<iostream>
#include<vector>
#include<cstring>

#define MAXN 100001
#define INF 1e18
#define int long long

using namespace std;

struct vertex
{
    int to, w;
};
struct Edge
{
    int v, u, w;
};
int n, s, q, root, marked[MAXN], par[MAXN][20], minD[MAXN], minDLCA[MAXN][20], sumLCA[MAXN][20], dulb[MAXN];
vector<vertex> M[MAXN];
vector<Edge> adj;
bool vis[MAXN], isMarked[MAXN];

void read()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>s>>q>>root;
    for(int i = 0; i < n - 1; i ++)
    {
        int a, b, w;
        cin>>a>>b>>w;
        M[a].push_back({b, w});
        M[b].push_back({a, w});
        adj.push_back({a, b, w});
    }
    for(int i = 0; i < s; i ++)
    {
        cin>>marked[i];
        isMarked[marked[i]] = 1;
    }
    fill_n(minD, sizeof minD, INF);
    for(int i = 0; i <= n; i ++)
    {
        for(int j = 0; j < 20; j ++) minDLCA[i][j] = INF;
    }
}
void buildLCA(int v, int p, int level, int w)
{
    if(v >= 0) dulb[v] = level;
    //par[v][0] = p;
    vis[v] = 1;
    /*if(isMarked[v]) minD[v] = 0;
    sumLCA[v][0] = w;*/

    /*for(int i = 1; i < 20; i ++)
    {
        par[v][i] = par[par[v][i - 1]][i - 1];
        sumLCA[v][i] = sumLCA[v][i - 1] + sumLCA[par[v][i - 1]][i - 1];
    }*/
    for(auto u : M[v])
    {
        if(!vis[u.to])
        {
            buildLCA(u.to, v, level + 1, u.w);
            //minD[v] = min(minD[v], minD[u.to] + u.w);
        }
    }
}
void dfs(int v, int p, int w)
{
    vis[v] = 1;
    if(p != -1) minDLCA[v][0] = min(minD[v], minD[p] + w);
    for(int i = 1; i < 20; i ++)
    {
        minDLCA[v][i] = min(minDLCA[v][i - 1], minDLCA[par[v][i - 1]][i - 1] + sumLCA[v][i - 1]);
    }
    for(auto u : M[v])
    {
        if(!vis[u.to])
        {
            dfs(u.to, v, u.w);
        }
    }

}
int LCA(int v, int u)
{
    if(dulb[v] > dulb[u]) swap(v, u);
    int dif = dulb[u] - dulb[v];
    for(int i = 0; i < 21; i ++)
    {
        if(dif & (1 << i))
        {
            u = par[u][i];
        }
    }
    if(v == u) return u;
    for(int i = 20; i > -1; i --)
    {
        if(par[v][i] != par[u][i])
        {
            v = par[v][i];
            u = par[u][i];
        }
    }

    return par[v][0];
}
int LCAans(int v, int u)
{
    if(v == u) return minD[v];
    int path = 0, answer = INF;
    if(dulb[u] < dulb[v]) swap(u, v);
    int dif = dulb[u] - dulb[v];
    for(int i = 0; i < 21; i ++)
    {
        if(dif & (1 << i))
        {
            answer = min(answer, minDLCA[u][i]);
            u = par[u][i];
        }
    }
    return answer;
}
void queries()
{
    for(int i = 0; i < q; i ++)
    {
        int a, b;
        cin>>b>>a;
        b --;
        int v = adj[b].v, u = adj[b].u;
        if(LCA(v, a) == v && LCA(u, a) == u && dulb[v] <= dulb[a] && dulb[u] <= dulb[a])
        {
            if(dulb[v] < dulb[u]) swap(v, u);
            int ans = LCAans(a, v);
            if(ans == INF) cout<<"oo\n";
            else cout<<ans<<'\n';
        }
        else cout<<"escaped\n";
    }
}
signed main()
{
    read();
    buildLCA(root, -1, 0, 0);
    /*memset(vis, 0, sizeof vis);
    dfs(root, -1, 0);*/
    queries();
    return 0;
}
/*
5 2 3 1
1 2 3
1 3 2
3 4 1
3 5 2
2
4
2 2
2 5
4 5

10 2 1 4
7 2 3
4 8 3
9 10 1
6 7 3
9 2 3
10 1 2
8 2 2
5 2 1
3 8 2
8
7
2 1

*/

Compilation message (stderr)

valley.cpp: In function 'long long int LCAans(long long int, long long int)':
valley.cpp:114:9: warning: unused variable 'path' [-Wunused-variable]
  114 |     int path = 0, answer = INF;
      |         ^~~~

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