This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e5;
const int MAXM = 5e5;
struct Edge
{
int u, v, p;
bool operator < (const Edge &q) const { return v<q.v; }
};
int A, B, M;
vector<Edge> E;
int CA[MAXN+10], CB[MAXN+10];
set<Edge> adj[MAXN*2+10];
vector<Edge> cir;
int ans[MAXM+10];
void dfs(int now, Edge bef)
{
vector<Edge> V;
for(auto it : adj[now]) V.push_back(it);
for(auto it : V)
{
if(adj[now].find(it)==adj[now].end()) continue;
adj[now].erase(it);
adj[it.v].erase({it.v, it.u, it.p});
dfs(it.v, it);
}
if(bef.p!=-2)
{
if(bef.v>=A+1) cir.push_back({bef.u, bef.v-A-1, bef.p});
else cir.push_back({bef.v, bef.u-A-1, bef.p});
}
}
void solve(vector<Edge> &V, int &k)
{
int i, j;
vector<int> acomp, bcomp;
for(auto it : V)
{
acomp.push_back(it.u);
bcomp.push_back(it.v);
CA[it.u]++; CB[it.v]++;
}
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.p]=k;
for(auto it : acomp) CA[it]=0;
for(auto it : bcomp) CB[it]=0;
vector<Edge>().swap(V);
vector<int>().swap(acomp);
vector<int>().swap(bcomp);
k++; return;
}
int cnt=0;
for(auto it : acomp) if(CA[it]%2) V.push_back({it, 0, -1}), cnt++;
for(auto it : bcomp) if(CB[it]%2) V.push_back({0, it, -1});
if(cnt%2) V.push_back({0, 0, -1});
for(auto it : V)
{
adj[it.u].insert({it.u, it.v+A+1, it.p});
adj[it.v+A+1].insert({it.v+A+1, it.u, it.p});
}
vector<Edge>().swap(V);
acomp.push_back(0);
for(auto it : acomp) dfs(it, {-1, -1, -2});
for(auto it : acomp) CA[it]=0;
for(auto it : bcomp) CB[it]=0;
vector<int>().swap(acomp);
vector<int>().swap(bcomp);
vector<Edge> L, R;
for(i=0; i<cir.size(); i++)
{
if(cir[i].p!=-1)
{
if(i%2) L.push_back(cir[i]);
else R.push_back(cir[i]);
}
}
vector<Edge>().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++)
{
int u, v;
scanf("%d%d", &u, &v);
E.push_back({u, v, i});
}
int ans2=1;
solve(E, 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<Edge>&, int&)':
teoreticar.cpp:101: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:117:9: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
teoreticar.cpp:119: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:123:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &u, &v);
~~~~~^~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |