oj.uz

Submission #571243

# Submission time Handle Problem Language Result Execution time Memory
571243 2022-06-01T15:23:25 Z YouAreMyGalaxy Swapping Cities (APIO20_swap) C++17
100 / 100
 403 ms 44560 KB 
//Make CSP great again
//Vengeance
#include <bits/stdc++.h>
#include <swap.h>
#define TASK "TESTCODE"
#define Log2(x) 31 - __builtin_clz(x)
using namespace std;
const int N = 1e5, M = 2e5, K = N + M, cbit = 18, oo = 1e9 + 1;
int f[K + 1][cbit + 1], id[M + 1];
int n, m;
int lab[K + 1], weight[K + 1], deg[K + 1], depth[K + 1];
bool able[K + 1];
vector<int> adj[K + 1];
int FindSet(int u)
{
    return lab[u] < 0 ? u : lab[u] = FindSet(lab[u]);
}
void unite(int u, int v, int w)
{
    bool ok = deg[u] > 1 | deg[v] > 1;
    ++deg[u];
    ++deg[v];
    u = FindSet(u);
    v = FindSet(v);
    if (u == v)
    {
        if (!able[u])
        {
            able[u] = true;
            weight[u] = w;
        }
        return ;
    }
    ++n;
    able[n] = able[u] | able[v] | ok;
    if (able[n])
    {
        weight[n] = w;
    }
    lab[u] = lab[v] = n;
    adj[n].push_back(u);
    adj[n].push_back(v);
    //cerr << n << ' ' << u << '\n';
    //cerr << n << ' ' << v << '\n';
}
void DFS(int u, int par)
{
    if (par != 0 && !able[u])
    {
        weight[u] = weight[par];
    }
    //cerr << u << ' ' << weight[u] << '\n';
    for (int v : adj[u])
    {
        //cerr << u << ' ' << v << '\n';
        depth[v] = depth[u] + 1;
        f[v][0] = u;
        for (int i = 1; i <= cbit; ++ i)
        {
            f[v][i] = f[f[v][i - 1]][i - 1];
        }
        DFS(v, u);
    }
}
int get(int u, int v)
{
    if (depth[v] < depth[u])
    {
        swap(u, v);
    }
    int k = depth[v] - depth[u];
    for (int i = cbit; i >= 0; -- i)
    {
        if ((k >> i) & 1)
        {
            v = f[v][i];
        }
    }
    if (u == v)
    {
        //cerr << u << '\n';
        return weight[u];
    }
    for (int i = cbit; i >= 0; -- i)
    {
        if (f[u][i] != f[v][i])
        {
            u = f[u][i];
            v = f[v][i];
        }
    }
    //cerr << f[u][0] << '\n';
    return weight[f[u][0]];
}
void init(int _n, int _m, vector<int> u, vector<int> v, vector<int> w)
{
    n = _n;
    m = _m;
    iota(id, id + m, 0);
    memset(lab, -1, sizeof(lab));
    memset(weight, -1, sizeof(weight));
    sort(id, id + m, [&](const int &a, const int &b)
         {
             return w[a] < w[b];
         });
    for (int i = 0; i < m; ++ i)
    {
        unite(u[id[i]] + 1, v[id[i]] + 1, w[id[i]]);
    }
    DFS(n, 0);
}
int getMinimumFuelCapacity(int X, int Y)
{
    return get(X + 1, Y + 1);
}
/*void read()
{
    init(5, 6, {0, 0, 1, 1, 1, 2}, {1, 2, 2, 3, 4, 3}, {4, 4, 1, 2, 10, 3});
    cout << getMinimumFuelCapacity(1, 2) << '\n';
    cout << getMinimumFuelCapacity(2, 4) << '\n';
    cout << getMinimumFuelCapacity(0, 1);
 
    init(3, 2, {0, 0}, {1, 2}, {5, 5});
    cout << getMinimumFuelCapacity(1, 2);
}
void solve()
{
 
}
int  main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        //freopen(TASK".OUT", "w", stdout);
    }
    int t = 1;
    bool typetest = false;
    if (typetest)
    {
        cin >> t;
    }
    for (int __ = 1; __ <= t; ++ __)
    {
        //cout << "Case " << __ << ": ";
        read();
        solve();
    }
}*/

Compilation message

swap.cpp: In function 'void unite(int, int, int)':
swap.cpp:20:22: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
   20 |     bool ok = deg[u] > 1 | deg[v] > 1;
      |               ~~~~~~~^~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 5 ms 9648 KB Output is correct
