Submission #1047051

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047051		ssense	Swapping Cities (APIO20_swap)	C++14	100 / 100	152 ms	85700 KiB

swap

#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 / 6
• Subtask 2: 7 / 7
• Subtask 3: 17 / 17
• Subtask 4: 20 / 20
• Subtask 5: 23 / 23
• Subtask 6: 27 / 27