oj.uz

Submission #593507

# Submission time Handle Problem Language Result Execution time Memory
593507 2022-07-11T09:57:44 Z thegamercoder19 Game (APIO22_game) C++17
0 / 100
 0 ms 208 KB 
#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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Incorrect 0 ms 208 KB Wrong Answer[1]
5 Halted 0 ms 0 KB -

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Incorrect 0 ms 208 KB Wrong Answer[1]
5 Halted 0 ms 0 KB -

Subtask #3
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Incorrect 0 ms 208 KB Wrong Answer[1]
5 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Incorrect 0 ms 208 KB Wrong Answer[1]
5 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Incorrect 0 ms 208 KB Wrong Answer[1]
5 Halted 0 ms 0 KB -