oj.uz

답안 #494307

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
494307 2021-12-15T05:05:19 Z wiwiho Valley (BOI19_valley) C++14
100 / 100
 984 ms 118312 KB 
#include <bits/stdc++.h>
#include <bits/extc++.h>

#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define iter(a) a.begin(), a.end()
#define riter(a) a.rbegin(), a.rend()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(riter(a))
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define pf(a) push_front(a)
#define ef(a) emplace_front(a)
#define pob pop_back()
#define pof pop_front()
#define mp(a, b) make_pair(a, b)
#define F first
#define S second
#define mt make_tuple
#define gt(t, i) get<i>(t)
#define tomax(a, b) ((a) = max((a), (b)))
#define tomin(a, b) ((a) = min((a), (b)))
#define topos(a) ((a) = (((a) % MOD + MOD) % MOD))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b) {bool pvaspace=false; \
for(auto pva : a){ \
    if(pvaspace) b << " "; pvaspace=true;\
    b << pva;\
}\
b << "\n";}

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
using tiii = tuple<int, int, int>;

const ll MOD = 1000000007;
const ll MAX = 1LL << 60;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}

ll ifloor(ll a, ll b){
    if(b < 0) a *= -1, b *= -1;
    if(a < 0) return (a - b + 1) / b;
    else return a / b;
}

ll iceil(ll a, ll b){
    if(b < 0) a *= -1, b *= -1;
    if(a > 0) return (a + b - 1) / b;
    else return a / b;
}

int n;
struct SegmentTree{
    vector<ll> st;
    int sz;
    explicit SegmentTree(int sz): sz(sz){
        st.resize(4 * sz, MAX);
    }
    void modify(int x, ll v, int L = 1, int R = n, int id = 0){
        //cerr << "modify " << x << " " << v << " " << L << " " << R << " " << sz << "\n";
        //assert(L <= R);
        if(L == R){
            st[id] = v;
            return;
        }
        int M = (L + R) / 2;
        if(x <= M) modify(x, v, L, M, 2 * id + 1);
        else modify(x, v, M + 1, R, 2 * id + 2);
        st[id] = min(st[2 * id + 1], st[2 * id + 2]);
    }
    ll query(int l, int r, int L = 1, int R = n, int id = 0){
        if(l > r) return MAX;
        if(l <= L && R <= r) return st[id];
        int M = (L + R) / 2;
        if(r <= M) return query(l, r, L, M, 2 * id + 1);
        else if(l > M) return query(l, r, M + 1, R, 2 * id + 2);
        else return min(query(l, r, L, M, 2 * id + 1), query(l, r, M + 1, R, 2 * id + 2));
    }
};


vector<vector<pii>> g;
vector<bool> shop;
vector<vector<int>> pr, in, out;
vector<vector<ll>> dpt;
vector<SegmentTree> st;
vector<int> sz, ts;
vector<bool> del;

const int SZ = 20;

vector<pii> e;
int esc;

void init(){
    g.resize(n + 1);
    shop.resize(n + 1);
    pr.resize(SZ, vector<int>(n + 1, -1));
    in.resize(SZ, vector<int>(n + 1, -1));
    out.resize(SZ, vector<int>(n + 1, -1));
    dpt.resize(SZ, vector<ll>(n + 1));
    st.resize(SZ, SegmentTree(n));
    sz.resize(n + 1);
    del.resize(n + 1);
    ts.resize(SZ);

    e.resize(n);
}

void dfsg(int now, int p){
    sz[now] = 1;
    for(pii i : g[now]){
        if(i.F == p || del[i.F]) continue;
        dfsg(i.F, now);
        sz[now] += sz[i.F];
    }
}

int cen;
void dfsg2(int now, int p, int t){
    int mx = t - sz[now];
    for(pii i : g[now]){
        if(i.F == p || del[i.F]) continue;
        mx = max(mx, sz[i.F]);
        dfsg2(i.F, now, t);
    }
    if(mx <= t / 2) cen = now;
}

