Submission #520105

#	Time	Username	Problem	Language	Result	Execution time	Memory
520105		Killer2501	Joker (BOI20_joker)	C++14	100 / 100	181 ms	13464 KiB

Joker

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define pb push_back
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;
const int N = 3e5+5;
const int M = 21;
const ll inf = 4e18;
const ll mod = 998244353;
int n, t, m, k, ans, tong, a[N], lab[N], d[N], b[N], c[N];
pii dp[N];
vector<int> vi;
string s;
struct node
{
    int x, vx, y, vy;
    node(){}
    node(int _x, int _vx, int _y, int _vy)
    {
        x = _x;
        vx = _vx;
        y = _y;
        vy = _vy;
    }
};
vector<node> q;
pii findp(int u)
{
    int bi = 0;
    while(lab[u] > 0)
    {
        bi ^= c[u];
        u = lab[u];
    }
    return {u, bi};
}
bool hop(int u, int v)
{
    pii x = findp(u), y = findp(v);
    if(x.fi == y.fi)
    {
        if(x.se == y.se)return false;
        return true;
    }
    q.pb(node(x.fi, lab[x.fi], y.fi, lab[y.fi]));
    if(lab[x.fi] > lab[y.fi])swap(x, y);
    lab[x.fi] += lab[y.fi];
    lab[y.fi] = x.fi;
    c[y.fi] = x.se^y.se^1;
    return true;
}
void rollback(int sz)
{
    while((int)q.size() > sz)
    {
        node u = q.back();
        q.pop_back();
        lab[u.x] = u.vx;
        lab[u.y] = u.vy;
    }
}
void cal(int l, int r, int opl, int opr)
{
    if(l > r)return;
    int mid = (l+r)>>1;
    int sz = q.size();
    bool ok = true;
    for(int i = max(l, 1); i <= mid; i ++)
    {
        if(!hop(a[i], b[i]))
        {
            ok = false;
            break;
        }
    }

    if(ok)
    {
        int sz1 = q.size();
        d[mid] = 0;
        for(int i = min(opr, m); i >= max(opl, mid+1); i --)
        {
            if(!hop(a[i], b[i]))
            {
                d[mid] = i;
                break;
            }
        }
        rollback(sz1);
        cal(mid+1, r, d[mid], opr);
    }
    //cout << mid <<" "<<d[mid]<<" "<<ok << '\n';
    rollback(sz);
    for(int i = d[mid]+1; i <= opr; i ++)hop(a[i], b[i]);
    cal(l, mid-1, opl, d[mid]);
    rollback(sz);

}
void sol()
{
    cin >> n >> m >> t;
    fill_n(lab, n+1, -1);
    for(int i = 1; i <= m; i ++)
    {
        cin >> a[i] >> b[i];
        d[i] = m+1;
    }
    cal(0, m, 1, m+1);
    while(t -- > 0)
    {
        int l, r;
        cin >> l >> r;
        if(d[l-1] >= r+1)cout << "YES" << '\n';
        else cout << "NO" << '\n';
    }
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    #define task "test"
    if(fopen(task".inp", "r"))
	{
		freopen(task".inp", "r", stdin);
		freopen(task".out", "w", stdout);
    }
    int ntest = 1;
    //cin >> ntest;
    while(ntest -- > 0)
    sol();
}

Compilation message (stderr)

Joker.cpp: In function 'int main()':
Joker.cpp:130:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |   freopen(task".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:131:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |   freopen(task".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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