oj.uz

Submission #555011

# Submission time Handle Problem Language Result Execution time Memory
555011 2022-04-29T23:17:49 Z Zhora_004 Swapping Cities (APIO20_swap) C++17
100 / 100
 292 ms 13596 KB 
#include "swap.h"
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <string>
#include <sstream>
#include <iomanip>
#include <map>
#include <unordered_map>
#include <stack>
#include <cstdio>
#include <climits>
#include <tuple>
#include <ctime>
#include <cstring>
#include <numeric>
#include <functional>
#include <chrono>
#include <cassert>
#include <bitset>
#include <fstream>
#define sz(a) ((int)((a).size()))
// printf("%.10f\n", ans);
using ll = long long;
using namespace std;
const int inf = 1e9;

struct Edge {
	int w, u, v;
};

bool comp(Edge& e1, Edge& e2)
{
	return e1.w < e2.w;
}

int n, m, q, x, y;
vector<int> a, b, c, par, rnk, start, finish, neww, noline;
vector<Edge> edges;

int find_par(int u)
{
	if (u == par[u]) return u;
	return find_par(par[u]);
}

void union_sets(int p1, int p2, int u, int v, int w)
{
    if (rnk[p1] < rnk[p2]) swap(p1, p2);
    par[p2] = p1;
    if (rnk[p1] == rnk[p2]) rnk[p1]++;
    neww[p2] = w;
    if (noline[p1] == noline[p2] && noline[p1] == 2 * inf)
    {
        if (finish[p1] == u && start[p2] == v) finish[p1] = finish[p2];
        else if (finish[p1] == u && finish[p2] == v) finish[p1] = start[p2];
        else if (start[p1] == u && start[p2] == v) start[p1] = finish[p2];
        else if (start[p1] == u && finish[p2] == v) start[p1] = start[p2];

        else if (finish[p1] == v && start[p2] == u) finish[p1] = finish[p2];
        else if (finish[p1] == v && finish[p2] == u) finish[p1] = start[p2];
        else if (start[p1] == v && start[p2] == u) start[p1] = finish[p2];
        else if (start[p1] == v && finish[p2] == u) start[p1] = start[p2];
        else
        {
            start[p1] = finish[p1] = -1;
            noline[p1] = w;
        }
    }
    else
    {
        start[p1] = finish[p1] = -1;
        noline[p1] = min(noline[p1], w);
    }
}

void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
	n = N;
	m = M;
	a = U;
	b = V;
	c = W;
    for (int i = 0; i < m; i++) edges.push_back({ c[i], a[i], b[i] });
    sort(edges.begin(), edges.end(), comp);
    par = rnk = start = finish = neww = vector<int>(n);
    noline = vector<int>(n, 2 * inf);
    iota(par.begin(), par.end(), 0);
    iota(start.begin(), start.end(), 0);
    iota(finish.begin(), finish.end(), 0);
    for (int i = 0; i < m; i++)
    {
        int w = edges[i].w, u = edges[i].u, v = edges[i].v;
        int p1 = find_par(u), p2 = find_par(v);
        if (p1 == p2)
        {
            start[p1] = finish[p1] = -1;
            noline[p1] = min(noline[p1], w);
        }
        else union_sets(p1, p2, u, v, w);
    }
}

int find_par1(int u, int& mid)
{
    if (u == par[u] || neww[u] > mid) return u;
    return find_par1(par[u], mid);
}

bool ok(int mid, int u, int v)
{
    int p1 = find_par1(u, mid), p2 = find_par1(v, mid);
    if (p1 != p2 || noline[p1] > mid) return 0;
    return 1;
}

