oj.uz

Submission #567846

# Submission time Handle Problem Language Result Execution time Memory
567846 2022-05-24T09:19:04 Z Tien_Noob Swapping Cities (APIO20_swap) C++17
6 / 100
 382 ms 42780 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)
{
    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] | deg[u] > 1 | deg[v] > 1;
    if (able[n])
    {
        weight[n] = w;
    }
    ++deg[u];
    ++deg[v];
    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:32:42: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
   32 |     able[n] = able[u] | able[v] | deg[u] > 1 | deg[v] > 1;
      |                                   ~~~~~~~^~~
swap.cpp:32:55: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
   32 |     able[n] = able[u] | able[v] | deg[u] > 1 | deg[v] > 1;
      |                                                ~~~~~~~^~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9684 KB Output is correct
2 Correct 6 ms 9660 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 6 ms 9812 KB Output is correct
5 Correct 6 ms 9944 KB Output is correct
6 Correct 6 ms 9856 KB Output is correct
7 Correct 6 ms 9940 KB Output is correct
8 Correct 6 ms 9940 KB Output is correct
9 Correct 115 ms 28856 KB Output is correct
10 Correct 141 ms 33356 KB Output is correct
11 Correct 133 ms 32860 KB Output is correct
12 Correct 138 ms 34244 KB Output is correct
13 Correct 124 ms 37368 KB Output is correct
14 Correct 118 ms 29388 KB Output is correct
15 Correct 244 ms 37452 KB Output is correct
16 Correct 247 ms 36804 KB Output is correct
17 Correct 234 ms 38220 KB Output is correct
18 Correct 382 ms 41388 KB Output is correct
19 Correct 87 ms 18636 KB Output is correct
20 Correct 242 ms 38564 KB Output is correct
21 Correct 230 ms 38096 KB Output is correct
22 Correct 235 ms 39712 KB Output is correct
23 Correct 317 ms 42780 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9684 KB Output is correct
2 Correct 6 ms 9660 KB Output is correct
3 Incorrect 244 ms 42360 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9684 KB Output is correct
2 Correct 6 ms 9660 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 6 ms 9812 KB Output is correct
5 Correct 6 ms 9944 KB Output is correct
6 Correct 6 ms 9856 KB Output is correct
7 Correct 6 ms 9940 KB Output is correct
8 Correct 6 ms 9940 KB Output is correct
9 Correct 5 ms 9660 KB Output is correct
10 Incorrect 6 ms 9924 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9660 KB Output is correct
2 Correct 7 ms 9684 KB Output is correct
3 Correct 6 ms 9660 KB Output is correct
4 Correct 6 ms 9684 KB Output is correct
5 Correct 6 ms 9812 KB Output is correct
6 Correct 6 ms 9944 KB Output is correct
7 Correct 6 ms 9856 KB Output is correct
8 Correct 6 ms 9940 KB Output is correct
9 Correct 6 ms 9940 KB Output is correct
10 Correct 115 ms 28856 KB Output is correct
11 Correct 141 ms 33356 KB Output is correct
12 Correct 133 ms 32860 KB Output is correct
13 Correct 138 ms 34244 KB Output is correct
14 Correct 124 ms 37368 KB Output is correct
15 Incorrect 6 ms 9924 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9684 KB Output is correct
2 Correct 6 ms 9660 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 6 ms 9812 KB Output is correct
5 Correct 6 ms 9944 KB Output is correct
6 Correct 6 ms 9856 KB Output is correct
7 Correct 6 ms 9940 KB Output is correct
8 Correct 6 ms 9940 KB Output is correct
9 Correct 115 ms 28856 KB Output is correct
10 Correct 141 ms 33356 KB Output is correct
11 Correct 133 ms 32860 KB Output is correct
12 Correct 138 ms 34244 KB Output is correct
13 Correct 124 ms 37368 KB Output is correct
14 Correct 118 ms 29388 KB Output is correct
15 Correct 244 ms 37452 KB Output is correct
16 Correct 247 ms 36804 KB Output is correct
17 Correct 234 ms 38220 KB Output is correct
18 Correct 382 ms 41388 KB Output is correct
19 Incorrect 244 ms 42360 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9660 KB Output is correct
2 Correct 7 ms 9684 KB Output is correct
3 Correct 6 ms 9660 KB Output is correct
4 Correct 6 ms 9684 KB Output is correct
5 Correct 6 ms 9812 KB Output is correct
6 Correct 6 ms 9944 KB Output is correct
7 Correct 6 ms 9856 KB Output is correct
8 Correct 6 ms 9940 KB Output is correct
9 Correct 6 ms 9940 KB Output is correct
10 Correct 115 ms 28856 KB Output is correct
11 Correct 141 ms 33356 KB Output is correct
12 Correct 133 ms 32860 KB Output is correct
13 Correct 138 ms 34244 KB Output is correct
14 Correct 124 ms 37368 KB Output is correct
15 Correct 118 ms 29388 KB Output is correct
16 Correct 244 ms 37452 KB Output is correct
17 Correct 247 ms 36804 KB Output is correct
18 Correct 234 ms 38220 KB Output is correct
19 Correct 382 ms 41388 KB Output is correct
20 Incorrect 244 ms 42360 KB Output isn't correct
21 Halted 0 ms 0 KB -