Submission #461141

#TimeUsernameProblemLanguageResultExecution timeMemory
461141grtTeoretičar (COCI18_teoreticar)C++17
52 / 130
2203 ms262144 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 = 1000 * 1000 + 10; int l, r, m; int deg[nax][2]; pi edge[nax]; vector<pi> V[nax][2]; int I[nax][2]; bool vis[nax]; int col[nax]; 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, int mx_deg) { if(a == b) { for(int i = 1; i <= l; ++i) { if((int)V[i][0].size() > 0) col[V[i][0][0].ND] = a; } return; } int ptr = 1; for(int i = 1; i <= l; ++i) { if((int)V[i][0].size() % 2 == 1) { while(V[ptr][1].size() == mx_deg) ptr++; nr++; V[i][0].emplace_back(ptr, nr); V[ptr][1].emplace_back(i, nr); edge[nr] = {i, ptr}; } } r = max(r, ptr); ptr = 1; for(int i = 1; i <= r; ++i) { if((int)V[i][1].size() % 2 == 1) { while(V[ptr][0].size() == mx_deg) ptr++; nr++; V[ptr][0].emplace_back(i, nr); V[i][1].emplace_back(ptr, nr); edge[nr] = {ptr, i}; } } l = max(l, ptr); 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 <= r; ++i) { V[i][1].swap(V2[i][1]); V2[i][1].clear(); } rec(a, (a + b)/2, mx_deg / 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 <= r; ++i) { V[i][1].swap(V2[i][1]); V2[i][1].clear(); } rec((a+b)/2 + 1, b, mx_deg / 2); } 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}); } 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; nr = m; rec(1, pt, pt); cout << pt << "\n"; for(int i = 1; i <= m; ++i) { cout << col[i] << "\n"; } }

Compilation message (stderr)

teoreticar.cpp: In function 'void rec(int, int, int)':
teoreticar.cpp:49:27: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   49 |    while(V[ptr][1].size() == mx_deg) ptr++;
      |          ~~~~~~~~~~~~~~~~~^~~~~~~~~
teoreticar.cpp:60:27: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   60 |    while(V[ptr][0].size() == mx_deg) ptr++;
      |          ~~~~~~~~~~~~~~~~~^~~~~~~~~
#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...