oj.uz

Submission #397839

# Submission time Handle Problem Language Result Execution time Memory
397839 2021-05-03T08:45:58 Z yuto1115 Swapping Cities (APIO20_swap) C++17
50 / 100
 2000 ms 17856 KB 
#include "swap.h"
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
#define rep2(i, s, n) for(ll i = ll(s); i < ll(n); i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define pb push_back
#define eb emplace_back
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
using vb = vector<bool>;
using vvb = vector<vb>;

template<class T>
bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

const int inf = 1001001001;

class unionfind {
    int n;
    vi par, rank;
public:
    unionfind(int n) : n(n), par(n, -1), rank(n, 0) {}
    
    int root(int x) {
        if (par[x] < 0) return x;
        return par[x] = root(par[x]);
    }
    
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x), y = root(y);
        if (x == y) return false;
        if (rank[x] < rank[y]) swap(x, y);
        if (rank[x] == rank[y]) rank[x]++;
        par[x] += par[y];
        par[y] = x;
        return true;
    }
};

namespace {
    int n;
    int m;
    vvp G;
    vi deg;
    int mx_w;
    int mx_deg;
    bool cycle;
}

void init(int _n, int _m, vi u, vi v, vi w) {
    n = _n;
    m = _m;
    G.resize(n);
    deg.resize(n);
    mx_w = 0;
    rep(i, m) {
        G[u[i]].eb(v[i], w[i]);
        G[v[i]].eb(u[i], w[i]);
        deg[u[i]]++;
        deg[v[i]]++;
        chmax(mx_w, w[i]);
    }
    cycle = all_of(all(deg), [](int i) { return i == 2; });
    mx_deg = *max_element(all(deg));
    sort(all(G[0]), [](P a, P b) { return a.second < b.second; });
}

