This is an old revision of the document!
= Marius Dragus = *Nume complet: Dragus Marius Ioan *Alias-uri: DMI *Data/locul nașterii: 14 octombrie 1990,Cluj-Napoca
*2005-2009 Liceul International de informatica Bucuresti *2009-prezent Universitatea Politehnica Bucuresti
*sunt smecher ce sa mai….
#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; }