Submission #1110533

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110533		vivo2006	Valley (BOI19_valley)	C++14	0 / 100	102 ms	90848 KiB

valley

#include<iostream>
#include<vector>

#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], depth[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)
{
    depth[v] = level;
    par[v][0] = p;
    vis[v] = 1;
    if(isMarked[v]) minD[v] = 0;
    for(auto u : M[v])
    {
        if(!vis[u.to])
        {
            sumLCA[u.to][0] = u.w;
            buildLCA(u.to, v, level + 1);
            minD[v] = min(minD[v], minD[u.to] + u.w);
        }
    }
    if(p != -1) minDLCA[v][0] = minD[p];
    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];
        minDLCA[v][i] = min(minDLCA[v][i - 1], minDLCA[par[v][i - 1]][i - 1] + sumLCA[v][i - 1]);
    }
}
int LCA(int v, int u)
{
    if(depth[v] > depth[u]) swap(v, u);
    int dif = depth[u] - depth[v];
    //cout<<"Beginning:"<<v<<" "<<u<<endl;
    for(int i = 0; i < 21; i ++)
    {
        if(dif & (1 << i))
        {
            u = par[u][i];
        }
    }
    if(v == u) return u;
    //cout<<v<<" "<<u<<endl;
    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(depth[u] < depth[v]) swap(u, v);
    int dif = depth[u] - depth[v];
    //cout<<"Difference = "<<dif<<endl;
    //cout<<v<<" "<<u<<endl;
    for(int i = 0; i < 21; i ++)
    {
        if(dif & (1 << i))
        {
            path += sumLCA[u][i];
            answer = min(answer, minDLCA[u][i] + path);
            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 && depth[v] <= depth[a] && depth[u] <= depth[a])
        {
            if(depth[v] < depth[u]) swap(v, u);
            //cout<<"! "<<v<<" "<<u<<endl;
            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);
    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
*/

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