Submission #1161883

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161883		12345678	Joker (BOI20_joker)	C++20	0 / 100	894 ms	31364 KiB

Joker

#include <bits/stdc++.h>

using namespace std;

const int nx=2e5+5;

int n, m, q, u[nx], v[nx], c[nx], f, sz, dsu[nx], dp[nx], a, b;
vector<pair<int, int>> d[nx];
vector<int> g[nx];

int find(int x)
{
    if (dsu[x]==x) return x;
    return dsu[x]=find(dsu[x]);
}

void dfs(int u, int p, int hd, int l, int r)
{
    //cout<<"dfs "<<u<<' '<<hd<<' '<<l<<' '<<r<<'\n';
    g[hd].push_back(u);
    dsu[u]=hd;
    for (auto [v, idx]:d[u])
    {
        if (v==p||(l<=idx&&idx<=r)) continue;
        //cout<<v<<' '<<u<<' '<<idx<<'\n';
        if (c[v]==-1) c[v]=!c[u], dfs(v, u, hd, l, r);
        else if (c[u]==c[v]) f=1;
    }
}

int check(int l, int r)
{
    f=0;
    for (int i=1; i<=n; i++) c[i]=-1, g[i].clear();
    for (int i=1; i<=n; i++) if (c[i]==-1) c[i]=1, dfs(i, -1, i, l, r);
    return f;
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m>>q;
    sz=min(100, m);
    for (int i=1; i<=m; i++) cin>>u[i]>>v[i], d[u[i]].push_back({v[i], i}), d[v[i]].push_back({u[i], i});
    dp[sz+1]=m+1;
    for (int i=sz; i>=1; i--)
    {
        int idx=dp[i+1];
        if (!check(i-1, idx))
        {
            while (1)
            {
                int pu=find(u[idx-1]), pv=find(v[idx-1]);
                if (pu!=pv)
                {
                    if (g[pu].size()>g[pv].size()) swap(pu, pv);
                    if (c[u[idx-1]]!=c[v[idx-1]]) for (auto x:g[pu]) c[x]=!c[x];
                    while (!g[pu].empty()) g[pv].push_back(g[pu].back()), g[pu].pop_back();
                    dsu[pu]=pv;
                }
                else if (find(u[idx-1])==find(v[idx-1])&&c[u[idx-1]]==c[v[idx-1]]) break;
                idx--;
            }
        }
        dp[i]=idx;
        //cout<<"dp "<<i<<' '<<dp[i]<<'\n';
    }
    /*
    for (int i=1; i<=m; i++)
    {
        for (int j=i; j<=m; j++) cout<<"check "<<i<<' '<<j<<' '<<check(i+1, j-1)<<'\n';
    }*/
    while (q--)
    {
        cin>>a>>b;
        if (b>=dp[a]) cout<<"NO\n";
        else cout<<"YES\n";
    }
}

/*
6 8 2
1 3
1 5
1 6
2 5
2 6
3 4
3 5
5 6
4 8
4 7
*/

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