oj.uz

Submission #1047051

# Submission time Handle Problem Language Result Execution time Memory
1047051 2024-08-07T08:10:48 Z ssense Swapping Cities (APIO20_swap) C++14
100 / 100
 152 ms 85700 KB 
#include <iostream>
#include "swap.h"
#include <algorithm>
#include <vector>
#include <array>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <chrono>
#include <random>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <iomanip>
#include <bitset>
#include <limits.h>
#include <cassert>
 
#define fr first
#define sc second
 
using namespace std;
 
// #define int long long

const int N = 500005;

int dsu[N], par[23][N], valid[N], sz[N], zero[N], one[N], two[N], deg[N], val[N], depth[N];

int new_vertex;

vector<int> adj[N];

int find(int a)
{
    if(dsu[a] == a)
    {
        return a;
    }
    return dsu[a] = find(dsu[a]);
}

void add_edge(int a, int b, int w)
{
    int ca = find(a);
    int cb = find(b);
    if(ca == cb)
    {

        dsu[new_vertex] = new_vertex;
        par[0][ca] = new_vertex;
        dsu[ca] = new_vertex;
        adj[new_vertex].push_back(ca);
        val[new_vertex] = w;
        if(valid[ca])
        {
            valid[new_vertex] = 1;
        }
        sz[new_vertex] = sz[ca];
        zero[new_vertex] = zero[ca];
        one[new_vertex] = one[ca];
        two[new_vertex] = two[ca];
        if(deg[a] == 2 || deg[b] == 2)
        {
            valid[new_vertex] = 1;
            new_vertex++;
            return;
        }
        if(deg[a] == 0)
        {
            deg[a]++;
            zero[new_vertex]--;
            one[new_vertex]++;
        }
        else if(deg[a] == 1)
        {
            deg[a]++;
            one[new_vertex]--;
            two[new_vertex]++;
        }
        if(deg[b] == 0)
        {
            deg[b]++;
            zero[new_vertex]--;
            one[new_vertex]++;
        }
        else if(deg[b] == 1)
        {
            deg[b]++;
            one[new_vertex]--;
            two[new_vertex]++;
        }
        if(two[new_vertex] == sz[new_vertex])
        {
            valid[new_vertex] = 1;
        }
        new_vertex++;
        return;
    }
    dsu[new_vertex] = new_vertex;
    dsu[ca] = new_vertex;
    dsu[cb] = new_vertex;
    par[0][ca] = new_vertex;
    par[0][cb] = new_vertex;
    adj[new_vertex].push_back(ca);
    adj[new_vertex].push_back(cb);
    val[new_vertex] = w;
    if(valid[ca] || valid[cb])
    {
        valid[new_vertex] = 1;
    }
    else
    {
        if(deg[a] == 2 || deg[b] == 2)
        {
            valid[new_vertex] = 1;
            new_vertex++;
            return;
        }
        sz[new_vertex] = sz[ca]+sz[cb];
        zero[new_vertex] = zero[ca]+zero[cb];
        one[new_vertex] = one[ca]+one[cb];
        two[new_vertex] = two[ca]+two[cb];
        if(deg[a] == 0)
        {
            deg[a]++;
            zero[new_vertex]--;
            one[new_vertex]++;
        }
        else if(deg[a] == 1)
        {
            deg[a]++;
            one[new_vertex]--;
            two[new_vertex]++;
        }
        if(deg[b] == 0)
        {
            deg[b]++;
            zero[new_vertex]--;
            one[new_vertex]++;
        }
        else if(deg[b] == 1)
        {
            deg[b]++;
            one[new_vertex]--;
            two[new_vertex]++;
        }
        if(two[new_vertex] == sz[new_vertex])
        {
            valid[new_vertex] = 1;
        }
    }
    new_vertex++;
}

void dfs(int u)
{
    for(auto v : adj[u])
    {
        depth[v] = depth[u]+1;
        dfs(v);
    }
}

int jump(int a, int len)
{
    for(int i = 0; i <= 19; i++)
    {
        if((len&(1<<i)) != 0)
        {
            a = par[i][a];
        }
    }
    return a;
}

