What's wrong with this?

Please someone point out whats wrong in the following code for QTREE3 on spoj.
It gets a score of 0 but I’m sure its right.

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

struct node{
	int id;
	int depth;
	int subtree_sz;
	int color; //0 is white, 1 is black
	vector<node*> nodesonpath;
	vector<node*> neighbors;
	set<int> blacknodes;
	node* parent;
	node* headnode; // head of heavy-path
};

node* newNode(int id){
	node* n = new node;
	n->id = id;
	n->parent = n->headnode = NULL;
	n->color = 0;
	return n;
}

int x,y,z;

void dfs(node* n, node* parent){
	if(!parent){
		n->depth = 0; //root
	}
	else n->depth = parent->depth + 1;
	
	//sets up subtree sizes
	n->parent = parent;
	n->subtree_sz = 1;
	for(int i = 0; i < n->neighbors.size(); i++){
		if(n->neighbors[i] == parent) continue;
		dfs(n->neighbors[i],n);
		n->subtree_sz += n->neighbors[i]->subtree_sz;
	}
}

void dfs_hld(node* n, node* parent, node* headnode){
	n->headnode = headnode;
	headnode->nodesonpath.push_back(n);
	for(auto &n1 : n->neighbors){
		if(n1 == parent) continue;
		if(n1->subtree_sz > (n->subtree_sz - 1)/2)
			dfs_hld(n1,n,headnode);
		else 
			dfs_hld(n1,n,n1);
	}
}

vector<node*> nodes;

void change(node* &n){
	if(n->color == 0){
		//white
		n->color = 1;
		n->headnode->blacknodes.insert(n->id);
	}
	else{
		//black
		n->color = 0;
		n->headnode->blacknodes.erase(n->id);
	}
}

int findmin(node* &n){
	int minval = -2, temp;
	node* ncur = n;
	while(ncur){
		if(!ncur->headnode->blacknodes.empty()){
			temp = *(ncur->headnode->blacknodes.begin());
			if(nodes[temp]->depth <= ncur->depth) minval = temp;
		}
		ncur = ncur->headnode->parent;
	}
	return 1+minval;
}

void addEdge(int a, int b){
	nodes[a]->neighbors.push_back(nodes[b]);
	nodes[b]->neighbors.push_back(nodes[a]);
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int N,Q;
	cin >> N >> Q;
	nodes.resize(N);
	for(int i = 0; i < N; i++)
		nodes[i] = newNode(i);

	for(int i = 0; i < N-1; i++){
		cin >> x >> y;
		addEdge(x-1,y-1);
	}
	dfs(nodes[0],NULL);
	dfs_hld(nodes[0],NULL,nodes[0]);
	int query;
	while(Q--){
		cin >> query >> x;
		if(query == 0){
			change(nodes[x-1]);
		}
		else{
			cout << findmin(nodes[x-1]) << endl;
		}
	}

	return 0;
}

As a request, please do refrain from giving general advice: this is perhaps the 20th time in 2 days that my code passes all sample testcases I wrote but scores 0. So please don’t give me general advice as to “do this, that”; please instead directly point out what my code does wrong or a testcase in which it gives a wrong answer.

test case
4 3
1 4
4 3
3 2
0 4
0 3
1 2

your output = 3

correct output = 4

2 Likes

Thanks.
I see what i was doing wrong.
Using set gives minimum id not minimum depth.
Thanks a lot again

1 Like

Thanks a lot! Finally got 100! After 2 days. :smile:
I was making such a silly error :sweat_smile:

2 Likes