Differences

This shows you the differences between two versions of the page.

--- rosedu:cdl:marius-dragus [2010/03/27 09:52]
mdragus created
+++ rosedu:cdl:marius-dragus [2010/03/27 10:07]
mdragus
@@ Line 1: / Line 1: @@
-====== Marius Dragus ======
+= Marius Dragus =
+*Nume complet: Dragus Marius Ioan
+*Alias-uri: DMI
+*Data/locul nașterii: 14 octombrie 1990,Cluj-Napoca
+== Educatie ==
+ *2005-2009 Liceul International de informatica Bucuresti
+ *2009-prezent Universitatea Politehnica Bucuresti
+== Competente ==
+*sunt smecher ce sa mai....
+== Link-uri spre alti oameni smecheri ==
+[[rosedu:cdl:mircea-ghideu|Mircea Ghideu]]
+[[rosedu:cdl:george-mitra|Mitra M. George-Daniel]]
+==Acum niste cod baby==
+<code>#include<stdio.h>
+#include<assert.h>
+#include<vector>
+#include<algorithm>
+#define pb push_back
+#define mkp make_pair
+using namespace std;
+const int maxn = 340;
+vector<short> VECT[maxn];
+vector<pair<short,short> > ANS,AUX,VEC;
+short N,MOVE,COST;
+short VER[maxn];
+short NRT,TATA[maxn];
+short D[maxn][maxn],M[maxn][maxn];
+bool cmpf(pair<short,short> p1,pair<short,short> p2)
+{
+	short n1 = p1.first;
+	short n2 = p2.first;
+	short i1 = p1.second;
+	short i2 = p2.second;
+	for(;i1 <= N && i2 <= N;++i1,++i2)
+	{
+		if (D[n1][i1] != D[n2][i2]) return D[n1][i1] < D[n2][i2];
+                if (D[n1][i1] == 0) return false;
+        }
+	return false;
+}
+bool ver(vector<pair<short,short> > v1,short timp)
+{
+	sort(v1.begin(),v1.end(),cmpf);
+        MOVE = 0;
+	for(int i = v1.size() - 1;v1.size();)
+	{
+                if (timp < 0) return false;
+		if (timp < D[v1[i].first][v1[i].second]) return false;
+		if (timp > D[v1[i].first][v1[i].second])
+		{
+			if (!MOVE) MOVE = v1[i].first;
+			v1.pop_back();--i;
+			timp--;
+			continue;
+		}
+		if (timp == D[v1[i].first][v1[i].second])
+		{
+			if(!MOVE) MOVE = M[v1[i].first][v1[i].second];
+			v1[i].second++;
+			timp--;
+                        while(i != 0 && cmpf(v1[i],v1[i - 1])) swap(v1[i],v1[i - 1]);
+			//sort(v1.begin(),v1.end(),cmpf);
+			continue;
+		}
+	}
+        if (timp < 0) return false;
+	return true;
+}
+void solve(vector<pair<short,short> > &v)
+{
+        if (v.size() == 0) {COST = 0;return;}
+	short x = 0,p;
+        for(p = 1;p < N; p <<= 1);
+	for(;p;p >>= 1)
+		if (!ver(v,x + p))
+		{
+			x += p;
+		}
+	x++;
+	ver(v,x);
+	COST = x;
+}
+void dfs(int nod)
+{
+	if (VER[nod]) return ;
+	VER[nod] = 1;
+	for(int i = 0;i < (int)VECT[nod].size(); ++i)
+	{
+                if (!VER[VECT[nod][i]]) TATA[VECT[nod][i]] = nod;
+		dfs(VECT[nod][i]);
+	}
+	VEC.clear();
+	for(int i = 0;i < (int)VECT[nod].size(); ++i)
+	{
+		if (VER[VECT[nod][i]] == 2)VEC.pb(mkp(VECT[nod][i],0));
+	}
+	for(int i = 0;i < N && VEC.size() > 0;++i)
+	{
+		solve(VEC);
+		D[nod][i] = COST;
+		M[nod][i] = MOVE;
+		for(int i = 0;i < (int)VEC.size(); ++i)
+		{
+			if (VEC[i].first == MOVE)
+			{
+				VEC[i] = VEC[VEC.size() - 1];
+				VEC.pop_back();
+			}
+			if (M[VEC[i].first][VEC[i].second] == MOVE) VEC[i].second += 1;
+		}
+	}
+	VER[nod] = 2;
+}
+int main()
+{
+	freopen("optic.in","r",stdin);
+	freopen("optic.out","w",stdout);
+	scanf("%d\n",&N);
+	for(int i = 1;i < N; ++i)
+	{
+		short x,y;
+		scanf("%hd %hd\n",&x,&y);
+                assert(x != 0 && y != 0);
+		VECT[x].pb(y);
+		VECT[y].pb(x);
+	}
+	dfs(1);
+        memset(VER,0,sizeof(VER));
+	printf("%d\n",D[1][0]);
+        ANS.pb(mkp(1,0));
+        VER[1] = 1;
+        for(int i = 1;i <= D[1][0]; ++i)
+        {
+                AUX.clear();
+                for(int j = 0;j < ANS.size(); ++j)
+                {
+                        if (VER[M[ANS[j].first][ANS[j].second]] == 0 && M[ANS[j].first][ANS[j].second])
+                        {
+                                AUX.pb(mkp(ANS[j].first,M[ANS[j].first][ANS[j].second]));
+                                VER[M[ANS[j].first][ANS[j].second]] = 1;
+                                ANS[j].second++;
+                        }
+                }
+                printf("%d\n",AUX.size());
+                for(int j = 0;j < AUX.size(); ++j)
+                {
+                        printf("%d %d\n",AUX[j].first,AUX[j].second);
+                        NRT = 0;
+                        int nod = AUX[j].second;
+                        for(NRT;VER[M[nod][NRT]];++NRT);
+                        ANS.pb(mkp(AUX[j].second,NRT));
+                }
+        }
+	return 0;
+}
+</code>

Razvan's wiki

User Tools

Site Tools

Differences

Page Tools