// subtask 2
int getMinimumFuelCapacity(int x, int y) {
    // subtask 1
    if (mx_deg <= 2) {
        return (cycle ? mx_w : -1);
    }
    // subtask 2
    if (m <= n - 1 and deg[0] == m) {
        if (n <= 3) return -1;
        if (x == 0) {
            int ans = G[y][0].second;
            int cnt = 0;
            for (auto[v, w] : G[0]) {
                if (v == y) continue;
                chmax(ans, w);
                cnt++;
                if (cnt == 2) break;
            }
            return ans;
        } else {
            int ans = max(G[x][0].second, G[y][0].second);
            for (auto[v, w] : G[0]) {
                if (v == x or v == y) continue;
                chmax(ans, w);
                break;
            }
            return ans;
        }
    }
    // subtask 3,4
    {
        int ok = inf, ng = 0;
        auto f = [&](int l) -> bool {
            unionfind uf(n);
            vi d(n);
            rep(i, n) for (auto[j, w] : G[i]) {
                    if (i > j) continue;
                    if (w > l) continue;
                    uf.merge(i, j);
                    d[i]++;
                    d[j]++;
                }
            if (!uf.same(x, y)) return false;
            bool res = true;
            rep(i, n) {
                if (!uf.same(i, x)) continue;
                if (d[i] > 2) return true;
                if (d[i] == 1) res = false;
            }
            return res;
        };
        if (!f(ok)) return -1;
        while (ok - ng > 1) {
            int mid = (ok + ng) / 2;
            (f(mid) ? ok : ng) = mid;
        }
        return ok;
    }
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 45 ms 7104 KB Output is correct
10 Correct 54 ms 8516 KB Output is correct
11 Correct 58 ms 8436 KB Output is correct
12 Correct 59 ms 8892 KB Output is correct
13 Correct 58 ms 8780 KB Output is correct
14 Correct 49 ms 7232 KB Output is correct
15 Correct 125 ms 10320 KB Output is correct
16 Correct 122 ms 10224 KB Output is correct
17 Correct 129 ms 10652 KB Output is correct
18 Correct 123 ms 10668 KB Output is correct
19 Correct 64 ms 5328 KB Output is correct
20 Correct 124 ms 11472 KB Output is correct
21 Correct 128 ms 11556 KB Output is correct
22 Correct 137 ms 12096 KB Output is correct
23 Correct 167 ms 12028 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 128 ms 11920 KB Output is correct
4 Correct 137 ms 12320 KB Output is correct
5 Correct 139 ms 12212 KB Output is correct
6 Correct 137 ms 12148 KB Output is correct
7 Correct 157 ms 12344 KB Output is correct
8 Correct 130 ms 11880 KB Output is correct
9 Correct 138 ms 12064 KB Output is correct
10 Correct 130 ms 14188 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 4 ms 332 KB Output is correct
11 Correct 5 ms 332 KB Output is correct
12 Correct 4 ms 332 KB Output is correct
13 Correct 5 ms 332 KB Output is correct
14 Correct 4 ms 332 KB Output is correct
15 Correct 6 ms 392 KB Output is correct
16 Correct 4 ms 332 KB Output is correct
17 Correct 4 ms 332 KB Output is correct
18 Correct 4 ms 308 KB Output is correct
19 Correct 4 ms 332 KB Output is correct
20 Correct 4 ms 460 KB Output is correct
21 Correct 5 ms 332 KB Output is correct
22 Correct 4 ms 332 KB Output is correct
23 Correct 3 ms 332 KB Output is correct
24 Correct 8 ms 332 KB Output is correct
25 Correct 7 ms 460 KB Output is correct
26 Correct 9 ms 460 KB Output is correct
27 Correct 6 ms 332 KB Output is correct
28 Correct 7 ms 460 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 45 ms 7104 KB Output is correct
11 Correct 54 ms 8516 KB Output is correct
12 Correct 58 ms 8436 KB Output is correct
13 Correct 59 ms 8892 KB Output is correct
14 Correct 58 ms 8780 KB Output is correct
15 Correct 4 ms 332 KB Output is correct
16 Correct 5 ms 332 KB Output is correct
17 Correct 4 ms 332 KB Output is correct
18 Correct 5 ms 332 KB Output is correct
19 Correct 4 ms 332 KB Output is correct
20 Correct 6 ms 392 KB Output is correct
21 Correct 4 ms 332 KB Output is correct
22 Correct 4 ms 332 KB Output is correct
23 Correct 4 ms 308 KB Output is correct
24 Correct 4 ms 332 KB Output is correct
25 Correct 4 ms 460 KB Output is correct
26 Correct 5 ms 332 KB Output is correct
27 Correct 4 ms 332 KB Output is correct
28 Correct 3 ms 332 KB Output is correct
29 Correct 8 ms 332 KB Output is correct
30 Correct 7 ms 460 KB Output is correct
31 Correct 9 ms 460 KB Output is correct
32 Correct 6 ms 332 KB Output is correct
33 Correct 7 ms 460 KB Output is correct
34 Correct 24 ms 1716 KB Output is correct
35 Correct 947 ms 10528 KB Output is correct
36 Correct 896 ms 10440 KB Output is correct
37 Correct 935 ms 10376 KB Output is correct
38 Correct 900 ms 10452 KB Output is correct
39 Correct 865 ms 10196 KB Output is correct
40 Correct 813 ms 9672 KB Output is correct
41 Correct 988 ms 11028 KB Output is correct
42 Correct 928 ms 10332 KB Output is correct
43 Correct 775 ms 10380 KB Output is correct
44 Correct 1151 ms 11384 KB Output is correct
45 Correct 1141 ms 13636 KB Output is correct
46 Correct 1032 ms 10504 KB Output is correct
47 Correct 921 ms 10592 KB Output is correct
48 Correct 1032 ms 11096 KB Output is correct
49 Correct 175 ms 11716 KB Output is correct
50 Correct 196 ms 8996 KB Output is correct
51 Correct 777 ms 11844 KB Output is correct
52 Correct 1619 ms 15432 KB Output is correct
53 Correct 1403 ms 16580 KB Output is correct
54 Correct 1785 ms 17856 KB Output is correct
55 Correct 876 ms 10520 KB Output is correct
56 Correct 1608 ms 16124 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 45 ms 7104 KB Output is correct
10 Correct 54 ms 8516 KB Output is correct
11 Correct 58 ms 8436 KB Output is correct
12 Correct 59 ms 8892 KB Output is correct
13 Correct 58 ms 8780 KB Output is correct
14 Correct 49 ms 7232 KB Output is correct
15 Correct 125 ms 10320 KB Output is correct
16 Correct 122 ms 10224 KB Output is correct
17 Correct 129 ms 10652 KB Output is correct
18 Correct 123 ms 10668 KB Output is correct
19 Correct 128 ms 11920 KB Output is correct
20 Correct 137 ms 12320 KB Output is correct
21 Correct 139 ms 12212 KB Output is correct
22 Correct 137 ms 12148 KB Output is correct
23 Correct 157 ms 12344 KB Output is correct
24 Correct 130 ms 11880 KB Output is correct
25 Correct 138 ms 12064 KB Output is correct
26 Correct 130 ms 14188 KB Output is correct
27 Correct 4 ms 332 KB Output is correct
28 Correct 5 ms 332 KB Output is correct
29 Correct 4 ms 332 KB Output is correct
30 Correct 5 ms 332 KB Output is correct
31 Correct 4 ms 332 KB Output is correct
32 Correct 6 ms 392 KB Output is correct
33 Correct 4 ms 332 KB Output is correct
34 Correct 4 ms 332 KB Output is correct
35 Correct 4 ms 308 KB Output is correct
36 Correct 24 ms 1716 KB Output is correct
37 Correct 947 ms 10528 KB Output is correct
38 Correct 896 ms 10440 KB Output is correct
39 Correct 935 ms 10376 KB Output is correct
40 Correct 900 ms 10452 KB Output is correct
41 Correct 865 ms 10196 KB Output is correct
42 Correct 813 ms 9672 KB Output is correct
43 Correct 988 ms 11028 KB Output is correct
44 Correct 928 ms 10332 KB Output is correct
45 Correct 775 ms 10380 KB Output is correct
46 Correct 1151 ms 11384 KB Output is correct
47 Execution timed out 2082 ms 1996 KB Time limit exceeded
48 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 45 ms 7104 KB Output is correct
11 Correct 54 ms 8516 KB Output is correct
12 Correct 58 ms 8436 KB Output is correct
13 Correct 59 ms 8892 KB Output is correct
14 Correct 58 ms 8780 KB Output is correct
15 Correct 49 ms 7232 KB Output is correct
16 Correct 125 ms 10320 KB Output is correct
17 Correct 122 ms 10224 KB Output is correct
18 Correct 129 ms 10652 KB Output is correct
19 Correct 123 ms 10668 KB Output is correct
20 Correct 128 ms 11920 KB Output is correct
21 Correct 137 ms 12320 KB Output is correct
22 Correct 139 ms 12212 KB Output is correct
23 Correct 137 ms 12148 KB Output is correct
24 Correct 157 ms 12344 KB Output is correct
25 Correct 130 ms 11880 KB Output is correct
26 Correct 138 ms 12064 KB Output is correct
27 Correct 130 ms 14188 KB Output is correct
28 Correct 4 ms 332 KB Output is correct
29 Correct 5 ms 332 KB Output is correct
30 Correct 4 ms 332 KB Output is correct
31 Correct 5 ms 332 KB Output is correct
32 Correct 4 ms 332 KB Output is correct
33 Correct 6 ms 392 KB Output is correct
34 Correct 4 ms 332 KB Output is correct
35 Correct 4 ms 332 KB Output is correct
36 Correct 4 ms 308 KB Output is correct
37 Correct 24 ms 1716 KB Output is correct
38 Correct 947 ms 10528 KB Output is correct
39 Correct 896 ms 10440 KB Output is correct
40 Correct 935 ms 10376 KB Output is correct
41 Correct 900 ms 10452 KB Output is correct
42 Correct 865 ms 10196 KB Output is correct
43 Correct 813 ms 9672 KB Output is correct
44 Correct 988 ms 11028 KB Output is correct
45 Correct 928 ms 10332 KB Output is correct
46 Correct 775 ms 10380 KB Output is correct
47 Correct 1151 ms 11384 KB Output is correct
48 Execution timed out 2082 ms 1996 KB Time limit exceeded
49 Halted 0 ms 0 KB -