There is a directed weighted graph with $$$m$$$ edges. There are $$$n$$$ edges marked as good one. Suppose that a vertex $$$h$$$ is called root and we want to find a minimum path starting from $$$h$$$ ending to itself that contains at least $$$k$$$ good edges. Path definition in this problem is as regular path that can not consists of same edges except good one. In fact on this path we can visit good edges as many times we want but not for other edges. (And also note that this path should end with $$$h$$$ itself.)

There is no constraints. I just wanna to know how to beat this problem theoretically.

I was coding for 217A - Ice Skating but I got wrong answer on test 12, can anyone help me out with debugging this code?

Idea: bipartite graph (Union x and y for every point, xs are from 0 to 999 and ys are from 1000 to 1999) What I am doing is subtracting those components with size equal to one that from 2000. The remaining number is equal to the number of components.

    #include <iostream>
    #include <vector>
     
    using namespace std;
     
    class DSU {
     
    public:
        int size;
        int components;
        vector<int> component_size;
        vector<int> id;
     
        DSU(int size) {
            this->size = size;
            this->components = size;
            this->component_size.resize(size, 1);
            this->id.resize(size);
            for(int i = 0; i < size; i++) {
                id[i] = i;
            }
        }
     
        int getSize() {
            return this->size;
        }
     
        int Find(int a) {
            int root = a;
     
            while(root != id[root]) {
                root = id[root];
            }
     
            while(a != root) {
                id[a] = root;
                a = id[a];
            }
     
            return root;
        }
     
        int Union(int a, int b) {
            int root_a = Find(a);
            int root_b = Find(b);
     
            if(root_a == root_b) {
                return root_a;
            } else {
                if (component_size[root_a] > component_size[root_b]) {
                    component_size[root_a] += component_size[id[root_b]];
                    components--;
                    return id[root_b] = root_a;
                } else {
                    component_size[root_b] += component_size[id[root_a]];
                    components--;
                    return id[root_a] = root_b;
                }
            }
        }
     
        void Show() {
            for(int i=0; i<size; i++) {
                cout << i << ' ' << id[i] << endl;
            }
            cout << endl;
            for(int i=0; i<size; i++) {
                cout << i << ' ' << component_size[Find(i)] << endl;
            }
        }
     
    };
     
    void test();
     
    int main() {
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        int t;
        t = 1;
    //    cin >> t;
        while(t--) {
            test();
            cout << endl;
        }
    }
     
    void test() {
        int n;
        cin >> n;
        DSU dsu(2000);
        for(int i = 0; i < n; i++) {
            int x, y;
            cin >> x >> y;
            dsu.Union(x - 1, 1000 + y - 1);
        }
        int ans = 2000;
        for(int i=0; i<2000; i++) {
            dsu.Find(i);
            if(dsu.component_size[i] == 1) {
                ans--;
            }
        }
        cout << ans - 1 << endl;
    }

does anyone know why am I getting idleness error?

77291795

Hello force coders, I was just solving a problem (1324A - Yet Another Tetris Problem) and my code was this:

#include <bits/stdc++.h>
using namespace std;

#define ll long long

#define li(n) for(int i=0; i<n; i++)

void test();

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int t = 1;
	cin >> t;
	while(t--) {
		test();
		cout << endl;
	}
}

void test() {
	int n;
	cin >> n;
	int pre, cur;
	cin >> pre;
	li(n-1) {
		cin >> cur;
		pre%=2;
		cur%=2;
		if(pre==cur) continue;
		else {
			cout << "NO";
			return;
		}
	}
	cout << "YES";
	return;
}

and the tried to check my solution by given test cases, but the operation of taking input was amazingly wonderful. Input:

4
3
1 1 3
4
1 1 2 1
2
11 11
1
100

My Code's Output: (also containing inputs)

4
3
1 1 3
YES
4
1 1 2 1
NO
2 // how?
YES
11 11
1
100
NO

I was wondered why would something like this happen in C++. Likewise I had same problem on some interactive problems before. That Was (1305D - Kuroni and the Celebration) = (72397838)

Any idea?