oj.uz

Submission #892075

# Submission time Handle Problem Language Result Execution time Memory
892075 2023-12-24T18:32:00 Z kh0i Evacuation plan (IZhO18_plan) C++17
100 / 100
 370 ms 146680 KB 
#include "bits/stdc++.h"
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif

using ll = long long;
using pii = pair<int, int>;

#define F first
#define S second
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll get_rand(ll l, ll r) {
    assert(l <= r);
    return uniform_int_distribution<ll> (l, r)(rng);
}

const int N = 1e5 + 3;

int n, m, k, q;
int p[N];
ll dist[N];
vector<pair<int, ll>> g[N];

struct DSU_Rollback{
    struct Data{
        int u, sz_u, v, sz_v;
    };
 
    int n;
    vector<int> p, sz;
    vector<Data> op;
    int comps;
 
    void init(int _n){
        n = _n;
        p.clear();
        sz.clear();
        p.resize(n + 2, 0);
        sz.resize(n + 2, 1);
        comps = n;
        iota(all(p), 0);
    }
 
    // no path compression
    int find_set(int u){
        return u == p[u] ? u : find_set(p[u]);
    }
 
    bool join_sets(int u, int v){
        u = find_set(u);
        v = find_set(v);
        if(u == v)
            return 0;
        --comps;
        if(sz[u] < sz[v])
            swap(u, v);
        op.push_back({u, sz[u], v, sz[v]});
        p[v] = u;
        sz[u] += sz[v];
        return 1;
    }

    bool same_set(int u, int v){
        return find_set(u) == find_set(v);
    }
 
    void rollback(){
        if(op.empty())
            return;
        Data &x = op.back();
        p[x.u] = x.u;
        p[x.v] = x.v;
        sz[x.u] = x.sz_u;
        sz[x.v] = x.sz_v;
        ++comps;
        op.pop_back();
    }
};

namespace Sub12{
    bool valid_input(){
        return (n <= 20 and m <= 200 and q <= 200) or q == 1;
    }

    void dijkstra(){
        priority_queue<pair<ll, int>> pq;
        memset(dist, 0x3f3f3f3f, sizeof(dist));
        for(int i = 1; i <= k; ++i){
            dist[p[i]] = 0;
            pq.push({-dist[p[i]], p[i]});
        }

        while(!pq.empty()){
            int u = pq.top().S;
            pq.pop();

            for(auto [v, w] : g[u]){
                if(dist[v] > dist[u] + w){
                    dist[v] = dist[u] + w;
                    pq.push({-dist[v], v});
                }
            }
        }
    }

    void solve(){
        dijkstra();
        for(int i = 1; i <= n; ++i)
            debug(i, dist[i]);
        DSU_Rollback dsu;

        while(q--){
            int s, t;
            cin >> s >> t;

            ll l = 0, r = 1e14, res = 1e14;
            while(l <= r){
                ll mid = (l + r) / 2;
                dsu.init(n);

                for(int i = 1; i <= n; ++i)
                    if(dist[i] >= mid)
                        for(auto [v, w] : g[i])
                            if(dist[v] >= mid)
                                dsu.join_sets(i, v);

                if(dsu.same_set(s, t)){
                    res = mid;
                    l = mid + 1;
                }
                else
                    r = mid - 1;
            }
            cout << res << '\n';
        }
    }
}

struct Edge{
    int u, v;
    ll mn;
};

struct Query{
    int s, t, id;
};

vector<Query> d;
vector<Edge> e;
map<int, int> mp[N];

namespace Sub3{
    DSU_Rollback dsu;
    vector<ll> dif_dist;
    ll ans[N];

    void calc(int l, int r, vector<Edge> &e, vector<Query> &d){
        if(l + 1 == r or d.empty()){
            for(auto& [s, t, id] : d)
                ans[id] = dif_dist[l];
            return;
        }
        int mid = (l + r) / 2;
        ll mxw = dif_dist[mid];

        vector<Edge> el, er;
        vector<Query> dl, dr;

        int cnt_add = 0;

        for(auto &x : e){
            if(x.mn >= mxw){
                cnt_add += dsu.join_sets(x.u, x.v);
                er.push_back(x);
            }
            else
                el.push_back(x);
        }

        for(auto &x : d){
            if(dsu.same_set(x.s, x.t))
                dr.push_back(x);
            else
                dl.push_back(x);
        }

        calc(l, mid, el, dl);
        while(cnt_add--)
            dsu.rollback();
        calc(mid, r, er, dr);
    }

