12354 - Paths in a Tree

All about problems in Volume 123. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
wert
New poster
Posts: 1
Joined: Sun Jan 08, 2012 6:43 pm

12354 - Paths in a Tree

Post by wert » Sun Jan 08, 2012 6:52 pm

I need help with this problem. I tried a lot of cases, checking them by hand, but i can't find the mistake.... I need some input for which my program fails

Code: Select all

#include <vector>
#include <stack>
#include <iostream>
#include <cstdio>

using namespace std;

#define forn(i, n) for(int i = 0; i < (int)(n); i++)
#define input ({int _t; scanf("%d", &_t); _t;})

typedef vector<int> vint;

typedef struct _nodo{
  vint adj;
  int par;
  int ind;
  bool mark;
  _nodo(){par=-1;mark = false;}
  
} nodo;

#define p(a) cout << a << endl

int main()
{
	int T = input;
	forn(TT,T)
	{
		int N = input;
		vector<nodo> tree = vector<nodo>(N);
		int a,b;
		forn(i,N) tree[i].ind = i;
		forn(i,N-1)
		{
			a = input;
			b = input;
			tree[a].adj.push_back(b);
			tree[b].par=a;
		}
		
		vint raiz;
		forn(i,N)
			if(tree[i].par == -1){
				raiz.push_back(i);
				//~ p("raiz "<<i);
			}
	
		int res = 0;
		stack<nodo> dfs;
		forn(i,raiz.size())
		dfs.push(tree[raiz[i]]);
		while(!dfs.empty())
		{
			
			nodo top = dfs.top();
			dfs.pop();
			if(top.mark){res++;continue;}
			
			if(top.adj.size())
			{
				forn(i,top.adj.size())
					//~ if(!tree[top.adj[i]].mark)
						dfs.push(tree[top.adj[i]]);
			}else{
				res++;
			}
			tree[top.ind].mark = true;

		}
		p("Case "<<TT+1<<": "<<res);
	}
}
Thank you!

Post Reply

Return to “Volume 123 (12300-12399)”