oj.uz

Submission #951163

# Submission time Handle Problem Language Result Execution time Memory
951163 2024-03-21T09:32:17 Z LOLOLO Evacuation plan (IZhO18_plan) C++17
22 / 100
 4000 ms 65988 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())

const int N = 1e5 + 100;
vector <pair <int, int>> ed[N];
int f[N], used[N], sz[N], p[N], cnt[N], ans[N];
vector <pair <int, int>> edge;
vector < vector <int>> save;
stack <pair <int, int>> st;

int get(int a) {
    return p[a] ? get(p[a]) : a;
}

void unite(int a, int b) {
    a = get(a), b = get(b);
    if (a == b)
        return;

    if (sz[a] < sz[b])
        swap(a, b);

    st.push({a, b});
    sz[a] += sz[b];
    p[b] = a;
} 

bool same(int a, int b) {
    return get(a) == get(b);
}

void rollback(int tt) {
    while (sz(st) > tt) {
        pair <int, int> t = st.top();
        st.pop();
        sz[t.f] -= sz[t.s];
        p[t.s] = 0;
    }
}

int cur = -1;
void move(int l) {
    while (cur < l) {
        cur++;
        unite(save[cur][1], save[cur][2]);
        cnt[cur] = sz(st);
    }

    while (cur > l) {
        cur = l;
        rollback(cnt[l]);
    }
}

void bin(int l, int r, vector < vector <int>> &ask) {
    if (l > r || ask.empty())
        return;

    int m = (l + r)  / 2;
    move(m);
    vector < vector <int>> win, lose;
    for (auto x : ask) {
        if (same(x[0], x[1])) {
            ans[x[2]] = save[m][0];
            win.pb(x);
        } else {
            lose.pb(x);
        }
    }

    ask.clear();
    bin(l, m - 1, win);
    bin(m + 1, r, lose);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    mem(f, 0x3f);

    int n, m;
    cin >> n >> m;

    fill(sz + 1, sz + 1 + n, 1);

    for (int i = 1; i <= m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        ed[a].pb({b, w});
        ed[b].pb({a, w});
        edge.pb({a, b});
    }

    priority_queue <pair <int, int>, vector <pair <int, int>>, greater <pair <int, int>>> pq;

    int k;
    cin >> k;

    for (int i = 0; i < k; i++) {
        int x;
        cin >> x;
        f[x] = 0;
        pq.push({0, x});
    }

    while (sz(pq)) {
        auto t = pq.top();
        pq.pop();
        if (f[t.s] < t.f)
            continue;

        for (auto x : ed[t.s]) {
            if (f[x.f] > x.s + t.f) {
                f[x.f] = x.s + t.f;
                pq.push({f[x.f], x.f});
            }
        }
    }

    for (auto x : edge) {
        save.pb({min(f[x.f], f[x.s]), x.f, x.s});
    }

    sort(all(save), greater < vector <int>>());
    
    int q;
    cin >> q;

    vector < vector <int>> ask;
    for (int i = 0; i < q; i++) {
        int s, t;
        cin >> s >> t;
        ask.pb({s, t, i});
    }

    bin(0, m - 1, ask);
    for (int i = 0; i < q; i++)
        cout << ans[i] << '\n';

    return 0;
}
/*
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
5
1 6
5 3
4 8
5 8
1 5
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4952 KB Output is correct
2 Correct 3 ms 5212 KB Output is correct
3 Correct 3 ms 5156 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 3 ms 5212 KB Output is correct
6 Correct 3 ms 5212 KB Output is correct
7 Correct 1 ms 4956 KB Output is correct
8 Correct 1 ms 4956 KB Output is correct
9 Correct 3 ms 5212 KB Output is correct
10 Correct 3 ms 5208 KB Output is correct
11 Correct 3 ms 5208 KB Output is correct
12 Correct 2 ms 5208 KB Output is correct
13 Correct 3 ms 5212 KB Output is correct
14 Correct 3 ms 5212 KB Output is correct
15 Correct 3 ms 5212 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4952 KB Output is correct
2 Correct 3 ms 5212 KB Output is correct
3 Correct 3 ms 5156 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 3 ms 5212 KB Output is correct
6 Correct 3 ms 5212 KB Output is correct
7 Correct 1 ms 4956 KB Output is correct
8 Correct 1 ms 4956 KB Output is correct
9 Correct 3 ms 5212 KB Output is correct
10 Correct 3 ms 5208 KB Output is correct
11 Correct 3 ms 5208 KB Output is correct
12 Correct 2 ms 5208 KB Output is correct
13 Correct 3 ms 5212 KB Output is correct
14 Correct 3 ms 5212 KB Output is correct
15 Correct 3 ms 5212 KB Output is correct
16 Correct 261 ms 31936 KB Output is correct
17 Execution timed out 4059 ms 65988 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 2 ms 5244 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 1 ms 4956 KB Output is correct
7 Correct 1 ms 4988 KB Output is correct
8 Correct 1 ms 4956 KB Output is correct
9 Correct 1 ms 4956 KB Output is correct
10 Correct 2 ms 4956 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 28532 KB Output is correct
2 Execution timed out 4059 ms 58488 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4952 KB Output is correct
2 Correct 3 ms 5212 KB Output is correct
3 Correct 3 ms 5156 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 3 ms 5212 KB Output is correct
6 Correct 3 ms 5212 KB Output is correct
7 Correct 1 ms 4956 KB Output is correct
8 Correct 1 ms 4956 KB Output is correct
9 Correct 3 ms 5212 KB Output is correct
10 Correct 3 ms 5208 KB Output is correct
11 Correct 3 ms 5208 KB Output is correct
12 Correct 2 ms 5208 KB Output is correct
13 Correct 3 ms 5212 KB Output is correct
14 Correct 3 ms 5212 KB Output is correct
15 Correct 3 ms 5212 KB Output is correct
16 Correct 261 ms 31936 KB Output is correct
17 Execution timed out 4059 ms 65988 KB Time limit exceeded
18 Halted 0 ms 0 KB -