oj.uz

답안 #94218

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
94218 2019-01-16T17:51:32 Z 4llower Evacuation plan (IZhO18_plan) C++14
0 / 100
 887 ms 110232 KB 
#include <bits/stdc++.h>

#define rust(a, b, c, d) sqrt(sqr(a - c) + sqr(b - d))
#define sqr(a) (a)*(a)
#define m_p make_pair
#define fi first
#define se second
#define fast_io ios_base::sync_with_stdio(0);cin.tie(0);
#define endl "\n"
#define pll pair <ll,ll>
#define next stopplz
#define y1 STOPPLZ

typedef long long ll;

const int MAXINT=2147483640;
const ll MAXLL=9223372036854775800LL;
const ll MAXN = 1e6;
const double eps = 1e-9;
const ll mod = 1e9 + 7;

using namespace std;
ll dsu[MAXN], tin[MAXN], tout[MAXN], p[100020][22], ans[100200][22], n, m, b[MAXN], stn, v1[MAXN], v2[MAXN];
vector <pll> v[MAXN];
ll get(ll x){
    if (dsu[x] != x) dsu[x] = get(dsu[x]);
    return dsu[x];
}
void dfs(ll x, ll pred){
    p[x][0] = pred;
    ans[x][0] = b[pred];
    tin[x] = ++stn;
    for (int i = 1; i <= 20; ++i) {
            p[x][i] = max(1ll, p[p[x][i - 1]][i - 1]);
            ans[x][i] = min(ans[x][i - 1], ans[p[x][i - 1]][i - 1]);
    }
    for (auto i : v[x]) if (i.fi != pred) dfs(i.fi, x);
    tout[x] = ++stn;
}

bool lower(ll x, ll y){
    if (tin[x] <= tin[y] && tout[y] <= tout[x]) return 1;
    else return 0;
}

ll lca(ll x, ll y){
    if (lower(x, y)) return 1e18;
    ll val = 1e18;
    for (int i = 20; i >= 0; i--) if (!lower(p[x][i], y)) {
            val = min(val, ans[x][i]);
            x = p[x][i];
    }
    val = min(val, ans[p[x][0]][0]);
    return val;
}

int main() {
    srand(time(0));
//    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);
    fast_io;
    cin >> n >> m;
    for (int i = 0; i <= n; ++i) dsu[i] = i, b[i] = 1e18;
    vector <pair <ll, pll> > vans;
    for (int i = 1; i <= m; ++i){
        ll val;
        cin >> v1[i] >> v2[i] >> val;
        v[v1[i]].push_back(m_p(v2[i], val));
        v[v2[i]].push_back(m_p(v1[i], val));
    }

    ll k;
    cin >> k;
    set <pll> s;
    for (int i = 1; i <= k; ++i) {
        ll x;
        cin >> x;
        s.insert(m_p(0, x));
        b[x] = 0;
    }

    while (!s.empty()){
        ll x = s.begin() -> se, val = s.begin() -> fi;
        s.erase(s.begin());
        for (auto i : v[x]) if (val + i.se < b[i.fi]){
            s.erase(m_p(b[i.fi], i.fi));
            b[i.fi] = i.se + val;
            s.insert(m_p(b[i.fi], i.fi));
        }
    }

    for (int i = 1; i <= n; ++i) v[i].clear();
    for (int i = 1; i <= m; ++i) vans.push_back(m_p(min(b[v1[i]], b[v2[i]]), m_p(v1[i], v2[i])));
    sort(vans.begin(), vans.end());
    reverse(vans.begin(), vans.end());
    for (auto i : vans) if (get(i.se.se) != get(i.se.fi)){
        dsu[get(i.se.se)] = get(i.se.fi);
        v[i.se.se].push_back(m_p(i.se.fi, 0));
        v[i.se.fi].push_back(m_p(i.se.se, 0));
    }

    dfs(1, 0);

    ll kek;
    cin >> kek;
    for (int i = 1; i <= kek; ++i){
        ll l, r;
        cin >> l >> r;
        ll mn = lca(l, r);
        mn = min(lca(r, l), mn);
        mn = min(b[l], mn);
        mn = min(b[r], mn);
        cout << mn << endl;
    }

    return 0;
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 23 ms 23928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 23 ms 23928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 24 ms 23928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 424 ms 80284 KB Output is correct
2 Correct 851 ms 110108 KB Output is correct
3 Correct 842 ms 110168 KB Output is correct
4 Correct 244 ms 74420 KB Output is correct
5 Correct 849 ms 110132 KB Output is correct
6 Correct 887 ms 110120 KB Output is correct
7 Correct 881 ms 110156 KB Output is correct
8 Correct 847 ms 110208 KB Output is correct
9 Correct 842 ms 110232 KB Output is correct
10 Correct 844 ms 110144 KB Output is correct
11 Correct 836 ms 109872 KB Output is correct
12 Correct 874 ms 106804 KB Output is correct
13 Correct 863 ms 106720 KB Output is correct
14 Correct 825 ms 106772 KB Output is correct
15 Correct 846 ms 106720 KB Output is correct
16 Correct 866 ms 106772 KB Output is correct
17 Correct 845 ms 106736 KB Output is correct
18 Correct 848 ms 106792 KB Output is correct
19 Incorrect 232 ms 74612 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 23 ms 23928 KB Output isn't correct
2 Halted 0 ms 0 KB -