oj.uz

Submission #335039

# Submission time Handle Problem Language Result Execution time Memory
335039 2020-12-11T00:24:00 Z gmyu Valley (BOI19_valley) C++14
100 / 100
 650 ms 41256 KB 
/*
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

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 2924 KB Output is correct
2 Correct 29 ms 2924 KB Output is correct
3 Correct 29 ms 2924 KB Output is correct
4 Correct 29 ms 2924 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 2924 KB Output is correct
2 Correct 29 ms 2924 KB Output is correct
3 Correct 29 ms 2924 KB Output is correct
4 Correct 29 ms 2924 KB Output is correct
5 Correct 6 ms 3052 KB Output is correct
6 Correct 6 ms 3052 KB Output is correct
7 Correct 7 ms 3052 KB Output is correct
8 Correct 6 ms 3052 KB Output is correct
9 Correct 6 ms 3052 KB Output is correct
10 Correct 6 ms 3052 KB Output is correct
11 Correct 6 ms 3052 KB Output is correct
12 Correct 6 ms 3052 KB Output is correct
13 Correct 7 ms 3052 KB Output is correct
14 Correct 6 ms 3052 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 536 ms 38424 KB Output is correct
2 Correct 565 ms 38032 KB Output is correct
3 Correct 575 ms 37868 KB Output is correct
4 Correct 610 ms 39148 KB Output is correct
5 Correct 592 ms 39276 KB Output is correct
6 Correct 650 ms 40748 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 2924 KB Output is correct
2 Correct 29 ms 2924 KB Output is correct
3 Correct 29 ms 2924 KB Output is correct
4 Correct 29 ms 2924 KB Output is correct
5 Correct 6 ms 3052 KB Output is correct
6 Correct 6 ms 3052 KB Output is correct
7 Correct 7 ms 3052 KB Output is correct
8 Correct 6 ms 3052 KB Output is correct
9 Correct 6 ms 3052 KB Output is correct
10 Correct 6 ms 3052 KB Output is correct
11 Correct 6 ms 3052 KB Output is correct
12 Correct 6 ms 3052 KB Output is correct
13 Correct 7 ms 3052 KB Output is correct
14 Correct 6 ms 3052 KB Output is correct
15 Correct 536 ms 38424 KB Output is correct
16 Correct 565 ms 38032 KB Output is correct
17 Correct 575 ms 37868 KB Output is correct
18 Correct 610 ms 39148 KB Output is correct
19 Correct 592 ms 39276 KB Output is correct
20 Correct 650 ms 40748 KB Output is correct
21 Correct 511 ms 37484 KB Output is correct
22 Correct 521 ms 36972 KB Output is correct
23 Correct 549 ms 36968 KB Output is correct
24 Correct 577 ms 38636 KB Output is correct
25 Correct 609 ms 40880 KB Output is correct
26 Correct 500 ms 37612 KB Output is correct
27 Correct 527 ms 37376 KB Output is correct
28 Correct 541 ms 37356 KB Output is correct
29 Correct 571 ms 38380 KB Output is correct
30 Correct 616 ms 39404 KB Output is correct
31 Correct 517 ms 37920 KB Output is correct
32 Correct 526 ms 37356 KB Output is correct
33 Correct 538 ms 37356 KB Output is correct
34 Correct 588 ms 39020 KB Output is correct
35 Correct 612 ms 41256 KB Output is correct
36 Correct 561 ms 39152 KB Output is correct