Submission #1308713

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308713		Born_To_Laugh	Joker (BOI20_joker)	C++17	39 / 100	2095 ms	16012 KiB

Joker

// Born_To_Laugh - Hughie Do
#include <bits/stdc++.h>
#define alle(AC) AC.begin(), AC.end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
[[maybe_unused]] const ll MOD = 998244353, INF = 1e9 + 7;

const int maxn = 2e5 + 10;
int n, m, q;
vector<pair<int, int>> edges(maxn);
vector<pair<int, int>> query(maxn);

struct DSU
{
    vector<int> par;
    vector<int> sz;
    int n;
    void init(int len){
        n = len;
        par.assign(n + 1, 0);
        sz.assign(n + 1, 1);
        for(int i=1; i<=n; ++i){
            par[i] = i;
        }
    }
    int Head_Set(int a){
        if(a == par[a])return a;
        return par[a] = Head_Set(par[a]);
    }
    void Union_Set(int a, int b){
        a = Head_Set(a);
        b = Head_Set(b);
        if(a == b)return;
        if(sz[a] < sz[b])swap(a, b);
        par[b] = a;
        sz[a] += sz[b];
    }
    bool same_set(int a, int b){
        return Head_Set(a) == Head_Set(b);
    }
};

namespace sub34
{
    vector<int> ans;
    vector<vector<pair<int, int>>> qr;
    vector<pair<int, int>> val;
    
    bool check(){
        for(int i=1; i<=q; ++i){
            if(query[i].fi > 200)return 0;
        }
        return 1;
    }
    void ope(int l){
        DSU dsu;
        dsu.init(2 * n + 5);

        bool ok = 0;
        for(int i=1; i<l; ++i){
            int a = edges[i].fi;
            int b = edges[i].se;
            dsu.Union_Set(val[a].fi, val[b].se);
            dsu.Union_Set(val[a].se, val[b].fi);
            if(dsu.same_set(val[a].fi, val[a].se) || dsu.same_set(val[b].fi, val[b].se)){
                ok = 1;
            }
        }
        int id = m;
        for(auto &cc: qr[l]){
            while(id > cc.fi){
                int a = edges[id].fi;
                int b = edges[id].se;
                dsu.Union_Set(val[a].fi, val[b].se);
                dsu.Union_Set(val[a].se, val[b].fi);
                if(dsu.same_set(val[a].fi, val[a].se) || dsu.same_set(val[b].fi, val[b].se)){
                    ok = 1;
                }
                id--;
            }
            ans[cc.se] = ok;
        }
    }
    void solve(){
        qr.assign(m + 1, vector<pair<int, int>>());
        val.assign(n + 1, {0, 0});
        ans.assign(q + 1, 0);

        for(int i=1; i<=n; ++i){
            val[i].fi = i;
            val[i].se = i + n;
        }
        for(int i=1; i<=q; ++i){
            int l = query[i].fi;
            int r = query[i].se;
            qr[l].push_back({r, i});
        }
        for(int i=1; i<=min(200, m); ++i){
            sort(alle(qr[i]), greater<>());
            ope(i);
        }
        for(int i=1; i<=q; ++i){
            if(ans[i])cout << "YES\n";
            else cout << "NO\n";
        }
    }
};

namespace sub5
{
    vector<vector<int>> adj;
    vector<int> col;
    bool bfs(int a){
        deque<int> bfs;
        col[a] = 1;
        bfs.push_back(a);

        while(!bfs.empty()){
            int x = bfs.front();
            bfs.pop_front();
            for(auto &elm: adj[x]){
                if(col[elm] != 0 && col[elm] != 3 - col[x]){
                    return 1;
                }
                if(col[elm] == 0){
                    col[elm] = 3 - col[x];
                    bfs.push_back(elm);
                }
            }
        }
        return 0;
    }
    bool ope(int l, int r){
        adj.assign(n + 1, vector<int>());
        col.assign(n + 1, 0);

        for(int i=1; i<l; ++i){
            int a = edges[i].fi;
            int b = edges[i].se;
            adj[a].push_back(b);
            adj[b].push_back(a);
        }
        for(int i=r + 1; i<=m; ++i){
            int a = edges[i].fi;
            int b = edges[i].se;
            adj[a].push_back(b);
            adj[b].push_back(a);
        }

        for(int i=1; i<=n; ++i){
            if(col[i] != 0)continue;
            if(bfs(i)){
                return 1;
            }
        }
        return 0;
    }
    void solve(){
        for(int i=1; i<=q; ++i){
            int l = query[i].fi;
            int r = query[i].se;
            if(ope(l, r))cout << "YES\n";
            else cout << "NO\n";
        }
    }
};

void solve(){
    cin >> n >> m >> q;
    for(int i=1; i<=m; ++i){
        cin >> edges[i].fi >> edges[i].se;
    }
    for(int i=1; i<=q; ++i){
        cin >> query[i].fi >> query[i].se;
    }
    if(sub34::check())sub34::solve();
    else sub5::solve();
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
}

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