oj.uz

Submission #567457

# Submission time Handle Problem Language Result Execution time Memory
567457 2022-05-23T13:53:59 Z Tien_Noob Swapping Cities (APIO20_swap) C++17
6 / 100
 322 ms 42936 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] > oo ? -1 : 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]] > oo ? -1 : 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, 0x3f, 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 6 ms 9684 KB Output is correct
2 Correct 6 ms 9660 KB Output is correct
3 Correct 7 ms 9684 KB Output is correct
4 Correct 7 ms 9788 KB Output is correct
5 Correct 9 ms 9916 KB Output is correct
6 Correct 7 ms 9924 KB Output is correct
7 Correct 8 ms 9940 KB Output is correct
8 Correct 6 ms 9928 KB Output is correct
9 Correct 98 ms 28872 KB Output is correct
10 Correct 125 ms 33228 KB Output is correct
11 Correct 119 ms 32780 KB Output is correct
12 Correct 169 ms 34236 KB Output is correct
13 Correct 131 ms 37476 KB Output is correct
14 Correct 108 ms 29248 KB Output is correct
15 Correct 269 ms 37444 KB Output is correct
16 Correct 250 ms 36860 KB Output is correct
17 Correct 223 ms 38312 KB Output is correct
18 Correct 303 ms 41384 KB Output is correct
19 Correct 85 ms 18604 KB Output is correct
20 Correct 223 ms 38600 KB Output is correct
21 Correct 256 ms 38132 KB Output is correct
22 Correct 232 ms 39756 KB Output is correct
23 Correct 322 ms 42936 KB Output is correct

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 6 ms 9660 KB Output is correct
3 Correct 7 ms 9684 KB Output is correct
4 Correct 7 ms 9788 KB Output is correct
5 Correct 9 ms 9916 KB Output is correct
6 Correct 7 ms 9924 KB Output is correct
7 Correct 8 ms 9940 KB Output is correct
8 Correct 6 ms 9928 KB Output is correct
9 Correct 7 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 7 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 6 ms 9660 KB Output is correct
4 Correct 7 ms 9684 KB Output is correct
5 Correct 7 ms 9788 KB Output is correct
6 Correct 9 ms 9916 KB Output is correct
7 Correct 7 ms 9924 KB Output is correct
8 Correct 8 ms 9940 KB Output is correct
9 Correct 6 ms 9928 KB Output is correct
10 Correct 98 ms 28872 KB Output is correct
11 Correct 125 ms 33228 KB Output is correct
12 Correct 119 ms 32780 KB Output is correct
13 Correct 169 ms 34236 KB Output is correct
14 Correct 131 ms 37476 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 6 ms 9684 KB Output is correct
2 Correct 6 ms 9660 KB Output is correct
3 Correct 7 ms 9684 KB Output is correct
4 Correct 7 ms 9788 KB Output is correct
5 Correct 9 ms 9916 KB Output is correct
6 Correct 7 ms 9924 KB Output is correct
7 Correct 8 ms 9940 KB Output is correct
8 Correct 6 ms 9928 KB Output is correct
9 Correct 98 ms 28872 KB Output is correct
10 Correct 125 ms 33228 KB Output is correct
11 Correct 119 ms 32780 KB Output is correct
12 Correct 169 ms 34236 KB Output is correct
13 Correct 131 ms 37476 KB Output is correct
14 Correct 108 ms 29248 KB Output is correct
15 Correct 269 ms 37444 KB Output is correct
16 Correct 250 ms 36860 KB Output is correct
17 Correct 223 ms 38312 KB Output is correct
18 Correct 303 ms 41384 KB Output is correct
19 Incorrect 276 ms 42308 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 6 ms 9660 KB Output is correct
4 Correct 7 ms 9684 KB Output is correct
5 Correct 7 ms 9788 KB Output is correct
6 Correct 9 ms 9916 KB Output is correct
7 Correct 7 ms 9924 KB Output is correct
8 Correct 8 ms 9940 KB Output is correct
9 Correct 6 ms 9928 KB Output is correct
10 Correct 98 ms 28872 KB Output is correct
11 Correct 125 ms 33228 KB Output is correct
12 Correct 119 ms 32780 KB Output is correct
13 Correct 169 ms 34236 KB Output is correct
14 Correct 131 ms 37476 KB Output is correct
15 Correct 108 ms 29248 KB Output is correct
16 Correct 269 ms 37444 KB Output is correct
17 Correct 250 ms 36860 KB Output is correct
18 Correct 223 ms 38312 KB Output is correct
19 Correct 303 ms 41384 KB Output is correct
20 Incorrect 276 ms 42308 KB Output isn't correct
21 Halted 0 ms 0 KB -