USACO Bronze- The Great Revegetation code passes case in IDE but not in USACO grader

Debugging Help
#1

I am trying to solve this problem: USACO using C++. When running my code, it says my code passes cases #1, 2, 3, 5 and 6 but fails everything else. I wasn’t sure how to solve it, so I downloaded the test data and inputted case #4 into my program.

My program outputted: 1111211223233233

The file 4.out says: 1111211223233233

I don’t know what my program outputted in case #4 because the USACO grader won’t let me check, so I was just wondering if anyone knew of any errors in my code that might be causing it to output something else. Any help would be appreciated!

My Code

(I have explained certain parts of my program here)

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<double> vd;
typedef vector<vector<double>> vvd;
typedef vector<ull> vull;
typedef vector<vector<ull>> vdull;
typedef unsigned int ui;
typedef pair<int, int> pii;
typedef pair<ull, ull> pull;
typedef double db;
typedef pair<db, db> pdb;
typedef long double ld;

#define pf push_front
#define pb push_back
#define sz(x) (int) x.size()
#define vrange(x) x.begin(), x.end()
#define f first
#define s second

const int MOD = 1e9 + 7;
const ull INF = 1e18;
const int OTHER_MOD = 998244353;
const int BIG_INTEGER = 2147483647;

void setIO(string name = "") {
	ios_base::sync_with_stdio(0); cin.tie(0);
	if(sz(name)){
		freopen((name+".in").c_str(), "r", stdin);
		freopen((name+".out").c_str(), "w", stdout);
	}
}

int main() {
    setIO("revegetate");
    int N, M;
    cin >> N >> M;
    vector<int> adj[N+1];
    int colors[N+1]; // This is supposed to represent the grass type of each field but I put it as color because this is a colouring problem.
    // build the adjacency list here
    for (int i = 0; i < M; ++i) {
        int a, b;
        cin >> a >> b;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    // optimize let colors[1] = 1 because we want the sequence to be lexicographically least.
    colors[1] = 1;
    for (int i = 2; i <= N; ++i) {
        // this algorithm checks if adjacent fields have the same colour, and then picks the smallest colour number available.
        bool one = true;
        bool two = true;
        bool three = true;
        bool four = true;
        for (int j : adj[i]) {
            if (colors[j] == 1) {
                one = false;
            } else if (colors[j] == 2) {
                two = false;
            } else if (colors[j] == 3) {
                three = false;
            } else if (colors[j] == 4) {
                four = false;
            }
        }
        if (one) {
            colors[i] = 1;
        } else if (two) {
            colors[i] = 2;
        } else if (three) {
            colors[i] = 3;
        } else if (four){
            colors[i] = 4;
        } else {
            //cout << "What?\n";
            colors[i] = 0;
        }
    }
    for (int i = 1; i <= N; ++i) {
        cout << colors[i];
    }
}
#2

I might be shooting in the dark here, but have you done bounds checking? When you access memory that’s out of bounds, C++ might just silently fail and return some random value.

#3

Thank you for helping me! I discovered I hadn’t initialized some of the values in my colors array to 0 and once I did that, my solution passed all the cases.

1 Like