    void dijkstra(){
        priority_queue<pair<ll, int>> pq;
        memset(dist, 0x3f3f3f3f, sizeof(dist));
        for(int i = 1; i <= k; ++i){
            dist[p[i]] = 0;
            pq.push({-dist[p[i]], p[i]});
        }

        while(!pq.empty()){
            int u = pq.top().S;
            pq.pop();

            for(auto [v, w] : g[u]){
                if(dist[v] > dist[u] + w){
                    dist[v] = dist[u] + w;
                    pq.push({-dist[v], v});
                }
            }
        }
    }

    void solve(){
        dsu.init(n);
        dijkstra();
        for(int i = 1; i <= n; ++i)
            for(auto& [v, w]: g[i])
                if(i > v)
                    e.push_back({i, v, min(dist[i], dist[v])});
        for(int i = 1; i <= q; ++i){
            int s, t;
            cin >> s >> t;
            d.push_back({s, t, i});
        }
        for(int i = 1; i <= n; ++i)
            dif_dist.push_back(dist[i]);
        sort(all(dif_dist));
        dif_dist.resize(unique(all(dif_dist)) - dif_dist.begin());
        calc(0, sz(dif_dist), e, d);
        for(int i = 1; i <= q; ++i)
            cout << ans[i] << '\n';
    }
}