int getMinimumFuelCapacity(int X, int Y) {
	x = X;
	y = Y;
    int l = 0, r = inf + 1;
    while (l + 1 < r)
    {
        int mid = (l + r) >> 1;
        if (ok(mid, x, y)) r = mid;
        else l = mid;
    }
    if (r == inf + 1) r = -1;
    return r;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 39 ms 5780 KB Output is correct
10 Correct 47 ms 7056 KB Output is correct
11 Correct 43 ms 6984 KB Output is correct
12 Correct 47 ms 7228 KB Output is correct
13 Correct 46 ms 7220 KB Output is correct
14 Correct 53 ms 5944 KB Output is correct
15 Correct 231 ms 8872 KB Output is correct
16 Correct 217 ms 8668 KB Output is correct
17 Correct 235 ms 9004 KB Output is correct
18 Correct 141 ms 9052 KB Output is correct
19 Correct 141 ms 4832 KB Output is correct
20 Correct 222 ms 10060 KB Output is correct
21 Correct 244 ms 10088 KB Output is correct
22 Correct 253 ms 10516 KB Output is correct
23 Correct 169 ms 10448 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 157 ms 9896 KB Output is correct
4 Correct 148 ms 10152 KB Output is correct
5 Correct 154 ms 10304 KB Output is correct
6 Correct 150 ms 10084 KB Output is correct
7 Correct 157 ms 10268 KB Output is correct
8 Correct 147 ms 9968 KB Output is correct
9 Correct 145 ms 10084 KB Output is correct
10 Correct 144 ms 9980 KB Output is correct

Subtask #3
17.0 / 17.0

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

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 39 ms 5780 KB Output is correct
11 Correct 47 ms 7056 KB Output is correct
12 Correct 43 ms 6984 KB Output is correct
13 Correct 47 ms 7228 KB Output is correct
14 Correct 46 ms 7220 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 6 ms 1172 KB Output is correct
35 Correct 45 ms 7236 KB Output is correct
36 Correct 49 ms 7224 KB Output is correct
37 Correct 48 ms 7324 KB Output is correct
38 Correct 49 ms 7260 KB Output is correct
39 Correct 46 ms 7208 KB Output is correct
40 Correct 41 ms 6596 KB Output is correct
41 Correct 48 ms 7232 KB Output is correct
42 Correct 44 ms 7304 KB Output is correct
43 Correct 45 ms 7312 KB Output is correct
44 Correct 49 ms 7232 KB Output is correct
45 Correct 70 ms 9012 KB Output is correct
46 Correct 45 ms 7232 KB Output is correct
47 Correct 47 ms 7232 KB Output is correct
48 Correct 49 ms 7700 KB Output is correct
49 Correct 65 ms 9060 KB Output is correct
50 Correct 50 ms 6216 KB Output is correct
51 Correct 61 ms 7820 KB Output is correct
52 Correct 78 ms 10120 KB Output is correct
53 Correct 86 ms 10948 KB Output is correct
54 Correct 98 ms 11972 KB Output is correct
55 Correct 44 ms 7308 KB Output is correct
56 Correct 81 ms 10624 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 39 ms 5780 KB Output is correct
10 Correct 47 ms 7056 KB Output is correct
11 Correct 43 ms 6984 KB Output is correct
12 Correct 47 ms 7228 KB Output is correct
13 Correct 46 ms 7220 KB Output is correct
14 Correct 53 ms 5944 KB Output is correct
15 Correct 231 ms 8872 KB Output is correct
16 Correct 217 ms 8668 KB Output is correct
17 Correct 235 ms 9004 KB Output is correct
18 Correct 141 ms 9052 KB Output is correct
19 Correct 157 ms 9896 KB Output is correct
20 Correct 148 ms 10152 KB Output is correct
21 Correct 154 ms 10304 KB Output is correct
22 Correct 150 ms 10084 KB Output is correct
23 Correct 157 ms 10268 KB Output is correct
24 Correct 147 ms 9968 KB Output is correct
25 Correct 145 ms 10084 KB Output is correct
26 Correct 144 ms 9980 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 340 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 6 ms 1172 KB Output is correct
37 Correct 45 ms 7236 KB Output is correct
38 Correct 49 ms 7224 KB Output is correct
39 Correct 48 ms 7324 KB Output is correct
40 Correct 49 ms 7260 KB Output is correct
41 Correct 46 ms 7208 KB Output is correct
42 Correct 41 ms 6596 KB Output is correct
43 Correct 48 ms 7232 KB Output is correct
44 Correct 44 ms 7304 KB Output is correct
45 Correct 45 ms 7312 KB Output is correct
46 Correct 49 ms 7232 KB Output is correct
47 Correct 23 ms 1468 KB Output is correct
48 Correct 241 ms 9916 KB Output is correct
49 Correct 248 ms 9912 KB Output is correct
50 Correct 224 ms 9896 KB Output is correct
51 Correct 247 ms 9784 KB Output is correct
52 Correct 214 ms 9508 KB Output is correct
53 Correct 213 ms 8548 KB Output is correct
54 Correct 241 ms 10536 KB Output is correct
55 Correct 247 ms 9912 KB Output is correct
56 Correct 156 ms 9880 KB Output is correct
57 Correct 224 ms 10532 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 39 ms 5780 KB Output is correct
11 Correct 47 ms 7056 KB Output is correct
12 Correct 43 ms 6984 KB Output is correct
13 Correct 47 ms 7228 KB Output is correct
14 Correct 46 ms 7220 KB Output is correct
15 Correct 53 ms 5944 KB Output is correct
16 Correct 231 ms 8872 KB Output is correct
17 Correct 217 ms 8668 KB Output is correct
18 Correct 235 ms 9004 KB Output is correct
19 Correct 141 ms 9052 KB Output is correct
20 Correct 157 ms 9896 KB Output is correct
21 Correct 148 ms 10152 KB Output is correct
22 Correct 154 ms 10304 KB Output is correct
23 Correct 150 ms 10084 KB Output is correct
24 Correct 157 ms 10268 KB Output is correct
25 Correct 147 ms 9968 KB Output is correct
26 Correct 145 ms 10084 KB Output is correct
27 Correct 144 ms 9980 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 340 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 6 ms 1172 KB Output is correct
38 Correct 45 ms 7236 KB Output is correct
39 Correct 49 ms 7224 KB Output is correct
40 Correct 48 ms 7324 KB Output is correct
41 Correct 49 ms 7260 KB Output is correct
42 Correct 46 ms 7208 KB Output is correct
43 Correct 41 ms 6596 KB Output is correct
44 Correct 48 ms 7232 KB Output is correct
45 Correct 44 ms 7304 KB Output is correct
46 Correct 45 ms 7312 KB Output is correct
47 Correct 49 ms 7232 KB Output is correct
48 Correct 23 ms 1468 KB Output is correct
49 Correct 241 ms 9916 KB Output is correct
50 Correct 248 ms 9912 KB Output is correct
51 Correct 224 ms 9896 KB Output is correct
52 Correct 247 ms 9784 KB Output is correct
53 Correct 214 ms 9508 KB Output is correct
54 Correct 213 ms 8548 KB Output is correct
55 Correct 241 ms 10536 KB Output is correct
56 Correct 247 ms 9912 KB Output is correct
57 Correct 156 ms 9880 KB Output is correct
58 Correct 224 ms 10532 KB Output is correct
59 Correct 141 ms 4832 KB Output is correct
60 Correct 222 ms 10060 KB Output is correct
61 Correct 244 ms 10088 KB Output is correct
62 Correct 253 ms 10516 KB Output is correct
63 Correct 169 ms 10448 KB Output is correct
64 Correct 1 ms 340 KB Output is correct
65 Correct 1 ms 340 KB Output is correct
66 Correct 1 ms 340 KB Output is correct
67 Correct 1 ms 340 KB Output is correct
68 Correct 1 ms 340 KB Output is correct
69 Correct 1 ms 340 KB Output is correct
70 Correct 1 ms 340 KB Output is correct
71 Correct 1 ms 340 KB Output is correct
72 Correct 1 ms 340 KB Output is correct
73 Correct 1 ms 340 KB Output is correct
74 Correct 70 ms 9012 KB Output is correct
75 Correct 45 ms 7232 KB Output is correct
76 Correct 47 ms 7232 KB Output is correct
77 Correct 49 ms 7700 KB Output is correct
78 Correct 65 ms 9060 KB Output is correct
79 Correct 50 ms 6216 KB Output is correct
80 Correct 61 ms 7820 KB Output is correct
81 Correct 78 ms 10120 KB Output is correct
82 Correct 86 ms 10948 KB Output is correct
83 Correct 98 ms 11972 KB Output is correct
84 Correct 44 ms 7308 KB Output is correct
85 Correct 81 ms 10624 KB Output is correct
86 Correct 60 ms 3832 KB Output is correct
87 Correct 221 ms 9932 KB Output is correct
88 Correct 223 ms 9924 KB Output is correct
89 Correct 181 ms 9892 KB Output is correct
90 Correct 200 ms 10844 KB Output is correct
91 Correct 194 ms 10236 KB Output is correct
92 Correct 199 ms 10532 KB Output is correct
93 Correct 253 ms 12568 KB Output is correct
94 Correct 232 ms 13200 KB Output is correct
95 Correct 292 ms 13596 KB Output is correct
96 Correct 149 ms 10012 KB Output is correct
97 Correct 215 ms 11760 KB Output is correct