Submission #1086015

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086015		yoav_s	Joker (BOI20_joker)	C++17	14 / 100	2078 ms	10188 KiB

Joker

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
using namespace std;

typedef int ll;
typedef vector<ll> v;
typedef vector<v> vv;
typedef vector<vv> vvv;
typedef pair<ll, ll> p;
typedef vector<p> vp;
typedef vector<vp> vvp;
typedef vector<vvp> vvvp;
typedef pair<ll, p> tri;
typedef vector<tri> vtri;
typedef vector<vtri> vvtri;
typedef vector<vvtri> vvvtri;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<vvb> vvvb;

#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()

const ll INF = 1e18;
const ll mod = 1e9 + 7;

void undo(v &dsuParent, v &dsuSize, v &dsuMul, p update)
{
    if (update.f == update.s) return;
    dsuParent[update.f] = update.f;
    dsuSize[update.s] -= dsuSize[update.f];
    dsuMul[update.f] = 1;
}

p getParentAndHeight(ll a, v &dsuParent, v &dsuMul)
{
    ll mul = dsuMul[a];
    while (dsuParent[a] != a)
    {
        a = dsuParent[a];
        mul *= dsuMul[a];
    }
    return p(a, mul);
}

void pushUpdate(v &dsuParent, v &dsuSize, v &dsuMul, p update, ll index, stack<tri> &updates, stack<p> &actUpdates, stack<bool> &wasBipartite)
{
    updates.emplace(index, p(update.f, update.s));
    p r1 = getParentAndHeight(update.f, dsuParent, dsuMul), r2 = getParentAndHeight(update.s, dsuParent, dsuMul);
    update.f = r1.f; update.s = r2.f;
    if (dsuSize[update.f] > dsuSize[update.s]) swap(update.f, update.s);
    actUpdates.push(update);
    if (update.f != update.s)
    {
        dsuParent[update.f] = update.s;
        dsuSize[update.s] += dsuSize[update.f];
        dsuMul[update.f] = -1 * r1.s * r2.s;
        wasBipartite.push(wasBipartite.top());
    }
    else if (r1.s == r2.s)
    {
        wasBipartite.push(false);
    }
    else
    {
        wasBipartite.push(wasBipartite.top());
    }
}

void popUpdate(v &dsuParent, v &dsuSize, v &dsuMul, ll popIndex, stack<tri> &updates, stack<p> &actUpdates, stack<bool> &wasBipartite)
{
    if (updates.top().f == popIndex)
    {
        undo(dsuParent, dsuSize, dsuMul, actUpdates.top());
        updates.pop();
        wasBipartite.pop();
        actUpdates.pop();
        return;
    }
    ll lasts = 0, recents = 0;
    vtri popped;
    while (!updates.empty() && (lasts < recents || recents == 0))
    {
        popped.eb(updates.top());
        undo(dsuParent, dsuSize, dsuMul, actUpdates.top());
        updates.pop();
        wasBipartite.pop();
        actUpdates.pop();
        if (popped.back().f == popIndex)
        {
            recents++; popIndex++;
        }
        else lasts++;
    }
    sort(all(popped),greater<tri>());
    for (ll i = 0; i < popped.size() - 1; i++) pushUpdate(dsuParent, dsuSize, dsuMul, popped[i].s, popped[i].f, updates, actUpdates, wasBipartite);
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    ll N, M, Q;
    cin >> N >> M >> Q;
    vp edges(M);
    for (ll i = 0; i < M; i++)
    {
        cin >> edges[i].f >> edges[i].s;
        edges[i].f--;
        edges[i].s--;
    }
    v dsuParent(N);
    for (ll i = 0; i < N; i++) dsuParent[i] = i;
    v dsuSize(N, 1), dsuMul(N, 1);
    stack<tri> updates; //index, merged i to j
    stack<bool> wasBipartite; wasBipartite.push(true);
    stack<p> actUpdates;
    v stoppingBeingBipartite(M, INF);
    ll j = 1 % M;
    ll updateFront = 0, updateBack = 0;
    pushUpdate(dsuParent, dsuSize, dsuMul, edges[0], updateFront++, updates, actUpdates, wasBipartite);
    for (ll i = 0; i < M; i++)
    {
        while (j != i && wasBipartite.top())
        {
            pushUpdate(dsuParent, dsuSize, dsuMul, edges[j], updateFront++, updates, actUpdates, wasBipartite); j = (j + 1) % M;
        }
        if (!wasBipartite.top())
            stoppingBeingBipartite[i] = (j + M - 1) % M;
        popUpdate(dsuParent, dsuSize, dsuMul, updateBack++, updates, actUpdates, wasBipartite);
    }
    ll i = 0;
    while (Q--)
    {
        ll a, b;
        cin >> a >> b; a--; b--; b = (b + 1) % M;
        bool poss = b != a && ((stoppingBeingBipartite[b] > b && b > a) || (stoppingBeingBipartite[b] < a)) && stoppingBeingBipartite[b] != INF;
        if (poss) cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}

Compilation message (stderr)

Joker.cpp:27:16: warning: overflow in conversion from 'double' to 'll' {aka 'int'} changes value from '1.0e+18' to '2147483647' [-Woverflow]
   27 | const ll INF = 1e18;
      |                ^~~~
Joker.cpp: In function 'void popUpdate(v&, v&, v&, ll, std::stack<std::pair<int, std::pair<int, int> > >&, std::stack<std::pair<int, int> >&, std::stack<bool>&)':
Joker.cpp:99:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |     for (ll i = 0; i < popped.size() - 1; i++) pushUpdate(dsuParent, dsuSize, dsuMul, popped[i].s, popped[i].f, updates, actUpdates, wasBipartite);
      |                    ~~^~~~~~~~~~~~~~~~~~~
Joker.cpp: In function 'int main()':
Joker.cpp:134:8: warning: unused variable 'i' [-Wunused-variable]
  134 |     ll i = 0;
      |        ^

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 0 / 25
• Subtask 4: 0 / 10
• Subtask 5: 0 / 22
• Subtask 6: 0 / 29