Not sure why minute detail causes error in code?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <fstream>
#include <vector>
#include <set>
#include <queue>
using namespace std;
vector<set<int> > groups;
set<int> gr;
vector<int> belong [1000001];
queue<int> q;
bool cond [1000001];
int main () {
	ifstream fin("invite.in");
	ofstream fout("invite.out");
    int n, g, s, cow;
    fin>>n>>g;
    for (int i=0; i<g; i++) {
        fin>>s;
        for (int j=0; j<s; j++) {
            fin>>cow;
            gr.insert(--cow);
            belong[cow].push_back(i);
        }
        groups.push_back(gr);
        gr.clear();
    }
    fin.close();
    q.push(0);
    cond[0]=true;
    int cur;
    int count=0;
    while (!q.empty()) {
        cur=q.front();
        q.pop();
        count++;
            for (int j=0; j<belong[cur].size(); j++) {
                int x=belong[cur][j];
                groups[x].erase(cur);
                int y=*groups[x].begin();
                if (groups[x].size()==1) {
                	if (!cond[y]) {
                	cond[y]=true;
                	q.push(y);
                	}
                }
            }
        }
        fout<<count<<endl;
        fout.close();
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <fstream>
#include <vector>
#include <set>
#include <queue>
using namespace std;
vector<set<int> > groups;
set<int> gr;
vector<int> belong [1000001];
queue<int> q;
bool cond [1000001];
int main () {
	ifstream fin("invite.in");
	ofstream fout("invite.out");
    int n, g, s, cow;
    fin>>n>>g;
    for (int i=1; i<=g; i++) {
        fin>>s;
        for (int j=0; j<s; j++) {
            fin>>cow;
            gr.insert(cow);
            belong[cow].push_back(i);
        }
        groups.push_back(gr);
        gr.clear();
    }
    fin.close();
    q.push(1);
    cond[1]=true;
    int cur;
    int count=0;
    while (!q.empty()) {
        cur=q.front();
        q.pop();
        count++;
            for (int j=0; j<belong[cur].size(); j++) {
                int x=belong[cur][j];
                groups[x].erase(cur);
                int y=*groups[x].begin();
                if (groups[x].size()==1) {
                	if (!cond[y]) {
                	cond[y]=true;
                	q.push(y);
                	}
                }
            }
        }
        fout<<count<<endl;
        fout.close();
    }

I feel like these two pieces of code should be the same in theory? The first one runs fine on the online judge and the second one return missing output file.

Lines 16. 20. 27. 28
Last edited on
"minute detail" ... not true has only "minute" difference from true, yet the result could not be more different.
Of cource small edits can cause huge changes, if they change the logic.

1
2
3
4
5
6
7
8
9
10
11
12
    int n, g, s, cow;
    fin>>n>>g;
    for (int i=0; i<g; i++) {
        fin>>s;
        for (int j=0; j<s; j++) {
            fin>>cow;
            gr.insert(--cow);
            belong[cow].push_back(i);
        }
        groups.push_back(gr);
        gr.clear();
    }
    int n, g, s, cow;
    fin>>n>>g;
    for (int i=1; i<=g; i++) {
        fin>>s;
        for (int j=0; j<s; j++) {
            fin>>cow;
            gr.insert(cow);
            belong[cow].push_back(i);
        }
        groups.push_back(gr);
        gr.clear();
    }

You have made three changes.

1. You have changed what values does the 'i' get and therefore what values are stored in the vectors of 'belong'.

2. You change what you store in 'gr' and where you store in 'belong'. I won't even try to check whether and how 'belong' and 'gr' are related, but my first instinct says: "that is a mess".

If you want to change the 'i' and 'i' only, then write:
1
2
3
4
5
6
7
8
9
10
11
12
    int n, g, s, cow;
    fin>>n>>g;
    for (int i=1; i<=g; i++) {
        fin>>s;
        for (int j=0; j<s; j++) {
            fin>>cow;
            gr.insert(--cow);
            belong[cow].push_back(i-1);
        }
        groups.push_back(gr);
        gr.clear();
    }



Given vector<int> belong [1000001]; the fin >> cow; belong[cow].push_back(value); is scary in both versions, unless you can completely, blindly, and entirely trust that all reads from input file succeed and produce valid array indices.
Last edited on
Topic archived. No new replies allowed.