void read_input(){
    cin >> n >> m;
    for(int i = 1; i <= m; ++i){
        int u, v, w;
        cin >> u >> v >> w;
        if(u == v)
            continue;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    
    cin >> k;
    for(int i = 1; i <= k; ++i)
        cin >> p[i];
    cin >> q;
}

void solve(){
    read_input();
    #ifdef LOCAL
        cerr << "\n[Input Time]: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
    #endif
    Sub3::solve();
}

int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(0);
    #define task "troll"
    if(fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    int test = 1;
//    cin >> test;
    for(int i = 1; i <= test; ++i){
//        cout << "Case #" << i << ": ";
        solve();
    }
    #ifdef LOCAL
        cerr << "\n[Time]: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
    #endif
    return 0;
}

Compilation message

plan.cpp: In function 'int32_t main()':
plan.cpp:272:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  272 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:273:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  273 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8792 KB Output is correct
2 Correct 3 ms 9196 KB Output is correct
3 Correct 3 ms 9160 KB Output is correct
4 Correct 2 ms 8792 KB Output is correct
5 Correct 3 ms 9308 KB Output is correct
6 Correct 2 ms 9048 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct
8 Correct 2 ms 8796 KB Output is correct
9 Correct 3 ms 9052 KB Output is correct
10 Correct 2 ms 9052 KB Output is correct
11 Correct 3 ms 9052 KB Output is correct
12 Correct 2 ms 9308 KB Output is correct
13 Correct 3 ms 9052 KB Output is correct
14 Correct 3 ms 9052 KB Output is correct
15 Correct 3 ms 9052 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8792 KB Output is correct
2 Correct 3 ms 9196 KB Output is correct
3 Correct 3 ms 9160 KB Output is correct
4 Correct 2 ms 8792 KB Output is correct
5 Correct 3 ms 9308 KB Output is correct
6 Correct 2 ms 9048 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct
8 Correct 2 ms 8796 KB Output is correct
9 Correct 3 ms 9052 KB Output is correct
10 Correct 2 ms 9052 KB Output is correct
11 Correct 3 ms 9052 KB Output is correct
12 Correct 2 ms 9308 KB Output is correct
13 Correct 3 ms 9052 KB Output is correct
14 Correct 3 ms 9052 KB Output is correct
15 Correct 3 ms 9052 KB Output is correct
16 Correct 118 ms 31712 KB Output is correct
17 Correct 361 ms 99948 KB Output is correct
18 Correct 28 ms 15776 KB Output is correct
19 Correct 85 ms 52920 KB Output is correct
20 Correct 348 ms 95776 KB Output is correct
21 Correct 161 ms 82984 KB Output is correct
22 Correct 143 ms 28992 KB Output is correct
23 Correct 339 ms 97300 KB Output is correct
24 Correct 367 ms 94840 KB Output is correct
25 Correct 363 ms 106544 KB Output is correct
26 Correct 93 ms 52772 KB Output is correct
27 Correct 87 ms 52904 KB Output is correct
28 Correct 88 ms 53924 KB Output is correct
29 Correct 85 ms 52692 KB Output is correct
30 Correct 85 ms 52768 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8792 KB Output is correct
4 Correct 2 ms 8888 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct
8 Correct 2 ms 8796 KB Output is correct
9 Correct 2 ms 8796 KB Output is correct
10 Correct 2 ms 8796 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 37684 KB Output is correct
2 Correct 267 ms 91020 KB Output is correct
3 Correct 283 ms 92024 KB Output is correct
4 Correct 46 ms 24692 KB Output is correct
5 Correct 262 ms 81680 KB Output is correct
6 Correct 286 ms 71520 KB Output is correct
7 Correct 283 ms 85200 KB Output is correct
8 Correct 259 ms 70028 KB Output is correct
9 Correct 265 ms 76560 KB Output is correct
10 Correct 273 ms 87952 KB Output is correct
11 Correct 278 ms 83116 KB Output is correct
12 Correct 282 ms 85060 KB Output is correct
13 Correct 296 ms 86448 KB Output is correct
14 Correct 271 ms 82548 KB Output is correct
15 Correct 280 ms 89312 KB Output is correct
16 Correct 273 ms 87616 KB Output is correct
17 Correct 262 ms 69668 KB Output is correct
18 Correct 269 ms 77348 KB Output is correct
19 Correct 47 ms 22860 KB Output is correct
20 Correct 292 ms 88236 KB Output is correct
21 Correct 251 ms 131064 KB Output is correct
22 Correct 64 ms 39708 KB Output is correct
23 Correct 56 ms 24992 KB Output is correct
24 Correct 61 ms 39708 KB Output is correct
25 Correct 60 ms 39724 KB Output is correct
26 Correct 59 ms 27840 KB Output is correct
27 Correct 47 ms 24004 KB Output is correct
28 Correct 60 ms 39468 KB Output is correct
29 Correct 46 ms 24788 KB Output is correct
30 Correct 61 ms 39712 KB Output is correct
31 Correct 46 ms 24420 KB Output is correct

Subtask #5
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8792 KB Output is correct
2 Correct 3 ms 9196 KB Output is correct
3 Correct 3 ms 9160 KB Output is correct
4 Correct 2 ms 8792 KB Output is correct
5 Correct 3 ms 9308 KB Output is correct
6 Correct 2 ms 9048 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct
8 Correct 2 ms 8796 KB Output is correct
9 Correct 3 ms 9052 KB Output is correct
10 Correct 2 ms 9052 KB Output is correct
11 Correct 3 ms 9052 KB Output is correct
12 Correct 2 ms 9308 KB Output is correct
13 Correct 3 ms 9052 KB Output is correct
14 Correct 3 ms 9052 KB Output is correct
15 Correct 3 ms 9052 KB Output is correct
16 Correct 118 ms 31712 KB Output is correct
17 Correct 361 ms 99948 KB Output is correct
18 Correct 28 ms 15776 KB Output is correct
19 Correct 85 ms 52920 KB Output is correct
20 Correct 348 ms 95776 KB Output is correct
21 Correct 161 ms 82984 KB Output is correct
22 Correct 143 ms 28992 KB Output is correct
23 Correct 339 ms 97300 KB Output is correct
24 Correct 367 ms 94840 KB Output is correct
25 Correct 363 ms 106544 KB Output is correct
26 Correct 93 ms 52772 KB Output is correct
27 Correct 87 ms 52904 KB Output is correct
28 Correct 88 ms 53924 KB Output is correct
29 Correct 85 ms 52692 KB Output is correct
30 Correct 85 ms 52768 KB Output is correct
31 Correct 2 ms 8796 KB Output is correct
32 Correct 2 ms 8796 KB Output is correct
33 Correct 2 ms 8792 KB Output is correct
34 Correct 2 ms 8888 KB Output is correct
35 Correct 2 ms 8796 KB Output is correct
36 Correct 2 ms 8796 KB Output is correct
37 Correct 2 ms 8796 KB Output is correct
38 Correct 2 ms 8796 KB Output is correct
39 Correct 2 ms 8796 KB Output is correct
40 Correct 2 ms 8796 KB Output is correct
41 Correct 112 ms 37684 KB Output is correct
42 Correct 267 ms 91020 KB Output is correct
43 Correct 283 ms 92024 KB Output is correct
44 Correct 46 ms 24692 KB Output is correct
45 Correct 262 ms 81680 KB Output is correct
46 Correct 286 ms 71520 KB Output is correct
47 Correct 283 ms 85200 KB Output is correct
48 Correct 259 ms 70028 KB Output is correct
49 Correct 265 ms 76560 KB Output is correct
50 Correct 273 ms 87952 KB Output is correct
51 Correct 278 ms 83116 KB Output is correct
52 Correct 282 ms 85060 KB Output is correct
53 Correct 296 ms 86448 KB Output is correct
54 Correct 271 ms 82548 KB Output is correct
55 Correct 280 ms 89312 KB Output is correct
56 Correct 273 ms 87616 KB Output is correct
57 Correct 262 ms 69668 KB Output is correct
58 Correct 269 ms 77348 KB Output is correct
59 Correct 47 ms 22860 KB Output is correct
60 Correct 292 ms 88236 KB Output is correct
61 Correct 251 ms 131064 KB Output is correct
62 Correct 64 ms 39708 KB Output is correct
63 Correct 56 ms 24992 KB Output is correct
64 Correct 61 ms 39708 KB Output is correct
65 Correct 60 ms 39724 KB Output is correct
66 Correct 59 ms 27840 KB Output is correct
67 Correct 47 ms 24004 KB Output is correct
68 Correct 60 ms 39468 KB Output is correct
69 Correct 46 ms 24788 KB Output is correct
70 Correct 61 ms 39712 KB Output is correct
71 Correct 46 ms 24420 KB Output is correct
72 Correct 179 ms 49628 KB Output is correct
73 Correct 347 ms 99144 KB Output is correct
74 Correct 344 ms 95884 KB Output is correct
75 Correct 358 ms 98008 KB Output is correct
76 Correct 345 ms 95104 KB Output is correct
77 Correct 341 ms 94340 KB Output is correct
78 Correct 345 ms 94864 KB Output is correct
79 Correct 351 ms 96348 KB Output is correct
80 Correct 340 ms 97380 KB Output is correct
81 Correct 370 ms 97716 KB Output is correct
82 Correct 330 ms 95884 KB Output is correct
83 Correct 337 ms 95412 KB Output is correct
84 Correct 338 ms 96456 KB Output is correct
85 Correct 343 ms 105264 KB Output is correct
86 Correct 357 ms 93236 KB Output is correct
87 Correct 350 ms 94852 KB Output is correct
88 Correct 344 ms 98852 KB Output is correct
89 Correct 171 ms 29580 KB Output is correct
90 Correct 350 ms 95712 KB Output is correct
91 Correct 287 ms 146680 KB Output is correct
92 Correct 91 ms 52952 KB Output is correct
93 Correct 139 ms 32612 KB Output is correct
94 Correct 88 ms 52756 KB Output is correct
95 Correct 85 ms 52760 KB Output is correct
96 Correct 132 ms 44732 KB Output is correct
97 Correct 163 ms 38596 KB Output is correct
98 Correct 88 ms 52664 KB Output is correct
99 Correct 163 ms 38812 KB Output is correct
100 Correct 89 ms 53924 KB Output is correct