Submission #1110658

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110658		luvna	Valley (BOI19_valley)	C++14	100 / 100	116 ms	39584 KiB

valley

#include<bits/stdc++.h>

#define all(v) v.begin(), v.end()
#define endl "\n"
#define pii pair<int,int>

using namespace std;

typedef long long ll;

const int N = 1e5 + 15;
const int lg = 17;
const ll INF = 1e18;

int n, s, q, root;
pii edges[N];
vector<pii> g[N];
int par[N][lg+1];
int h[N];
ll dist[N];
int tin[N], tout[N], timerDFS;
bool shop[N];

void dfs(int u, int p){
    tin[u] = ++timerDFS;
    for(auto [v, w] : g[u]) if(v != p){
        h[v] = h[u] + 1;
        dist[v] = dist[u] + w;
        par[v][0] = u;
        for(int j = 1; j <= lg; j++) par[v][j] = par[par[v][j-1]][j-1];
        dfs(v,u);
    }
    tout[u] = timerDFS;
}

bool inside(int u, int v){
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}

ll best[N];
ll Up[N][lg+1];

void calc(int u, int p){
    best[u] = INF; // there is no shop in subtree u
    if(shop[u]) best[u] = dist[u];
    for(auto [v, w] : g[u]) if(v != p){
        calc(v,u);
        best[u] = min(best[u], best[v]);
    }
}

ll query(int v, int u){
    ll ans = INF;
    for(int j = lg; j >= 0; j--){
        if(h[u] - h[v] >= (1 << j)){
            ans = min(ans, Up[u][j]);
            u = par[u][j];
        }
    }
    return ans;
}

void solve(){
    cin >> n >> s >> q >> root;

    for(int i = 1; i < n; i++){
        int u, v, w; cin >> u >> v >> w;
        g[u].push_back(pii(v,w));
        g[v].push_back(pii(u,w));
        edges[i] = pii(u,v);
    }

    dfs(root,-1);

    for(int i = 1; i < n; i++){
        if(h[edges[i].first] > h[edges[i].second]) swap(edges[i].first, edges[i].second);
    }

    for(int i = 1; i <= s; i++){
        int u; cin >> u;
        shop[u] = true;
    }

    // dist[u] + dist[v] - 2*dist[lca]
    // best[u] = dist[v] - 2*dist[lca] : v has shop, inside(u,v)

    calc(root,-1);

    for(int i = 1; i <= n; i++){
        Up[i][0] = best[i] - 2*dist[i];
    }

    for(int j = 1; j <= lg; j++){
        for(int i = 1; i <= n; i++){
            Up[i][j] = min(Up[i][j-1], Up[par[i][j-1]][j-1]);
        }
    }

    while(q--){
        int id, node; cin >> id >> node;
        int u, v; tie(u,v) = edges[id];
        if(!inside(v,node)){
            cout << "escaped" << endl;
            continue;
        }
        if(best[v] == INF){// no shop in subtree v -> no shop for node
            cout << "oo" << endl;
            continue;
        }
        cout << dist[node] + query(edges[id].first, node) << endl;
    }
}

signed main(){
    ios_base::sync_with_stdio(NULL);
    cin.tie(0); cout.tie(0);

    #define task "task"

    if(fopen(task".INP", "r")){
        freopen(task".INP", "r", stdin);
        freopen(task".OUT", "w", stdout);
    }

    int t; t = 1; //cin >> t;
    while(t--) solve();
}

Compilation message (stderr)

valley.cpp: In function 'void dfs(int, int)':
valley.cpp:26:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   26 |     for(auto [v, w] : g[u]) if(v != p){
      |              ^
valley.cpp: In function 'void calc(int, int)':
valley.cpp:46:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   46 |     for(auto [v, w] : g[u]) if(v != p){
      |              ^
valley.cpp: In function 'int main()':
valley.cpp:121:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |         freopen(task".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:122:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |         freopen(task".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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