void dfssub(int now, int p, ll d, int gd){
    in[gd][now] = ++ts[gd];
    pr[gd][now] = cen;
    dpt[gd][now] = d;
    if(shop[now]){
        st[gd].modify(in[gd][now], d, 1, n, 0);
    }
    for(pii i : g[now]){
        if(i.F == p || del[i.F]) continue;
        dfssub(i.F, now, d + i.S, gd);
    }
    out[gd][now] = ts[gd];
}

void solve(int rt, int gd){
    dfsg(rt, rt);
    dfsg2(rt, rt, sz[rt]);
    dfssub(cen, cen, 0, gd);
    //cerr << "solve " << cen << "  ";
    //printv(sub[cen], cerr);
    
    del[cen] = true;
    for(pii i : g[cen]){
        if(!del[i.F]) solve(i.F, gd + 1);
    }
}

ll oao = MAX;
void query(int u1, int u2, int v){
    
    for(int i = SZ - 1; i >= 0; i--){
        if(pr[i][v] == -1 || pr[i][esc] == -1) continue;
        if(pr[i][v] != pr[i][esc]) continue;
        int cen = pr[i][v];

        if(pr[i][u1] != cen || pr[i][u2] != cen){
            cout << "escaped\n";
            return;
        }

        if(in[i][u1] > in[i][u2]) swap(u1, u2);

        if(in[i][u2] <= in[i][v] && out[i][v] <= out[i][u2]) break;
        if(in[i][u2] <= in[i][esc] && out[i][esc] <= out[i][u2]) break;

        cout << "escaped\n";
        return;
    }

    ll ans = MAX;
    for(int i = SZ - 1; i >= 0; i--){
        if(pr[i][v] == -1) continue;

        int cen = pr[i][v];
        if(pr[i][u1] != cen || pr[i][u2] != cen){
            ans = min(ans, dpt[i][v] + st[i].query(in[i][cen], out[i][cen]));
            //cerr << "query " << i << " " << v << " " << "\n";
            //for(int j = in[i][cen]; j <= out[i][cen]; j++) cerr << st[i].query(j, j) << " ";
            //cerr << "\n";
            continue;
        }
        
        if(in[i][u1] > in[i][u2]) swap(u1, u2);
        if(in[i][u2] <= in[i][v] && out[i][v] <= out[i][u2]) continue;
        ans = min(ans, dpt[i][v] + st[i].query(in[i][cen], in[i][u2] - 1));
        ans = min(ans, dpt[i][v] + st[i].query(out[i][u2] + 1, out[i][cen]));
        /*if(in[i][v] <= in[i][u2] && out[i][u2] <= out[i][v]){
            ans = min(ans, dpt[i][v] + st[i].query(in[i][cen], in[i][v] - 1));
            ans = min(ans, dpt[i][v] + st[i].query(out[i][v] + 1, out[i][cen]));
        }
        else if(in[i][u2] <= in[i][v]){
            ans = min(ans, dpt[i][v] + st[i].query(in[i][cen], in[i][u2] - 1));
            ans = min(ans, dpt[i][v] + st[i].query(out[i][u2] + 1, in[i][v] - 1));
            ans = min(ans, dpt[i][v] + st[i].query(out[i][v] + 1, out[i][cen]));
        }
        else{
            ans = min(ans, dpt[i][v] + st[i].query(in[i][cen], in[i][v] - 1));
            ans = min(ans, dpt[i][v] + st[i].query(out[i][v] + 1, in[i][u2] - 1));
            ans = min(ans, dpt[i][v] + st[i].query(out[i][u2] + 1, out[i][cen]));
        }*/
    }

    //if(ans != oao) cerr << ans << " " << oao << "\n";
    //assert(ans == oao);
    if(ans == MAX) cout << "oo\n";
    else cout << ans << "\n";
    //if(oao == MAX) cout << "oo\n";
    //else cout << oao << "\n";
}

void dfsbf(int now, int p, int u1, int u2, ll d){
    if(now == esc) oao = -1;
    if(shop[now]) oao = min(oao, d);
    for(pii i : g[now]){
        if(i.F == p) continue;
        if(mp(now, i.F) == mp(u1, u2) || mp(now, i.F) == mp(u2, u1)) continue;
        dfsbf(i.F, now, u1, u2, d + i.S);
    }
}

