Submission #729340

#	Time	Username	Problem	Language	Result	Execution time	Memory
729340		jerzyk	Joker (BOI20_joker)	C++14	100 / 100	249 ms	13428 KiB

Joker

#include <bits/stdc++.h>

using namespace std;

const int N = 200 * 1000 + 7;

struct dynamic_mst
{
    int fau[N], mn[N], pp = -1, sum[N];
    bool ifb = true;
    vector<pair<int, pair <int,int>>> edges;

    void start(int v)
    {
    	sum[v] = 1;
    	fau[v] = v;
    	mn[v] = 1;
    }
    pair<int, int> find(int v)
    {
    	pair<int, int> w;
    	if(fau[v] == v)
    		return make_pair(v, mn[v]);

    	w = find(fau[v]);
    	w.second *= mn[v];
    	return w;
    }

    void add(pair<int,int> edge)
    {
       	pair<int, int> w1, w2;
       	w1 = find(edge.first);
       	w2 = find(edge.second);
       	if(w1.first == w2.first)
       	{
       		if(w1.second == w2.second)
       		{
       			ifb = false;
       			if(pp == -1)
       				pp = edges.size() + 1;
       		}
       		edges.push_back(make_pair(0, edge));
       	}else
       	{
       		if(sum[w1.first] < sum[w2.first])
       		{
       			swap(w1, w2);
       			swap(edge.first, edge.second);
       		}
       		sum[w1.first] += sum[w2.first];
            if(mn[w1.first] == -1)
            {
                mn[w1.first] *= -1;
                mn[w2.first] *= -1; 
            }
       		if(w1.second == w2.second)
            {
       			mn[w2.first] *= -1;
            }

       		fau[w2.first] = w1.first;
       		edges.push_back(make_pair(1, make_pair(w1.first, w2.first)));
       	}
    }
    void remove()
    {
        if(edges.size() == 0)
            return;

        if(edges.back().first == 1)
        {
        	fau[edges.back().second.second] = edges.back().second.second;
       		sum[edges.back().second.first] -= sum[edges.back().second.second];
        }
        if((int)edges.size() == pp)
        {
        	pp = -1;
        	ifb = true;
        }
        edges.pop_back();
    }
    void print_colors()
    {
        for (int i = 1; i <= 5; i++)
            cout << i << ", " << mn[i] << " | ";
        cout << "\n";

    }
    int check()
    {
        for (int i = 0; i < (int)edges.size(); ++i)
        {
            cout << edges[i].second.first << " " << edges[i].second.second << " : ";
        }
        cout << "\n";
        return edges.size();
    }
    bool is_bipartite()
    {
        return ifb;
    }
};

dynamic_mst mst;
int w[N];
pair<int, int> kr[N];

void DAC(int p, int k, int aw)
{
    int i, v;
    v = (p + k) / 2;
    for(i = k; i > v; --i)
        mst.add(kr[i]);

    if(v != p)
    {
        mst.add(kr[v]);
        DAC(p, v - 1, aw);
        mst.remove();
    }

    i = aw;
    while(mst.is_bipartite() && i < v)
    {
        ++i;
        mst.add(kr[i]);
    }
    if(i > aw && mst.is_bipartite() == false)
    {
        --i;
        mst.remove();
    }
    w[v] = i;
    if(!mst.is_bipartite())
        w[v] = -1;

    for( ; i > aw; --i)
        mst.remove();

    for(i = v + 1; i <= k; ++i)
        mst.remove();
    
    for(i = aw + 1; i <= w[v]; ++i)
        mst.add(kr[i]);

    i = max(aw, w[v]);
    if(v != k)
        DAC(v + 1, k, i);
    
    for(i = w[v]; i > aw; --i)
        mst.remove();
}

void Odpowiadaj(int m)
{
    int i, a, b;
    for(i = 1; i <= m; ++i)
    {
        cin >> a >> b;
        if(w[b] >= a - 1)
            cout << "NO\n";
        else
            cout << "YES\n";
    }
}

void Wczytaj(int &n, int &m)
{
    int k, i, a, b;
    cin >> k >> n >> m;
    for(i = 1; i <= k; ++i)
        mst.start(i);
    for(i = 1; i <= n; ++i)
    {
        cin >> a >> b;
        kr[i] = make_pair(a, b);
    }
}

void Joker()
{
    int n, m;
    Wczytaj(n, m);
    DAC(1, n, 0);
    Odpowiadaj(m);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	Joker();

	return 0;
}

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