int lca_v(int a, int b)
{
    // cout << "FINDING LCA: " << a << " " << b << endl;
    int lca;
    if(depth[a] < depth[b])
    {
        swap(a, b);
    }
    a = jump(a, depth[a]-depth[b]);
    if(a == b){lca = a;}
    else
    {
        // cout << "BEFORE ENTERING: " << a << " " << b << endl;
        for(int i = 19; i >= 0; i--)
        {
            if(par[i][a] != par[i][b])
            {
                a = par[i][a];
                b = par[i][b];
            }
        }
        lca = par[0][a];
    }
    // cout << "LCA FOUND BEFORE VALID: " << lca << endl; 
    if(valid[lca])
    {
        return lca;
    }
    for(int i = 19; i >= 0; i--)
    {
        if(valid[par[i][lca]] == 0)
        {
            lca = par[i][lca];
        }
    }
    lca = par[0][lca];
    return lca;
}

void init(int n, int m, vector<int> u, vector<int> v, vector<int> w)
{
    for(int i = 1; i <= n; i++)
    {
        zero[i] = 1;
        sz[i] = 1;
        dsu[i] = i;
    }
    new_vertex = n+1;
    vector<pair<int, int> > s;
    for(int i = 0; i < m; i++)
    {
        s.push_back(make_pair(w[i], i));
    }
    sort(s.begin(), s.end());
    for(int i = 0; i < m; i++)
    {
        //cout << "ADDING EDGE: " << u[s[i].sc]+1 << " " <<  v[s[i].sc]+1 << " " <<  s[i].fr << endl;
        add_edge(u[s[i].sc]+1, v[s[i].sc]+1, s[i].fr);
    }
    // for(int i = 0; i < new_vertex; i++)
    // {
    //     cout << "VALID[" << i << "] = " << valid[i] << endl;
    // }
    if(valid[new_vertex-1])
    {
        valid[0] = 1;
    }
    depth[0] = -1;
    dfs(new_vertex-1);
    // for(int i = 0; i < new_vertex; i++)
    // {
    //     cout << "Depth[" << i << "] = " << depth[i] << endl;
    // }
    for(int i = 1; i <= 19; i++)
    {
        for(int j = 1; j < new_vertex; j++)
        {
            par[i][j] = par[i-1][par[i-1][j]];
        }
    }
    // cout << new_vertex << endl;
} 

int getMinimumFuelCapacity(int x, int y)
{
    x++;
    y++;
    int bruh = lca_v(x, y);
    if(bruh == 0)
    {
        return -1;
    }
    else
    {
        return val[bruh];
    }
}
 
// int32_t main()
// {
//     ios_base::sync_with_stdio(false);cin.tie(0);
//     int n, m, q;
//     cin >> n >> m;
//     vector<int> u(m), v(m), w(m);
//     for(int i = 0; i < m; i++)
//     {
//         cin >> u[i];
//     }
//     for(int i = 0; i < m; i++)
//     {
//         cin >> v[i];
//     }
//     for(int i = 0; i < m; i++)
//     {
//         cin >> w[i];
//     }
//     init(n, m, u, v, w);
//     cin >> q;
//     for(int i = 0; i < q; i++)
//     {
//         int x, y;
//         cin >> x >> y;
//         cout << getMinimumFuelCapacity(x, y) << endl;
//     }
// }
 
/*
5 6
0 0 1 1 1 2
1 2 2 3 4 3
4 4 1 2 10 3
3
1 2
2 4
0 1

*/
 
