oj.uz

답안 #568188

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
568188 2022-05-24T20:13:02 Z mat_v Valley (BOI19_valley) C++14
100 / 100
 226 ms 44360 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
#define mod 998244353
#define xx first
#define yy second
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define ll long long
#define pii pair<int,ll>


using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>,rb_tree_tag, tree_order_statistics_node_update> ordered_set;/// find_by_order(x)(x+1th) , order_of_key() (strictly less)
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());


int n,m,q,e;
struct gr{
    int a;
    int b;
    ll w;
};

gr edges[100005];
vector<pii> graf[100005];

int lca[100005][20];
ll najm[100005][20];
int disc[100005];
int out[100005];
ll dub[100005];
ll dp[100005];
bool dobar[100005];
int br;

ll pom = 1e8;


void dfs(int x, int y, ll z){
    lca[x][0] = y;
    disc[x] = br;
    dub[x] = z;
    dp[x] = pom;
    if(dobar[x])dp[x] = 0;
    for(auto c:graf[x]){
        if(c.xx == y)continue;
        br++;
        dfs(c.xx,x,z+c.yy);
        dp[x] = min(dp[x], dp[c.xx] + c.yy);
    }
    out[x] = br;
    najm[x][0] = (dp[x] - dub[x]);
}

void resilca(int x, int y){
    ff(j,1,19){
        lca[x][j] = lca[lca[x][j-1]][j-1];
        najm[x][j] = min(najm[x][j - 1], najm[lca[x][j-1]][j-1]);
    }
    for(auto c:graf[x]){
        if(c.xx == y)continue;
        resilca(c.xx, x);
    }
}


bool insubtr(int x, int y){
    if(x == 0)return 1;
    if(x == y)return 1;
    if(disc[y] >= disc[x] && disc[y] <= out[x])return 1;
    return 0;
}

int main()
{

    ios_base::sync_with_stdio(false); cin.tie(0);
    pom *= pom;
    cin >> n >> m >> q >> e;
    ff(i,1,n)dp[i] = pom;
    ff(i,1,n - 1){
        int x,y,z;
        cin >> x >> y >> z;
        edges[i] = {x,y,z};
        graf[x].pb({y,z});
        graf[y].pb({x,z});
    }
    ff(i,1,m){
        int x;
        cin >> x;
        dobar[x] = 1;
    }
    ff(i,1,n)dp[i] += dub[i];
    br = 1;
    dfs(e,0,1);
    resilca(e,0);
    ll mks = 1e9;
    ll mks2 = 1e5;
    mks *= mks2;
    while(q--){
        int r,y;
        cin >> r >> y;
        int koji = edges[r].a;
        if(dub[edges[r].a] < dub[edges[r].b])koji = edges[r].b;

        if(!insubtr(koji,y)){
            cout << "escaped\n";
            continue;
        }
        ll ans = pom;
        ll dlt = dub[y];
        fb(j,19,0){
            if(insubtr(koji,lca[y][j])){
                ans = min(ans, najm[y][j]);
                y = lca[y][j];
            }
        }
        ans = min(ans, najm[y][0]);
        if(ans > mks)cout << "oo\n";
        else cout << ans + dlt << "\n";

    }

    return 0;
}

Compilation message

valley.cpp: In function 'void resilca(int, int)':
valley.cpp:6:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
valley.cpp:62:5: note: in expansion of macro 'ff'
   62 |     ff(j,1,19){
      |     ^~
valley.cpp: In function 'int main()':
valley.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
valley.cpp:86:5: note: in expansion of macro 'ff'
   86 |     ff(i,1,n)dp[i] = pom;
      |     ^~
valley.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
valley.cpp:87:5: note: in expansion of macro 'ff'
   87 |     ff(i,1,n - 1){
      |     ^~
valley.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
valley.cpp:94:5: note: in expansion of macro 'ff'
   94 |     ff(i,1,m){
      |     ^~
valley.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
valley.cpp:99:5: note: in expansion of macro 'ff'
   99 |     ff(i,1,n)dp[i] += dub[i];
      |     ^~
valley.cpp:7:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    7 | #define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
      |                           ^
valley.cpp:118:9: note: in expansion of macro 'fb'
  118 |         fb(j,19,0){
      |         ^~

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2824 KB Output is correct
2 Correct 4 ms 2832 KB Output is correct
3 Correct 3 ms 2772 KB Output is correct
4 Correct 4 ms 2772 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2824 KB Output is correct
2 Correct 4 ms 2832 KB Output is correct
3 Correct 3 ms 2772 KB Output is correct
4 Correct 4 ms 2772 KB Output is correct
5 Correct 2 ms 3084 KB Output is correct
6 Correct 2 ms 3028 KB Output is correct
7 Correct 3 ms 3028 KB Output is correct
8 Correct 2 ms 3084 KB Output is correct
9 Correct 3 ms 3028 KB Output is correct
10 Correct 3 ms 3028 KB Output is correct
11 Correct 3 ms 3028 KB Output is correct
12 Correct 3 ms 3028 KB Output is correct
13 Correct 2 ms 3028 KB Output is correct
14 Correct 3 ms 3028 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 140 ms 39748 KB Output is correct
2 Correct 168 ms 39724 KB Output is correct
3 Correct 167 ms 39832 KB Output is correct
4 Correct 188 ms 41636 KB Output is correct
5 Correct 175 ms 41836 KB Output is correct
6 Correct 226 ms 43888 KB Output is correct

Subtask #4
41.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2824 KB Output is correct
2 Correct 4 ms 2832 KB Output is correct
3 Correct 3 ms 2772 KB Output is correct
4 Correct 4 ms 2772 KB Output is correct
5 Correct 2 ms 3084 KB Output is correct
6 Correct 2 ms 3028 KB Output is correct
7 Correct 3 ms 3028 KB Output is correct
8 Correct 2 ms 3084 KB Output is correct
9 Correct 3 ms 3028 KB Output is correct
10 Correct 3 ms 3028 KB Output is correct
11 Correct 3 ms 3028 KB Output is correct
12 Correct 3 ms 3028 KB Output is correct
13 Correct 2 ms 3028 KB Output is correct
14 Correct 3 ms 3028 KB Output is correct
15 Correct 140 ms 39748 KB Output is correct
16 Correct 168 ms 39724 KB Output is correct
17 Correct 167 ms 39832 KB Output is correct
18 Correct 188 ms 41636 KB Output is correct
19 Correct 175 ms 41836 KB Output is correct
20 Correct 226 ms 43888 KB Output is correct
21 Correct 128 ms 39116 KB Output is correct
22 Correct 153 ms 38896 KB Output is correct
23 Correct 165 ms 39100 KB Output is correct
24 Correct 176 ms 41332 KB Output is correct
25 Correct 185 ms 44232 KB Output is correct
26 Correct 137 ms 39160 KB Output is correct
27 Correct 144 ms 39072 KB Output is correct
28 Correct 156 ms 39268 KB Output is correct
29 Correct 199 ms 40788 KB Output is correct
30 Correct 193 ms 42392 KB Output is correct
31 Correct 138 ms 39252 KB Output is correct
32 Correct 151 ms 39200 KB Output is correct
33 Correct 160 ms 39460 KB Output is correct
34 Correct 184 ms 41296 KB Output is correct
35 Correct 186 ms 44360 KB Output is correct
36 Correct 165 ms 41408 KB Output is correct