제출 #1110577

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1110577		vivo2006	Valley (BOI19_valley)	C++14	100 / 100	211 ms	67828 KiB

valley

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

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

using namespace std;

struct vertex
{
    int to, w;
};
struct Edge
{
    int v, u, w;
};
int n, s, q, root, 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 ++)
    {
        int marked;
        cin>>marked;
        isMarked[marked] = 1;
    }
    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)
{
    depth[v] = level;
    par[v][0] = p;
    vis[v] = 1;
    if(isMarked[v]) minD[v] = 0;
    else minD[v] = INF;
    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(depth[v] > depth[u]) swap(v, u);
    int dif = depth[u] - depth[v];
    for(int i = 0; i < 20; i ++)
    {
        if(dif & (1LL << i))
        {
            u = par[u][i];
        }
    }
    if(v == u) return u;
    for(int i = 19; 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];
    for(int i = 0; i < 20; i ++)
    {
        if(dif & (1 << i))
        {
            answer = min(answer, minDLCA[u][i] + path);
            path += sumLCA[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 && depth[v] <= depth[a] && depth[u] <= depth[a])
        {
            if(depth[v] < depth[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, 0, 0, 0);
    memset(vis, 0, sizeof vis);
    dfs(root, -1, 0);
    queries();
    return 0;
}

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