Cod sursa(job #1220138)

Utilizator SebiSebiPirtoaca George Sebastian SebiSebi Data 16 august 2014 16:51:29
Problema Arbore Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#include<bitset>
#include<math.h>
using namespace std;

#define NMAX 100001
#define RMAX 301

vector <int> v[NMAX];
int st[NMAX],dr[NMAX],viz[NMAX],a[NMAX],c[RMAX],l[RMAX],r[RMAX],b[NMAX],nr;
bitset <RMAX> p[1000001];

void dfs(int nod)
{
	viz[nod]=1;
	nr++;
	st[nod]=nr;
	b[nr]=nod;
	for(vector <int> :: iterator it=v[nod].begin();it!=v[nod].end();it++)
		if(viz[*it]==0)
			dfs(*it);
	dr[nod]=nr;
}

void buildsqrt(int n)
{
	int i,R,j;
	nr=0;
	R=sqrt(n);
	i=1;
	j=min(n,R);
	while(i<=n) {
		nr++;
		l[nr]=i;
		r[nr]=j;
		i=j+1;
		j=min(n,j+R);
		p[nr][0]=1;
	}
	l[nr+1]=r[nr+1]=n+1;
}

void update(int poz1, int poz2, int sum)
{
	int i,k;
	for(k=1;k<=nr;k++)
		if(l[k]>=poz1)
			break;
	for(i=poz1;i<=l[k]-1;i++)
		a[i]=a[i]+sum;
}

int query(int val)
{
	int k,i;
	return -1;
}

int main  ()
{
	int n,x,y,m,op,i;
	ifstream f("arbore.in");
	ofstream g("arbore.out");
	f>>n>>m;
	for(i=1;i<=n-1;i++) {
		f>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(1);
	buildsqrt(n);
	for(i=1;i<=m;i++) {
		f>>op;
		if(op==1) {
			f>>x>>y;
			update(st[x],dr[x],y);
		}
		else {
			f>>x;
			g<<query(x)<<'\n';
		}
	}
	f.close();
	g.close();
	return 0;
}