Submission #335039

#	Time	Username	Problem	Language	Result	Execution time	Memory
335039		gmyu	Valley (BOI19_valley)	C++14	100 / 100	650 ms	41256 KiB

valley

/*
ID: USACO_template
LANG: C++
PROG: USACO
*/
#include <iostream>  //cin , cout
#include <fstream>   //fin, fout
#include <stdio.h>   // scanf , pringf
#include <cstdio>
#include <algorithm> // sort , stuff
#include <stack>     // stacks
#include <queue>     // queues
#include <map>
#include <string>

using namespace std;

typedef pair<int, int>          pii;
typedef vector<int>             vi;     /// adjlist without weight
typedef vector<pii>             vii;    /// adjlist with weight
typedef vector<pair<int,pii>>   vpip;   /// edge with weight
typedef long long               ll;

#define mp  make_pair
#define fst first
#define snd second
#define pb  push_back
#define sz(x) (int)(x).size()
#define trav(u, adj_v) for (auto& u: adj_v)

const int MOD = 1e9+7;  // 998244353;
const int MX  = 2e5+5;   //
const ll  INF = 1e18;    //

#define MAXV 100007
#define MAXE 100007

/// code from USACO examples
void setIO(string name) {
    ios_base::sync_with_stdio(0); cin.tie(0);
    freopen((name+".in").c_str(),"r",stdin);
    freopen((name+".out").c_str(),"w",stdout);
}
bool debug = false, submit = true;

int N, S, Q, E;
vii adj[MAXV];
pii edge[MAXV];
int isShop[MAXV];

#define MAXLCALOG 20
int p[MAXV], depth[MAXV], anc[MAXV][MAXLCALOG];
ll dist[MAXV], dp[MAXV], dpanc[MAXV][MAXLCALOG];

void buildTree(int v_s) {
    depth[v_s] = 0; p[v_s] = 0; dist[v_s] = 0LL;

    queue<int> q;
    q.push(v_s);
    while(!q.empty()) {
        int curr = q.front();
        q.pop();
        for(int i = 0; i < adj[curr].size(); i++) {
            int u = adj[curr][i].fst;
            if (u == p[curr]) continue;
            p[u] = curr;
            depth[u] = 1 + depth[curr];
            dist[u] = dist[curr] + adj[curr][i].snd;
            q.push(u);
        }
    }
}
void prepLCA() {
    for(int i = 1; i <= N; i++) anc[i][0] = p[i];

    for(int j = 1; j < MAXLCALOG; j++)
        for(int i = 1; i <= N; i++)
            anc[i][j] = anc[anc[i][j-1]][j-1];
}
int upD(int curr, int dist) {
    if(dist == 0) return curr;
    for(int k = MAXLCALOG - 1; k>=0; k--) {
        while(dist >= (1<<k) ) {
            curr = anc[curr][k];
            dist  -= (1<<k);
        }
        if(dist == 0) return curr;
    }
    return curr;
}
int getP(int curr, int wantedD) {
    for(int k = MAXLCALOG - 1; depth[curr] != wantedD; k--) {
        while(depth[curr] - (1<<k) >= wantedD) {
            curr = anc[curr][k];
        }
    }
    return curr;
}

bool canEscape(int b, int s) {
    if(depth[s] < depth[b]) return true;
    if(depth[s] == depth[b]) return (s!=b);

    /// now s is deeper than b
    int dist = depth[s] - depth[b];
    if(upD(s, dist) == b) return false;
    return true;
}
ll dfsDP(int v) {
    if(v != E && sz(adj[v]) == 1) {
        // leaf
        if (isShop[v]) {
            dp[v] = dist[v] - dist[v] * 2LL;
            return dist[v];
        } else {
            dp[v] = INF;
            return INF;
        }
    }

    ll minShopDist = INF;
    if(isShop[v]) minShopDist = dist[v];
    dp[v] = INF;

    for(int i = 0; i < sz(adj[v]); i++) {
        int u = adj[v][i].fst;
        if (u == p[v]) continue;
        ll d0 = dfsDP(u);
        minShopDist = min(minShopDist, d0);
    }
    if(minShopDist!= INF) dp[v] = minShopDist - dist[v] * 2LL;

    return minShopDist;
}


void prepDPjump() {
    for(int i = 1; i <= N; i++) dpanc[i][0] = min(dp[i], dp[anc[i][0]]);

    for(int j = 1; j < MAXLCALOG; j++)
        for(int i = 1; i <= N; i++)
            dpanc[i][j] = min(dpanc[i][j-1], dpanc[anc[i][j-1]][j-1]);
}
ll dpUpD(int curr, int dist) {
    if(dist == 0) return dp[curr];
    ll ans0 = INF;
    for(int k = MAXLCALOG - 1; k>=0; k--) {
        while(dist >= (1<<k) ) {
            ans0 = min(ans0, dpanc[curr][k]);
            curr = anc[curr][k];
            dist  -= (1<<k);
        }
        if(dist == 0) return min(ans0, dp[curr]);
    }
    return min(ans0, dp[curr]);
}

int main() {
    debug = true; submit = false;
    if(submit) setIO("testName");

    int i, j, k;

    cin >> N >> S >> Q >> E;
    for(i=1;i<=N-1;i++) {
        int a, b, w; cin >> a >> b >> w;
        adj[a].pb(mp(b,w)); adj[b].pb(mp(a, w));
        edge[i] = mp(a, b);
    }
    buildTree(E); prepLCA();

    for(i=0; i<S; i++) {
        int a; cin >> a;
        isShop[a] = 1;
    }
    dfsDP(E);
    prepDPjump();

    for(i = 0; i<Q; i++) {
        int ei, src; cin >> ei >> src;
        int a = edge[ei].fst, b = edge[ei].snd;
        if(depth[a] > depth[b]) swap(a, b);
        if(canEscape(b, src)) {
            cout << "escaped" << endl;
        } else {
            int d0 = depth[src] - depth[b];
            ll ans = dpUpD(src, d0);
            if(ans == INF) cout << "oo" << endl;
            else cout << dist[src] + ans << endl;
        }

    }


}

Compilation message (stderr)

valley.cpp: In function 'void buildTree(int)':
valley.cpp:63:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         for(int i = 0; i < adj[curr].size(); i++) {
      |                        ~~^~~~~~~~~~~~~~~~~~
valley.cpp: In function 'int main()':
valley.cpp:162:12: warning: unused variable 'j' [-Wunused-variable]
  162 |     int i, j, k;
      |            ^
valley.cpp:162:15: warning: unused variable 'k' [-Wunused-variable]
  162 |     int i, j, k;
      |               ^
valley.cpp: In function 'void setIO(std::string)':
valley.cpp:41:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   41 |     freopen((name+".in").c_str(),"r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:42:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   42 |     freopen((name+".out").c_str(),"w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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