제출 #594106

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
594106		Do_you_copy	Valley (BOI19_valley)	C++17	100 / 100	276 ms	57460 KiB

valley

#include <bits/stdc++.h>
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using pii = pair <ll, ll>;
using pil = pair <ll, ll>;
using pli = pair <ll, ll>;
using pll = pair <ll, ll>;
using ull = unsigned ll;
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());

ll min(const ll &a, const ll &b){
    return (a < b) ? a : b;
}

ll max(const ll &a, const ll &b){
    return (a > b) ? a : b;
}

//const ll Mod = 1000000009;
//const ll Mod2 = 999999999989;
//only use when required
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll maxN = 2e5 + 1;
ll n, s, q, e;
ll cnt = 1;
ll a[maxN], pos[maxN], dis[maxN], rpos[maxN], child[maxN];
ll depth[maxN];
bool isshop[maxN];
vector <pii> adj[maxN];
ll st[maxN * 4];
pii edge[maxN];

void build(ll id = 1, ll l = 1, ll r = n){
    if (l == r){
        st[id] = isshop[rpos[l]] ? dis[rpos[l]] : inf;
        return;
    }
    ll mid = (l + r) / 2;
    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);
    st[id] = min(st[id * 2], st[id * 2 + 1]);
}

ll get(ll id, ll i, ll j, ll l = 1, ll r = n){
    if (r < i || l > j) return inf;
    if (i <= l && r <= j) return st[id];
    ll mid = (l + r) / 2;
    return min(get(id * 2, i, j, l, mid), get(id * 2 + 1, i, j, mid + 1, r));
}

void pre_dfs(ll u, ll p){
    pos[u] = cnt;
    rpos[cnt++] = u;
    depth[u] = depth[p] + 1;
    for (const pii &i: adj[u]){
        if (i.fi == p) continue;
        dis[i.fi] = dis[u] + i.se;
        pre_dfs(i.fi, u);
        child[u] += child[i.fi] + 1;
    }
}

pii stble[maxN][20];
void dfs(ll u, ll p){
    stble[u][0].fi = get(1, pos[u], pos[u] + child[u]);
    if (stble[u][0].fi != inf) stble[u][0].fi -= dis[u];
    stble[u][0].se = p;
    for (ll i = 1; i < 20; ++i){
        stble[u][i].fi = min(stble[u][i - 1].fi, stble[stble[u][i - 1].se][i - 1].fi + dis[u] - dis[stble[u][i - 1].se]);
        stble[u][i].se = stble[stble[u][i - 1].se][i - 1].se;
    }
    for (const pii &i: adj[u]){
        if (i.fi == p) continue;
        dfs(i.fi, u);
    }
}

ll findshop(ll u, ll v){
    ll k = depth[u] - depth[v];
    ll uu = u;
    ll ans = inf;
    for (ll i = 19; i >= 0; --i){
        if (depth[stble[u][i].se] >= depth[v] - 1){
            ans = min(ans, stble[u][i].fi + dis[uu] - dis[u]);
            u = stble[u][i].se;
        }
    }
    return ans;
}

void Init(){
    cin >> n >> s >> q >> e;
    for (ll i = 1; i < n; ++i){
        ll u, v, w;
        cin >> u >> v >> w;
        edge[i] = {u, v};
        adj[u].pb({v, w});
        adj[v].pb({u, w});
    }
    for (ll i = 1; i <= s; ++i){
        ll t; cin >> t;
        isshop[t] = 1;
    }
    for (ll i = 0; i <= n; ++i){
        for (ll j = 0; j < 20; ++j) stble[i][j] = {inf, 0};
    }
    pre_dfs(e, 0);
    build();
    dfs(e, 0);
    while (q--){
        ll i, r;
        cin >> i >> r;
        ll u, v;
        u = dis[edge[i].fi] < dis[edge[i].se] ? edge[i].fi : edge[i].se;
        v = u ^ edge[i].fi ^ edge[i].se;
        if (pos[r] < pos[v] || pos[r] > pos[v] + child[v]){
            cout << "escaped\n";
        }
        else{
            ll tem = findshop(r, v);
            if (tem >= inf) cout << "oo\n";
            else cout << tem << "\n";
        }
    }
}


int main(){
    if (fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin);
        //freopen(taskname".out", "w", stdout);
    }
    faster;
    ll tt = 1;
    //cin >> tt;
    while (tt--){
        Init();
    }
}

컴파일 시 표준 에러 (stderr) 메시지

valley.cpp: In function 'll findshop(ll, ll)':
valley.cpp:84:8: warning: unused variable 'k' [-Wunused-variable]
   84 |     ll k = depth[u] - depth[v];
      |        ^
valley.cpp: In function 'int main()':
valley.cpp:135:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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