4 Correct 7 ms 9788 KB Output is correct
5 Correct 7 ms 9924 KB Output is correct
6 Correct 6 ms 9812 KB Output is correct
7 Correct 6 ms 9928 KB Output is correct
8 Correct 6 ms 9940 KB Output is correct
9 Correct 104 ms 28724 KB Output is correct
10 Correct 127 ms 32844 KB Output is correct
11 Correct 121 ms 32512 KB Output is correct
12 Correct 160 ms 33768 KB Output is correct
13 Correct 154 ms 36988 KB Output is correct
14 Correct 135 ms 28852 KB Output is correct
15 Correct 280 ms 37044 KB Output is correct
16 Correct 251 ms 36468 KB Output is correct
17 Correct 267 ms 37824 KB Output is correct
18 Correct 318 ms 41064 KB Output is correct
19 Correct 132 ms 18584 KB Output is correct
20 Correct 242 ms 38184 KB Output is correct
21 Correct 239 ms 37636 KB Output is correct
22 Correct 247 ms 39468 KB Output is correct
23 Correct 296 ms 42436 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 300 ms 43224 KB Output is correct
4 Correct 291 ms 44560 KB Output is correct
5 Correct 281 ms 44008 KB Output is correct
6 Correct 301 ms 44336 KB Output is correct
7 Correct 280 ms 44392 KB Output is correct
8 Correct 288 ms 43128 KB Output is correct
9 Correct 314 ms 43980 KB Output is correct
10 Correct 312 ms 42924 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 5 ms 9648 KB Output is correct
4 Correct 7 ms 9788 KB Output is correct
5 Correct 7 ms 9924 KB Output is correct
6 Correct 6 ms 9812 KB Output is correct
7 Correct 6 ms 9928 KB Output is correct
8 Correct 6 ms 9940 KB Output is correct
9 Correct 6 ms 9684 KB Output is correct
10 Correct 8 ms 9928 KB Output is correct
11 Correct 6 ms 9940 KB Output is correct
12 Correct 6 ms 9928 KB Output is correct
13 Correct 6 ms 9812 KB Output is correct
14 Correct 6 ms 9920 KB Output is correct
15 Correct 6 ms 9928 KB Output is correct
16 Correct 7 ms 9924 KB Output is correct
17 Correct 6 ms 9940 KB Output is correct
18 Correct 7 ms 9940 KB Output is correct
19 Correct 7 ms 9808 KB Output is correct
20 Correct 9 ms 9928 KB Output is correct
21 Correct 7 ms 9928 KB Output is correct
22 Correct 9 ms 9812 KB Output is correct
23 Correct 7 ms 9812 KB Output is correct
24 Correct 7 ms 9964 KB Output is correct
25 Correct 8 ms 9940 KB Output is correct
26 Correct 7 ms 9968 KB Output is correct
27 Correct 6 ms 9924 KB Output is correct
28 Correct 7 ms 9940 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 ms 9648 KB Output is correct
5 Correct 7 ms 9788 KB Output is correct
6 Correct 7 ms 9924 KB Output is correct
7 Correct 6 ms 9812 KB Output is correct
8 Correct 6 ms 9928 KB Output is correct
9 Correct 6 ms 9940 KB Output is correct
10 Correct 104 ms 28724 KB Output is correct
11 Correct 127 ms 32844 KB Output is correct
12 Correct 121 ms 32512 KB Output is correct
13 Correct 160 ms 33768 KB Output is correct
14 Correct 154 ms 36988 KB Output is correct
15 Correct 8 ms 9928 KB Output is correct
16 Correct 6 ms 9940 KB Output is correct
17 Correct 6 ms 9928 KB Output is correct
18 Correct 6 ms 9812 KB Output is correct
19 Correct 6 ms 9920 KB Output is correct
20 Correct 6 ms 9928 KB Output is correct
21 Correct 7 ms 9924 KB Output is correct
22 Correct 6 ms 9940 KB Output is correct
23 Correct 7 ms 9940 KB Output is correct
24 Correct 7 ms 9808 KB Output is correct
25 Correct 9 ms 9928 KB Output is correct
26 Correct 7 ms 9928 KB Output is correct
27 Correct 9 ms 9812 KB Output is correct
28 Correct 7 ms 9812 KB Output is correct
29 Correct 7 ms 9964 KB Output is correct
30 Correct 8 ms 9940 KB Output is correct
31 Correct 7 ms 9968 KB Output is correct
32 Correct 6 ms 9924 KB Output is correct
33 Correct 7 ms 9940 KB Output is correct
34 Correct 17 ms 13000 KB Output is correct
35 Correct 124 ms 33476 KB Output is correct
36 Correct 147 ms 33556 KB Output is correct
37 Correct 134 ms 33456 KB Output is correct
38 Correct 135 ms 33136 KB Output is correct
39 Correct 140 ms 33100 KB Output is correct
40 Correct 115 ms 31052 KB Output is correct
41 Correct 126 ms 33724 KB Output is correct
42 Correct 150 ms 33464 KB Output is correct
43 Correct 114 ms 37652 KB Output is correct
44 Correct 139 ms 33864 KB Output is correct
45 Correct 148 ms 33548 KB Output is correct
46 Correct 138 ms 33484 KB Output is correct
47 Correct 137 ms 33524 KB Output is correct
48 Correct 158 ms 35124 KB Output is correct
49 Correct 68 ms 16992 KB Output is correct
50 Correct 56 ms 16824 KB Output is correct
51 Correct 126 ms 29480 KB Output is correct
52 Correct 200 ms 36760 KB Output is correct
53 Correct 176 ms 38360 KB Output is correct
54 Correct 241 ms 38416 KB Output is correct
55 Correct 131 ms 37212 KB Output is correct
56 Correct 189 ms 39204 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 5 ms 9648 KB Output is correct
4 Correct 7 ms 9788 KB Output is correct
5 Correct 7 ms 9924 KB Output is correct
6 Correct 6 ms 9812 KB Output is correct
7 Correct 6 ms 9928 KB Output is correct
8 Correct 6 ms 9940 KB Output is correct
9 Correct 104 ms 28724 KB Output is correct
10 Correct 127 ms 32844 KB Output is correct
11 Correct 121 ms 32512 KB Output is correct
12 Correct 160 ms 33768 KB Output is correct
13 Correct 154 ms 36988 KB Output is correct
14 Correct 135 ms 28852 KB Output is correct
15 Correct 280 ms 37044 KB Output is correct
16 Correct 251 ms 36468 KB Output is correct
17 Correct 267 ms 37824 KB Output is correct
18 Correct 318 ms 41064 KB Output is correct
19 Correct 300 ms 43224 KB Output is correct
20 Correct 291 ms 44560 KB Output is correct
21 Correct 281 ms 44008 KB Output is correct
22 Correct 301 ms 44336 KB Output is correct
23 Correct 280 ms 44392 KB Output is correct
24 Correct 288 ms 43128 KB Output is correct
25 Correct 314 ms 43980 KB Output is correct
26 Correct 312 ms 42924 KB Output is correct
27 Correct 8 ms 9928 KB Output is correct
28 Correct 6 ms 9940 KB Output is correct
29 Correct 6 ms 9928 KB Output is correct
30 Correct 6 ms 9812 KB Output is correct
31 Correct 6 ms 9920 KB Output is correct
32 Correct 6 ms 9928 KB Output is correct
33 Correct 7 ms 9924 KB Output is correct
34 Correct 6 ms 9940 KB Output is correct
35 Correct 7 ms 9940 KB Output is correct
36 Correct 17 ms 13000 KB Output is correct
37 Correct 124 ms 33476 KB Output is correct
38 Correct 147 ms 33556 KB Output is correct
39 Correct 134 ms 33456 KB Output is correct
40 Correct 135 ms 33136 KB Output is correct
41 Correct 140 ms 33100 KB Output is correct
42 Correct 115 ms 31052 KB Output is correct
43 Correct 126 ms 33724 KB Output is correct
44 Correct 150 ms 33464 KB Output is correct
45 Correct 114 ms 37652 KB Output is correct
46 Correct 139 ms 33864 KB Output is correct
47 Correct 25 ms 13140 KB Output is correct
48 Correct 246 ms 38316 KB Output is correct
49 Correct 242 ms 38416 KB Output is correct
50 Correct 232 ms 38344 KB Output is correct
51 Correct 237 ms 38188 KB Output is correct
52 Correct 220 ms 36936 KB Output is correct
53 Correct 186 ms 31556 KB Output is correct
54 Correct 254 ms 39244 KB Output is correct
55 Correct 285 ms 38440 KB Output is correct
56 Correct 377 ms 41672 KB Output is correct
57 Correct 275 ms 39292 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 ms 9648 KB Output is correct
5 Correct 7 ms 9788 KB Output is correct
6 Correct 7 ms 9924 KB Output is correct
7 Correct 6 ms 9812 KB Output is correct
8 Correct 6 ms 9928 KB Output is correct
9 Correct 6 ms 9940 KB Output is correct
10 Correct 104 ms 28724 KB Output is correct
11 Correct 127 ms 32844 KB Output is correct
12 Correct 121 ms 32512 KB Output is correct
13 Correct 160 ms 33768 KB Output is correct
14 Correct 154 ms 36988 KB Output is correct
15 Correct 135 ms 28852 KB Output is correct
16 Correct 280 ms 37044 KB Output is correct
17 Correct 251 ms 36468 KB Output is correct
18 Correct 267 ms 37824 KB Output is correct
19 Correct 318 ms 41064 KB Output is correct
20 Correct 300 ms 43224 KB Output is correct
21 Correct 291 ms 44560 KB Output is correct
22 Correct 281 ms 44008 KB Output is correct
23 Correct 301 ms 44336 KB Output is correct
24 Correct 280 ms 44392 KB Output is correct
25 Correct 288 ms 43128 KB Output is correct
26 Correct 314 ms 43980 KB Output is correct
27 Correct 312 ms 42924 KB Output is correct
28 Correct 8 ms 9928 KB Output is correct
29 Correct 6 ms 9940 KB Output is correct
30 Correct 6 ms 9928 KB Output is correct
31 Correct 6 ms 9812 KB Output is correct
32 Correct 6 ms 9920 KB Output is correct
33 Correct 6 ms 9928 KB Output is correct
34 Correct 7 ms 9924 KB Output is correct
35 Correct 6 ms 9940 KB Output is correct
36 Correct 7 ms 9940 KB Output is correct
37 Correct 17 ms 13000 KB Output is correct
38 Correct 124 ms 33476 KB Output is correct
39 Correct 147 ms 33556 KB Output is correct
40 Correct 134 ms 33456 KB Output is correct
41 Correct 135 ms 33136 KB Output is correct
42 Correct 140 ms 33100 KB Output is correct
43 Correct 115 ms 31052 KB Output is correct
44 Correct 126 ms 33724 KB Output is correct
45 Correct 150 ms 33464 KB Output is correct
46 Correct 114 ms 37652 KB Output is correct
47 Correct 139 ms 33864 KB Output is correct
48 Correct 25 ms 13140 KB Output is correct
49 Correct 246 ms 38316 KB Output is correct
50 Correct 242 ms 38416 KB Output is correct
51 Correct 232 ms 38344 KB Output is correct
52 Correct 237 ms 38188 KB Output is correct
53 Correct 220 ms 36936 KB Output is correct
54 Correct 186 ms 31556 KB Output is correct
55 Correct 254 ms 39244 KB Output is correct
56 Correct 285 ms 38440 KB Output is correct
57 Correct 377 ms 41672 KB Output is correct
58 Correct 275 ms 39292 KB Output is correct
59 Correct 132 ms 18584 KB Output is correct
60 Correct 242 ms 38184 KB Output is correct
61 Correct 239 ms 37636 KB Output is correct
62 Correct 247 ms 39468 KB Output is correct
63 Correct 296 ms 42436 KB Output is correct
64 Correct 7 ms 9808 KB Output is correct
65 Correct 9 ms 9928 KB Output is correct
66 Correct 7 ms 9928 KB Output is correct
67 Correct 9 ms 9812 KB Output is correct
68 Correct 7 ms 9812 KB Output is correct
69 Correct 7 ms 9964 KB Output is correct
70 Correct 8 ms 9940 KB Output is correct
71 Correct 7 ms 9968 KB Output is correct
72 Correct 6 ms 9924 KB Output is correct
73 Correct 7 ms 9940 KB Output is correct
74 Correct 148 ms 33548 KB Output is correct
75 Correct 138 ms 33484 KB Output is correct
76 Correct 137 ms 33524 KB Output is correct
77 Correct 158 ms 35124 KB Output is correct
78 Correct 68 ms 16992 KB Output is correct
79 Correct 56 ms 16824 KB Output is correct
80 Correct 126 ms 29480 KB Output is correct
81 Correct 200 ms 36760 KB Output is correct
82 Correct 176 ms 38360 KB Output is correct
83 Correct 241 ms 38416 KB Output is correct
84 Correct 131 ms 37212 KB Output is correct
85 Correct 189 ms 39204 KB Output is correct
86 Correct 81 ms 19676 KB Output is correct
87 Correct 276 ms 38440 KB Output is correct
88 Correct 291 ms 38420 KB Output is correct
89 Correct 332 ms 38472 KB Output is correct
90 Correct 204 ms 21504 KB Output is correct
91 Correct 214 ms 23492 KB Output is correct
92 Correct 289 ms 34428 KB Output is correct
93 Correct 384 ms 41424 KB Output is correct
94 Correct 379 ms 42756 KB Output is correct
95 Correct 403 ms 42232 KB Output is correct
96 Correct 339 ms 41996 KB Output is correct
97 Correct 335 ms 42316 KB Output is correct