Submission #204792

#TimeUsernameProblemLanguageResultExecution timeMemory
204792arnold518Teoretičar (COCI18_teoreticar)C++14
52 / 130
12073 ms30192 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXN = 2e5; const int MAXM = 5e5; int A, B, M; pii E[MAXN+10]; int CA[MAXN+10], CB[MAXN+10]; set<pii> S; vector<pii> adj1[MAXN+10], adj2[MAXN+10]; vector<int> cir; int ans[MAXM+10]; void dfs(int now, int edge, int col) { if(col==1) { for(auto &nxt : adj1[now]) { if(S.count({now, nxt.first})) continue; S.insert({now, nxt.first}); dfs(nxt.first, nxt.second, 2); } } else { for(auto &nxt : adj2[now]) { if(S.count({nxt.first, now})) continue; S.insert({nxt.first, now}); dfs(nxt.first, nxt.second, 1); } } if(edge!=-2) cir.push_back(edge); } void solve(vector<int> &V, int &k) { int i, j; vector<int> acomp, bcomp; for(auto &it : V) { acomp.push_back(E[it].first); bcomp.push_back(E[it].second); CA[E[it].first]++; CB[E[it].second]++; } sort(acomp.begin(), acomp.end()); acomp.erase(unique(acomp.begin(), acomp.end()), acomp.end()); sort(bcomp.begin(), bcomp.end()); bcomp.erase(unique(bcomp.begin(), bcomp.end()), bcomp.end()); int maxdeg=0; for(auto &it : acomp) maxdeg=max(maxdeg, CA[it]); for(auto &it : bcomp) maxdeg=max(maxdeg, CB[it]); if(maxdeg<=1) { for(auto &it : V) ans[it]=k; for(auto &it : acomp) CA[it]=0; for(auto &it : bcomp) CB[it]=0; vector<int>().swap(V); vector<int>().swap(acomp); vector<int>().swap(bcomp); k++; return; } for(auto &it : V) { adj1[E[it].first].push_back({E[it].second, it}); adj2[E[it].second].push_back({E[it].first, it}); } int cnt=0; for(auto &it : acomp) if(CA[it]%2) { adj1[it].push_back({0, -1}); adj2[0].push_back({it, -1}); cnt++; } for(auto &it : bcomp) if(CB[it]%2) { adj2[it].push_back({0, -1}); adj1[0].push_back({it, -1}); } if(cnt%2) { adj1[0].push_back({0, -1}); adj2[0].push_back({0, -1}); } vector<int>().swap(V); acomp.push_back(0); bcomp.push_back(0); for(auto it : acomp) dfs(it, -2, 1); S.clear(); for(auto &it : acomp) CA[it]=0; for(auto &it : bcomp) CB[it]=0; for(auto &it : acomp) vector<pii>().swap(adj1[it]); for(auto &it : bcomp) vector<pii>().swap(adj2[it]); vector<int>().swap(acomp); vector<int>().swap(bcomp); vector<int> L, R; for(i=0; i<cir.size(); i++) { if(cir[i]!=-1) { if(i%2) L.push_back(cir[i]); else R.push_back(cir[i]); } } vector<int>().swap(cir); solve(L, k); solve(R, k); } int main() { int i, j; scanf("%d%d%d", &A, &B, &M); for(i=1; i<=M; i++) scanf("%d%d", &E[i].first, &E[i].second); vector<int> V; for(i=1; i<=M; i++) V.push_back(i); int ans2=1; solve(V, ans2); printf("%d\n", ans2-1); for(i=1; i<=M; i++) printf("%d\n", ans[i]); }

Compilation message (stderr)

teoreticar.cpp: In function 'void solve(std::vector<int>&, int&)':
teoreticar.cpp:118:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0; i<cir.size(); i++)
           ~^~~~~~~~~~~
teoreticar.cpp:46:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
teoreticar.cpp: In function 'int main()':
teoreticar.cpp:134:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
teoreticar.cpp:136:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &A, &B, &M);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
teoreticar.cpp:137:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=M; i++) scanf("%d%d", &E[i].first, &E[i].second);
                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...