int N = 20;
mt19937 rnd(2124123);
uniform_int_distribution<int> ud(1, 1000000000);
uniform_int_distribution<int> ud2(1, N);

int main(){
    StarBurstStream

    int q, s;
    cin >> n >> s >> q >> esc;
    //n = N;
    //s = 1;
    //q = N;
    //esc = ud2(rnd);
    init();

    for(int i = 1; i < n; i++){
        int u, v, w;
        cin >> u >> v >> w;
        //u = i; v = i + 1;
        //w = ud(rnd);

        g[u].eb(mp(v, w));
        g[v].eb(mp(u, w));
        e[i] = mp(u, v);
        //cerr << u << " " << v << " " << w << "\n";
    }

    for(int i = 0; i < s; i++){
        int c;
        cin >> c;
        //c = ud2(rnd);
        shop[c] = true;
        //cerr << "shop " << c << "\n";
    }

    solve(1, 0);

    /*cerr << "pr\n";
    for(int i = 0; i < SZ; i++){
        printv(pr[i], cerr);
    }
    cerr << "in\n";
    for(int i = 0; i < SZ; i++){
        printv(in[i], cerr);
    }
    cerr << "out\n";
    for(int i = 0; i < SZ; i++){
        printv(out[i], cerr);
    }*/
    
    for(int i = 0; i < q; i++){
        int eid, v;
        cin >> eid >> v;
        //eid = ud2(rnd); if(eid == n) eid--;
        //v = ud2(rnd);
        int u1 = e[eid].F, u2 = e[eid].S;
        //cerr << eid << " " << v << "\n";

        //oao = MAX;
        //dfsbf(v, v, u1, u2, 0);

        query(u1, u2, v);
    }

    return 0;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
27.0 / 27.0

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

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 281 ms 110384 KB Output is correct
2 Correct 485 ms 113788 KB Output is correct
3 Correct 586 ms 113780 KB Output is correct
4 Correct 766 ms 115636 KB Output is correct
5 Correct 674 ms 116032 KB Output is correct
6 Correct 984 ms 118312 KB Output is correct

Subtask #4
41.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 460 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 4 ms 460 KB Output is correct
4 Correct 3 ms 460 KB Output is correct
5 Correct 2 ms 1356 KB Output is correct
6 Correct 3 ms 1356 KB Output is correct
7 Correct 2 ms 1356 KB Output is correct
8 Correct 2 ms 1396 KB Output is correct
9 Correct 2 ms 1356 KB Output is correct
10 Correct 2 ms 1356 KB Output is correct
11 Correct 2 ms 1356 KB Output is correct
12 Correct 2 ms 1356 KB Output is correct
13 Correct 3 ms 1356 KB Output is correct
14 Correct 2 ms 1356 KB Output is correct
15 Correct 281 ms 110384 KB Output is correct
16 Correct 485 ms 113788 KB Output is correct
17 Correct 586 ms 113780 KB Output is correct
18 Correct 766 ms 115636 KB Output is correct
19 Correct 674 ms 116032 KB Output is correct
20 Correct 984 ms 118312 KB Output is correct
21 Correct 231 ms 113628 KB Output is correct
22 Correct 394 ms 113260 KB Output is correct
23 Correct 436 ms 113192 KB Output is correct
24 Correct 517 ms 115124 KB Output is correct
25 Correct 562 ms 117432 KB Output is correct
26 Correct 299 ms 113560 KB Output is correct
27 Correct 349 ms 113212 KB Output is correct
28 Correct 485 ms 113396 KB Output is correct
29 Correct 578 ms 115444 KB Output is correct
30 Correct 674 ms 117488 KB Output is correct
31 Correct 251 ms 113780 KB Output is correct
32 Correct 360 ms 113432 KB Output is correct
33 Correct 495 ms 113424 KB Output is correct
34 Correct 691 ms 115340 KB Output is correct
35 Correct 589 ms 117316 KB Output is correct
36 Correct 481 ms 115656 KB Output is correct