Bài "Even Path" trên codeforces

[Circuit]

Link bài: Problem - 1252C - Codeforces

  class Disjoint_set
    {
    private:
    	vector<int> parent;
    	vector<int> rank;

    public:
    	Disjoint_set(int n)
    	{
    		parent.resize(n + 1);
    		rank.resize(n + 1);

    		for (int i = 1; i <= n; i++) parent[i] = i;
    		for (int& r : rank) r = 0;
    	}

    	int find(int i)
    	{
    		// If i is the parent of itself
    		if (parent[i] == i)
    		{
    			// Then i is the representative 
    			return i;
    		}
    		else
    		{
    			// Recursively find the representative.
    			int result = find(parent[i]);

    			// We cache the result by moving i’s node 
    			// directly under the representative of this
    			// set
    			parent[i] = result;

    			// And then we return the result
    			return result;
    		}
    	}

    	// Unites the set that includes i and the set 
    // that includes j
    	void _union(int i, int j)
    	{
    		// Find the representatives (or the root nodes) 
    		// for the set that includes i
    		int irep = find(i);

    		// And do the same for the set that includes j
    		int jrep = find(j);

    		// Elements are in same set, no need to 
    		// unite anything.    
    		if (irep == jrep)
    			return;

    		// Get the rank of i’s tree
    		int irank = rank[irep],

    			// Get the rank of j’s tree
    			jrank = rank[jrep];

    		// If i’s rank is less than j’s rank
    		if (irank < jrank)
    		{
    			// Then move i under j
    			parent[irep] = jrep;
    		}

    		// Else if j’s rank is less than i’s rank
    		else if (jrank < irank)
    		{
    			// Then move j under i
    			parent[jrep] = irep;
    		}

    		// Else if their ranks are the same
    		else
    		{

    			// Then move i under j (doesn’t matter
    			// which one goes where)
    			parent[irep] = jrep;

    			// And increment the result tree’s 
    			// rank by 1
    			rank[jrep]++;
    		}
    	}

    	bool In_same_set(int i, int j)
    	{
    		return find(i) == find(j);
    	}
    };

    int main()
    {
    	int n, q;

    	cin >> n >> q;

    	Disjoint_set s(n), s2(n);
    	vector<long long int> arr(n + 1);

    	for (int i = 1; i <= n; i++) cin >> arr[i];

    	for (int i = 1; i <= n; i++)
    	{
    		int _next = (i + 1) % (n + 1) + (i == n);
    		if ((arr[i] + arr[_next]) % 2 == 0) s._union(i, _next);
    	}

    	for (int i = 1; i <= n; i++) cin >> arr[i];

    	for (int i = 1; i <= n; i++)
    	{
    		int _next = (i + 1) % (n + 1) + (i == n);
    		if ((arr[i] + arr[_next]) % 2 == 0) s2._union(i, _next);
    	}

    	for (int i = 0; i < q; i++)
    	{
    		int r1, c1, r2, c2;

    		cin >> r1 >> c1 >> r2 >> c2;

    		if (s.In_same_set(r1, r2) && s2.In_same_set(c1, c2)) cout << "YES";
    		else cout << "NO";

    		cout << endl;
    	}
    	return 0;
    }

Em thử cả Disjoint_set của em và trên GeeksForGeeks đều fail ở test 19. Không biết ý tưởng em sai ở đâu ạ . Giúp em bài này với.

Em giải quyết theo chiều X, Y xem từ r1 có đến được r2 và từ c1 có đến được c2 không. Sau đó trả lời YES nếu đi được từ hai chiều ngược lại thì NO.

[Circuit]

Không thể đi từ n -> 1 được . Chỉ cần xét đến trước n là xong. : D. Cảm ơn mọi người đã đọc lỗi ngớ ngẩn của em

for (int i = 1; i < n; i++)
    	{
    		if ((arr[i] + arr[i + 1]) % 2 == 0) s._union(i, i + 1);
    	}