Weird behavior on vector initialization

help
1

I’m experiencing a very weird behavior on vector initialization. All codes are working fine on my local machine with inputs of 1M size, and they even pass half of systests. I simply can’t guess what could even possibly go wrong here.

Full codes are here (CodeChef: Practical coding for everyone), but what’s relevant is the following.

std::vector<int> a;

// working
void way1(){
  a.resize(n);
  for(int i=0; i<n; i++){
      std::cin >> a[i];
  }
}

// not working
void way2(){
  a.reserve(n);
  int ai;
  for (int i = 0; i < n; i++){
       std::cin >> ai;
       a.push_back(ai);
  }
}

// working
void way3(){
  a = std::vector<int>(0);
  a.reserve(n);
  int ai;
  for (int i = 0; i < n; i++){
       std::cin >> ai;
       a.push_back(ai);
  }
}

How come push_back can possibly go wrong? And then here comes the standard graph representation.

std::vector<std::vector<int>> neighbors;

 // working
void way1(){
  neighbors = std::vector<std::vector<int>>(n);
}
    
// not working
void way2(){
    neighbors.resize(n);
}
    
// not working
void way3(){
    neighbors.resize(n, std::vector<int>(0));
}
 
// working
void way4(){
    neighbors.resize(n);
    for(int i=0; i<n; i++){
         neighbors[i].resize(0);
    }
}

Well, I really don’t know. Codechef’s compiler having some weird default constructor is my only guess.

Any help is appreciated!

2

I think you are unaware of what the vector functions resize, reserve, and clear do.
Refer to the following to understand what exactly happens when each of them is called on Empty and non-empty vectors.

Vector Resize: std::vector<T,Allocator>::resize - cppreference.com
Vector Reserve: std::vector<T,Allocator>::reserve - cppreference.com
Vector Clear: std::vector<T,Allocator>::clear - cppreference.com

You should notice that your code runs not against just 1 test case. So, if you’re using global variables, you should make sure you’re clearing all the contents of vectors before running on the next test case.

An example:

vector<vector<int>> adj;

void solve() {
    int N = 0;
    cin >> N;
    // Use exactly one of the following
    
    // Resize
    adj.clear();
    adj.resize(N, vector<int>());

    // Fresh allocation
    adj = vector<vector<int>>(N, vector<int>());

    // With Reserve
    adj.clear();
    adj.reserve(N);
    for(int i = 0; i < N; i++) {
        adj.push_back(vector<int>());
    }

    // Rest is straight forward
    for(int i = 0; i < N - 1; i++) {
        int a = 0, b = 0;
        cin >> a >> b;
        adj[a - 1].push_back(b - 1);
        adj[b - 1].push_back(a - 1);
    }
}

You might want to explore further on these.

3

Thanks so much. I knew exactly what vector functions do, but yeah, I really forgot there are multiple test cases. Ah, global variables are bad.