Submission #593507

#	Time	Username	Problem	Language	Result	Execution time	Memory
593507		thegamercoder19	Game (APIO22_game)	C++17	0 / 100	0 ms	208 KiB

game

#include "game.h"
//#include <bits/stdc++.h>
#include <vector>
#include<set>

using ll = long long;

#define V vector

#define FOR(typ,i,a,b,c) for(typ i = a; i < b; i += c)

using namespace std;
V<ll> dsu, isc, isp;
ll n1,k1;
set<pair<ll,ll>> s;
void ms(ll u)
{
    dsu[u] = u;
}

ll find_set(ll u)
{
    if (u == dsu[u])return u;
    isp[dsu[u]] |= isp[u];
    isc[u] |= isc[dsu[u]];
    return (dsu[u] = find_set(dsu[u]));
}
bool unite(ll u, ll v)
{
    ll pu = find_set(u), pv = find_set(v);
    if (pu == pv)
    {
        if ((isc[u] && isp[v] && !isc[v]) || (u == v && u <= k1 - 1))return 1;
        isc[v] |= isc[u];
        return 0;
    }
    isp[u] |= isp[v];
    isp[pu] |= isp[pv];
    isc[v] |= isc[u];
    isc[pv] |= isc[pu];
    dsu[pv] = pu;
    return 0;
}

void init(int n, int k) 
{
    k1 = k;
    n1 = n;
    dsu.resize(n + 1, -1); isc.resize(n + 1, 0); isp.resize(n + 1, 0);
    isc[0] = 1; isp[0] = 1;
    
    FOR(ll, i, 0, n, 1)ms(i);
    //s.insert({ 0,0 });
    FOR(ll, i, 1, k, 1)unite(i - 1, i), isc[i] = 1, isp[i-1]=1,s.insert({ i - 1,i });//, s.insert({i,i});
}

int add_teleporter(int u, int v)
{
    if (s.find({ u, v }) != s.end())return 0;
    s.insert({ u, v });
    return unite(u, v);
}

• Subtask 1: 0 / 2
• Subtask 2: 0 / 10
• Subtask 3: 0 / 18
• Subtask 4: 0 / 30
• Subtask 5: 0 / 40