/*
#include <iostream>
#include <algorithm>
#include <vector>
#include <array>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <chrono>
#include <random>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <iomanip>
#include <bitset>
#include <cassert>
*/

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 59992 KB Output is correct
2 Correct 5 ms 59992 KB Output is correct
3 Correct 5 ms 60100 KB Output is correct
4 Correct 6 ms 59992 KB Output is correct
5 Correct 7 ms 60508 KB Output is correct
6 Correct 6 ms 59996 KB Output is correct
7 Correct 6 ms 59996 KB Output is correct
8 Correct 6 ms 59996 KB Output is correct
9 Correct 37 ms 67528 KB Output is correct
10 Correct 45 ms 69316 KB Output is correct
11 Correct 44 ms 69120 KB Output is correct
12 Correct 48 ms 69572 KB Output is correct
13 Correct 41 ms 70812 KB Output is correct
14 Correct 43 ms 67780 KB Output is correct
15 Correct 103 ms 73156 KB Output is correct
16 Correct 101 ms 72900 KB Output is correct
17 Correct 101 ms 73416 KB Output is correct
18 Correct 118 ms 74692 KB Output is correct
19 Correct 63 ms 66516 KB Output is correct
20 Correct 99 ms 73504 KB Output is correct
21 Correct 117 ms 73700 KB Output is correct
22 Correct 105 ms 74380 KB Output is correct
23 Correct 123 ms 75544 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 59992 KB Output is correct
2 Correct 5 ms 59992 KB Output is correct
3 Correct 99 ms 74792 KB Output is correct
4 Correct 95 ms 75288 KB Output is correct
5 Correct 98 ms 75296 KB Output is correct
6 Correct 96 ms 75036 KB Output is correct
7 Correct 114 ms 75332 KB Output is correct
8 Correct 99 ms 74888 KB Output is correct
9 Correct 114 ms 75072 KB Output is correct
10 Correct 96 ms 74924 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 59992 KB Output is correct
2 Correct 5 ms 59992 KB Output is correct
3 Correct 5 ms 60100 KB Output is correct
4 Correct 6 ms 59992 KB Output is correct
5 Correct 7 ms 60508 KB Output is correct
6 Correct 6 ms 59996 KB Output is correct
7 Correct 6 ms 59996 KB Output is correct
8 Correct 6 ms 59996 KB Output is correct
9 Correct 5 ms 59996 KB Output is correct
10 Correct 6 ms 60252 KB Output is correct
11 Correct 6 ms 60252 KB Output is correct
12 Correct 5 ms 59996 KB Output is correct
13 Correct 6 ms 59996 KB Output is correct
14 Correct 6 ms 60096 KB Output is correct
15 Correct 5 ms 59996 KB Output is correct
16 Correct 5 ms 59996 KB Output is correct
17 Correct 6 ms 60252 KB Output is correct
18 Correct 6 ms 60248 KB Output is correct
19 Correct 6 ms 60056 KB Output is correct
20 Correct 6 ms 60252 KB Output is correct
21 Correct 6 ms 60076 KB Output is correct
22 Correct 7 ms 60252 KB Output is correct
23 Correct 6 ms 59996 KB Output is correct
24 Correct 6 ms 60252 KB Output is correct
25 Correct 6 ms 60252 KB Output is correct
26 Correct 6 ms 60252 KB Output is correct
27 Correct 5 ms 60248 KB Output is correct
28 Correct 6 ms 60252 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 59996 KB Output is correct
2 Correct 6 ms 59992 KB Output is correct
3 Correct 5 ms 59992 KB Output is correct
4 Correct 5 ms 60100 KB Output is correct
5 Correct 6 ms 59992 KB Output is correct
6 Correct 7 ms 60508 KB Output is correct
7 Correct 6 ms 59996 KB Output is correct
8 Correct 6 ms 59996 KB Output is correct
9 Correct 6 ms 59996 KB Output is correct
10 Correct 37 ms 67528 KB Output is correct
11 Correct 45 ms 69316 KB Output is correct
12 Correct 44 ms 69120 KB Output is correct
13 Correct 48 ms 69572 KB Output is correct
14 Correct 41 ms 70812 KB Output is correct
15 Correct 6 ms 60252 KB Output is correct
16 Correct 6 ms 60252 KB Output is correct
17 Correct 5 ms 59996 KB Output is correct
18 Correct 6 ms 59996 KB Output is correct
19 Correct 6 ms 60096 KB Output is correct
20 Correct 5 ms 59996 KB Output is correct
21 Correct 5 ms 59996 KB Output is correct
22 Correct 6 ms 60252 KB Output is correct
23 Correct 6 ms 60248 KB Output is correct
24 Correct 6 ms 60056 KB Output is correct
25 Correct 6 ms 60252 KB Output is correct
26 Correct 6 ms 60076 KB Output is correct
27 Correct 7 ms 60252 KB Output is correct
28 Correct 6 ms 59996 KB Output is correct
29 Correct 6 ms 60252 KB Output is correct
30 Correct 6 ms 60252 KB Output is correct
31 Correct 6 ms 60252 KB Output is correct
32 Correct 5 ms 60248 KB Output is correct
33 Correct 6 ms 60252 KB Output is correct
34 Correct 10 ms 61276 KB Output is correct
35 Correct 43 ms 69372 KB Output is correct
36 Correct 45 ms 69320 KB Output is correct
37 Correct 43 ms 69572 KB Output is correct
38 Correct 48 ms 69424 KB Output is correct
39 Correct 43 ms 69576 KB Output is correct
40 Correct 46 ms 68636 KB Output is correct
41 Correct 45 ms 69572 KB Output is correct
42 Correct 48 ms 69252 KB Output is correct
43 Correct 46 ms 71300 KB Output is correct
44 Correct 51 ms 70084 KB Output is correct
45 Correct 70 ms 76736 KB Output is correct
46 Correct 44 ms 69352 KB Output is correct
47 Correct 49 ms 69828 KB Output is correct
48 Correct 52 ms 71624 KB Output is correct
49 Correct 60 ms 78536 KB Output is correct
50 Correct 47 ms 74436 KB Output is correct
51 Correct 59 ms 74692 KB Output is correct
52 Correct 72 ms 77248 KB Output is correct
53 Correct 80 ms 79060 KB Output is correct
54 Correct 93 ms 82112 KB Output is correct
55 Correct 46 ms 71368 KB Output is correct
56 Correct 82 ms 79684 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 59992 KB Output is correct
2 Correct 5 ms 59992 KB Output is correct
3 Correct 5 ms 60100 KB Output is correct
4 Correct 6 ms 59992 KB Output is correct
5 Correct 7 ms 60508 KB Output is correct
6 Correct 6 ms 59996 KB Output is correct
7 Correct 6 ms 59996 KB Output is correct
8 Correct 6 ms 59996 KB Output is correct
9 Correct 37 ms 67528 KB Output is correct
10 Correct 45 ms 69316 KB Output is correct
11 Correct 44 ms 69120 KB Output is correct
12 Correct 48 ms 69572 KB Output is correct
13 Correct 41 ms 70812 KB Output is correct
14 Correct 43 ms 67780 KB Output is correct
15 Correct 103 ms 73156 KB Output is correct
16 Correct 101 ms 72900 KB Output is correct
17 Correct 101 ms 73416 KB Output is correct
18 Correct 118 ms 74692 KB Output is correct
19 Correct 99 ms 74792 KB Output is correct
20 Correct 95 ms 75288 KB Output is correct
21 Correct 98 ms 75296 KB Output is correct
22 Correct 96 ms 75036 KB Output is correct
23 Correct 114 ms 75332 KB Output is correct
24 Correct 99 ms 74888 KB Output is correct
25 Correct 114 ms 75072 KB Output is correct
26 Correct 96 ms 74924 KB Output is correct
27 Correct 6 ms 60252 KB Output is correct
28 Correct 6 ms 60252 KB Output is correct
29 Correct 5 ms 59996 KB Output is correct
30 Correct 6 ms 59996 KB Output is correct
31 Correct 6 ms 60096 KB Output is correct
32 Correct 5 ms 59996 KB Output is correct
33 Correct 5 ms 59996 KB Output is correct
34 Correct 6 ms 60252 KB Output is correct
35 Correct 6 ms 60248 KB Output is correct
36 Correct 10 ms 61276 KB Output is correct
37 Correct 43 ms 69372 KB Output is correct
38 Correct 45 ms 69320 KB Output is correct
39 Correct 43 ms 69572 KB Output is correct
40 Correct 48 ms 69424 KB Output is correct
41 Correct 43 ms 69576 KB Output is correct
42 Correct 46 ms 68636 KB Output is correct
43 Correct 45 ms 69572 KB Output is correct
44 Correct 48 ms 69252 KB Output is correct
45 Correct 46 ms 71300 KB Output is correct
46 Correct 51 ms 70084 KB Output is correct
47 Correct 15 ms 61684 KB Output is correct
48 Correct 94 ms 73496 KB Output is correct
49 Correct 96 ms 73496 KB Output is correct
50 Correct 111 ms 73752 KB Output is correct
51 Correct 92 ms 73772 KB Output is correct
52 Correct 95 ms 73360 KB Output is correct
53 Correct 89 ms 71844 KB Output is correct
54 Correct 97 ms 74224 KB Output is correct
55 Correct 101 ms 73500 KB Output is correct
56 Correct 110 ms 75028 KB Output is correct
57 Correct 102 ms 74776 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 59996 KB Output is correct
2 Correct 6 ms 59992 KB Output is correct
3 Correct 5 ms 59992 KB Output is correct
4 Correct 5 ms 60100 KB Output is correct
5 Correct 6 ms 59992 KB Output is correct
6 Correct 7 ms 60508 KB Output is correct
7 Correct 6 ms 59996 KB Output is correct
8 Correct 6 ms 59996 KB Output is correct
9 Correct 6 ms 59996 KB Output is correct
10 Correct 37 ms 67528 KB Output is correct
11 Correct 45 ms 69316 KB Output is correct
12 Correct 44 ms 69120 KB Output is correct
13 Correct 48 ms 69572 KB Output is correct
14 Correct 41 ms 70812 KB Output is correct
15 Correct 43 ms 67780 KB Output is correct
16 Correct 103 ms 73156 KB Output is correct
17 Correct 101 ms 72900 KB Output is correct
18 Correct 101 ms 73416 KB Output is correct
19 Correct 118 ms 74692 KB Output is correct
20 Correct 99 ms 74792 KB Output is correct
21 Correct 95 ms 75288 KB Output is correct
22 Correct 98 ms 75296 KB Output is correct
23 Correct 96 ms 75036 KB Output is correct
24 Correct 114 ms 75332 KB Output is correct
25 Correct 99 ms 74888 KB Output is correct
26 Correct 114 ms 75072 KB Output is correct
27 Correct 96 ms 74924 KB Output is correct
28 Correct 6 ms 60252 KB Output is correct
29 Correct 6 ms 60252 KB Output is correct
30 Correct 5 ms 59996 KB Output is correct
31 Correct 6 ms 59996 KB Output is correct
32 Correct 6 ms 60096 KB Output is correct
33 Correct 5 ms 59996 KB Output is correct
34 Correct 5 ms 59996 KB Output is correct
35 Correct 6 ms 60252 KB Output is correct
36 Correct 6 ms 60248 KB Output is correct
37 Correct 10 ms 61276 KB Output is correct
38 Correct 43 ms 69372 KB Output is correct
39 Correct 45 ms 69320 KB Output is correct
40 Correct 43 ms 69572 KB Output is correct
41 Correct 48 ms 69424 KB Output is correct
42 Correct 43 ms 69576 KB Output is correct
43 Correct 46 ms 68636 KB Output is correct
44 Correct 45 ms 69572 KB Output is correct
45 Correct 48 ms 69252 KB Output is correct
46 Correct 46 ms 71300 KB Output is correct
47 Correct 51 ms 70084 KB Output is correct
48 Correct 15 ms 61684 KB Output is correct
49 Correct 94 ms 73496 KB Output is correct
50 Correct 96 ms 73496 KB Output is correct
51 Correct 111 ms 73752 KB Output is correct
52 Correct 92 ms 73772 KB Output is correct
53 Correct 95 ms 73360 KB Output is correct
54 Correct 89 ms 71844 KB Output is correct
55 Correct 97 ms 74224 KB Output is correct
56 Correct 101 ms 73500 KB Output is correct
57 Correct 110 ms 75028 KB Output is correct
58 Correct 102 ms 74776 KB Output is correct
59 Correct 63 ms 66516 KB Output is correct
60 Correct 99 ms 73504 KB Output is correct
61 Correct 117 ms 73700 KB Output is correct
62 Correct 105 ms 74380 KB Output is correct
63 Correct 123 ms 75544 KB Output is correct
64 Correct 6 ms 60056 KB Output is correct
65 Correct 6 ms 60252 KB Output is correct
66 Correct 6 ms 60076 KB Output is correct
67 Correct 7 ms 60252 KB Output is correct
68 Correct 6 ms 59996 KB Output is correct
69 Correct 6 ms 60252 KB Output is correct
70 Correct 6 ms 60252 KB Output is correct
71 Correct 6 ms 60252 KB Output is correct
72 Correct 5 ms 60248 KB Output is correct
73 Correct 6 ms 60252 KB Output is correct
74 Correct 70 ms 76736 KB Output is correct
75 Correct 44 ms 69352 KB Output is correct
76 Correct 49 ms 69828 KB Output is correct
77 Correct 52 ms 71624 KB Output is correct
78 Correct 60 ms 78536 KB Output is correct
79 Correct 47 ms 74436 KB Output is correct
80 Correct 59 ms 74692 KB Output is correct
81 Correct 72 ms 77248 KB Output is correct
82 Correct 80 ms 79060 KB Output is correct
83 Correct 93 ms 82112 KB Output is correct
84 Correct 46 ms 71368 KB Output is correct
85 Correct 82 ms 79684 KB Output is correct
86 Correct 40 ms 66508 KB Output is correct
87 Correct 92 ms 73500 KB Output is correct
88 Correct 103 ms 73820 KB Output is correct
89 Correct 111 ms 75204 KB Output is correct
90 Correct 112 ms 83136 KB Output is correct
91 Correct 116 ms 81348 KB Output is correct
92 Correct 116 ms 78140 KB Output is correct
93 Correct 137 ms 80836 KB Output is correct
94 Correct 148 ms 82848 KB Output is correct
95 Correct 152 ms 85700 KB Output is correct
96 Correct 110 ms 75292 KB Output is correct
97 Correct 145 ms 79004 KB Output is correct