Submission #460905

#TimeUsernameProblemLanguageResultExecution timeMemory
460905grtTeoretičar (COCI18_teoreticar)C++17
0 / 130
1091 ms107892 KiB
#include <bits/stdc++.h> #define PB push_back #define ST first #define ND second #define _ ios_base::sync_with_stdio(0); cin.tie(0); //mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); using namespace std; using ll = long long; using pi = pair<int,int>; using vi = vector<int>; const int nax = 200 * 1000 + 10; int l, r, m; int deg[nax][2]; pi edge[1000 * 1000 + 10]; vector<pi> V[nax][2]; int I[nax][2]; bool vis[1000 * 1000 + 10]; int col[1000 * 1000 + 10]; int nr; vi cycle; void eulerCycle(int x, bool turn) { while(I[x][turn] < (int)V[x][turn].size()) { auto nbh = V[x][turn][I[x][turn]++]; if(!vis[nbh.ND]) { vis[nbh.ND] = true; eulerCycle(nbh.ST, turn^1); cycle.PB(nbh.ND); } } } vector<pi>V2[nax][2]; void rec(int a, int b) { if(a == b) { for(int i = 1; i <= l; ++i) { col[V[i][0][0].ND] = a; } return; } for(int i = 1; i <= l; ++i) { I[i][0] = 0; for(auto nbh : V[i][0]) { vis[nbh.ND] = false; } } for(int i = 1; i <= r; ++i) { I[i][1] = 0; } cycle.clear(); for(int i = 1; i <= l; ++i) { eulerCycle(i, 0); } vi cyc = cycle; for(int i = 0; i < (int)cyc.size(); i += 2) { V2[edge[cyc[i]].ST][0].PB({edge[cyc[i]].ND, cyc[i]}); V2[edge[cyc[i]].ND][1].PB({edge[cyc[i]].ST, cyc[i]}); } for(int i = 1; i <= l; ++i) { V[i][0].swap(V2[i][0]); V2[i][0].clear(); } for(int i = 1; i <= l; ++i) { V[i][1].swap(V2[i][1]); V2[i][1].clear(); } rec(a, (a + b)/2); for(int i = 1; i < (int)cyc.size(); i += 2) { V2[edge[cyc[i]].ST][0].PB({edge[cyc[i]].ND, cyc[i]}); V2[edge[cyc[i]].ND][1].PB({edge[cyc[i]].ST, cyc[i]}); } for(int i = 1; i <= l; ++i) { V[i][0].swap(V2[i][0]); V2[i][0].clear(); } for(int i = 1; i <= l; ++i) { V[i][1].swap(V2[i][1]); V2[i][1].clear(); } rec((a+b)/2 + 1, b); } int main() {_ cin >> l >> r >> m; for(int a, b, i = 1; i <= m; ++i) { cin >> a >> b; edge[i] = {a, b}; deg[a][0]++; deg[b][1]++; V[a][0].PB({b, i}); V[b][1].PB({a, i}); //cout << i << ": " << a << " " << b << "\n"; } int mx = 0; for(int i = 1; i <= l; ++i) { mx = max(mx, deg[i][0]); } for(int i = 1; i <= r; ++i) { mx = max(mx, deg[i][1]); } int pt = 1; while(pt < mx) pt *= 2; int ptr = 1; nr = m; for(int i = 1; i <= l || deg[ptr][1] != pt; ++i) { l = max(l, i); while(deg[i][0] != pt) { while(deg[ptr][1] == pt) ptr++; deg[ptr][1]++; deg[i][0]++; nr++; V[i][0].PB({ptr, nr}); V[ptr][1].PB({i, nr}); //cout << nr << ": " << i << " " << ptr << "\n"; edge[nr] = {i, ptr}; } } r = max(r, ptr); rec(1, pt); for(int i = 1; i <= m; ++i) { cout << col[i] << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...