This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
rosedu:cdl:marius-dragus [2010/03/27 10:01] mdragus |
rosedu:cdl:marius-dragus [2010/03/27 10:16] mdragus |
||
---|---|---|---|
Line 11: | Line 11: | ||
== Link-uri spre alti oameni smecheri == | == Link-uri spre alti oameni smecheri == | ||
- | [[cdl: | + | [[rosedu:cdl:mircea-ghideu|Mircea |
+ | |||
+ | [[rosedu: | ||
+ | |||
+ | ==Acum niste cod baby== | ||
+ | < | ||
+ | # | ||
+ | # | ||
+ | # | ||
+ | #define pb push_back | ||
+ | #define mkp make_pair | ||
+ | |||
+ | using namespace std; | ||
+ | const int maxn = 340; | ||
+ | |||
+ | vector< | ||
+ | vector< | ||
+ | short N, | ||
+ | short VER[maxn]; | ||
+ | short NRT, | ||
+ | short D[maxn][maxn], | ||
+ | |||
+ | bool cmpf(pair< | ||
+ | { | ||
+ | short n1 = p1.first; | ||
+ | short n2 = p2.first; | ||
+ | short i1 = p1.second; | ||
+ | short i2 = p2.second; | ||
+ | for(;i1 <= N && i2 <= N; | ||
+ | { | ||
+ | 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< | ||
+ | { | ||
+ | sort(v1.begin(), | ||
+ | MOVE = 0; | ||
+ | for(int i = v1.size() - 1; | ||
+ | { | ||
+ | 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(); | ||
+ | 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], | ||
+ | // | ||
+ | continue; | ||
+ | } | ||
+ | } | ||
+ | if (timp < 0) return false; | ||
+ | return true; | ||
+ | } | ||
+ | |||
+ | void solve(vector< | ||
+ | { | ||
+ | if (v.size() == 0) {COST = 0; | ||
+ | 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, | ||
+ | COST = x; | ||
+ | } | ||
+ | |||
+ | void dfs(int nod) | ||
+ | { | ||
+ | if (VER[nod]) return ; | ||
+ | VER[nod] = 1; | ||
+ | for(int i = 0;i < (int)VECT[nod].size(); | ||
+ | { | ||
+ | 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(); | ||
+ | { | ||
+ | if (VER[VECT[nod][i]] == 2)VEC.pb(mkp(VECT[nod][i], | ||
+ | } | ||
+ | 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(); | ||
+ | { | ||
+ | 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(" | ||
+ | freopen(" | ||
+ | scanf(" | ||
+ | for(int i = 1;i < N; ++i) | ||
+ | { | ||
+ | short x,y; | ||
+ | scanf(" | ||
+ | assert(x != 0 && y != 0); | ||
+ | VECT[x].pb(y); | ||
+ | VECT[y].pb(x); | ||
+ | } | ||
+ | dfs(1); | ||
+ | |||
+ | memset(VER, | ||
+ | printf(" | ||
+ | ANS.pb(mkp(1, | ||
+ | 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, | ||
+ | VER[M[ANS[j].first][ANS[j].second]] = 1; | ||
+ | ANS[j].second++; | ||
+ | } | ||
+ | } | ||
+ | printf(" | ||
+ | for(int j = 0;j < AUX.size(); ++j) | ||
+ | { | ||
+ | printf(" | ||
+ | NRT = 0; | ||
+ | int nod = AUX[j].second; | ||
+ | for(NRT; | ||
+ | ANS.pb(mkp(AUX[j].second, | ||
+ | } | ||
+ | } | ||
+ | |||
+ | return 0; | ||
+ | } | ||
+ | |||
+ | </ | ||
+ | |||
+ | ==Si un tabel cu giberis== | ||
+ | |||
+ | ^Ceva ^Blablabla ^altceva ^ | ||
+ | |caca |maca|nata| | ||
+ | |gata|cu|rimele| | ||
+ |