oj.uz

Submission #567461

# Submission time Handle Problem Language Result Execution time Memory
567461 2022-05-23T13:58:33 Z Tien_Noob Swapping Cities (APIO20_swap) C++17
6 / 100
 270 ms 38684 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 ;
    }
    bool check = deg[u] > 1 | deg[v] > 1;
    ++n;
    able[n] = able[u] | able[v] | check;
    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});
}
void solve()
{
    cout << getMinimumFuelCapacity(0, 1);
}
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:31:25: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
   31 |     bool check = 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 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 6 ms 9812 KB Output is correct
5 Correct 8 ms 9940 KB Output is correct
6 Correct 7 ms 9812 KB Output is correct
7 Correct 6 ms 9940 KB Output is correct
8 Correct 6 ms 9940 KB Output is correct
9 Correct 99 ms 27236 KB Output is correct
10 Correct 114 ms 31280 KB Output is correct
11 Correct 110 ms 30884 KB Output is correct
12 Correct 118 ms 32204 KB Output is correct
13 Correct 103 ms 35288 KB Output is correct
14 Correct 102 ms 27408 KB Output is correct
15 Correct 210 ms 33208 KB Output is correct
16 Correct 210 ms 32576 KB Output is correct
17 Correct 217 ms 33980 KB Output is correct
18 Correct 265 ms 36912 KB Output is correct
19 Correct 75 ms 16636 KB Output is correct
20 Correct 215 ms 34364 KB Output is correct
21 Correct 205 ms 33740 KB Output is correct
22 Correct 220 ms 35284 KB Output is correct
23 Correct 270 ms 38352 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Incorrect 240 ms 38684 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 6 ms 9812 KB Output is correct
5 Correct 8 ms 9940 KB Output is correct
6 Correct 7 ms 9812 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 9684 KB Output is correct
10 Incorrect 6 ms 9940 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 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9812 KB Output is correct
6 Correct 8 ms 9940 KB Output is correct
7 Correct 7 ms 9812 KB Output is correct
8 Correct 6 ms 9940 KB Output is correct
9 Correct 6 ms 9940 KB Output is correct
10 Correct 99 ms 27236 KB Output is correct
11 Correct 114 ms 31280 KB Output is correct
12 Correct 110 ms 30884 KB Output is correct
13 Correct 118 ms 32204 KB Output is correct
14 Correct 103 ms 35288 KB Output is correct
15 Incorrect 6 ms 9940 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 6 ms 9812 KB Output is correct
5 Correct 8 ms 9940 KB Output is correct
6 Correct 7 ms 9812 KB Output is correct
7 Correct 6 ms 9940 KB Output is correct
8 Correct 6 ms 9940 KB Output is correct
9 Correct 99 ms 27236 KB Output is correct
10 Correct 114 ms 31280 KB Output is correct
11 Correct 110 ms 30884 KB Output is correct
12 Correct 118 ms 32204 KB Output is correct
13 Correct 103 ms 35288 KB Output is correct
14 Correct 102 ms 27408 KB Output is correct
15 Correct 210 ms 33208 KB Output is correct
16 Correct 210 ms 32576 KB Output is correct
17 Correct 217 ms 33980 KB Output is correct
18 Correct 265 ms 36912 KB Output is correct
19 Incorrect 240 ms 38684 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 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9812 KB Output is correct
6 Correct 8 ms 9940 KB Output is correct
7 Correct 7 ms 9812 KB Output is correct
8 Correct 6 ms 9940 KB Output is correct
9 Correct 6 ms 9940 KB Output is correct
10 Correct 99 ms 27236 KB Output is correct
11 Correct 114 ms 31280 KB Output is correct
12 Correct 110 ms 30884 KB Output is correct
13 Correct 118 ms 32204 KB Output is correct
14 Correct 103 ms 35288 KB Output is correct
15 Correct 102 ms 27408 KB Output is correct
16 Correct 210 ms 33208 KB Output is correct
17 Correct 210 ms 32576 KB Output is correct
18 Correct 217 ms 33980 KB Output is correct
19 Correct 265 ms 36912 KB Output is correct
20 Incorrect 240 ms 38684 KB Output isn't correct
21 Halted 0 ms 0 KB -