#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;
int A, B, M;
pii E[MAXM+10];
int CA[MAXN+10], CB[MAXN+10];
bool S[MAXM*2+10];
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[nxt.second]) continue;
S[nxt.second]=1;
dfs(nxt.first, nxt.second, 2);
}
}
else
{
for(auto &nxt : adj2[now])
{
if(S[nxt.second]) continue;
S[nxt.second]=1;
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;
int num=M+1;
for(auto &it : acomp) if(CA[it]%2)
{
adj1[it].push_back({0, num});
adj2[0].push_back({it, num});
num++;
cnt++;
}
for(auto &it : bcomp) if(CB[it]%2)
{
adj2[it].push_back({0, num});
adj1[0].push_back({it, num});
num++;
}
if(cnt%2)
{
adj1[0].push_back({0, num});
adj2[0].push_back({0, num});
num++;
}
acomp.push_back(0); bcomp.push_back(0);
for(auto it : acomp) dfs(it, -2, 1);
for(auto &it : V) S[it]=0;
for(i=M+1; i<num; i++) S[i]=0;
vector<int>().swap(V);
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]<=M)
{
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
teoreticar.cpp: In function 'void solve(std::vector<int>&, int&)':
teoreticar.cpp:125:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0; i<cir.size(); i++)
~^~~~~~~~~~~
teoreticar.cpp:47:9: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
teoreticar.cpp: In function 'int main()':
teoreticar.cpp:141:9: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
teoreticar.cpp:143: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:144: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 time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
4984 KB |
Output is correct |
| 2 |
Correct |
8 ms |
4984 KB |
Output is correct |
| 3 |
Correct |
8 ms |
4984 KB |
Output is correct |
| 4 |
Correct |
8 ms |
4984 KB |
Output is correct |
| 5 |
Correct |
8 ms |
4984 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
5112 KB |
Output is correct |
| 2 |
Correct |
8 ms |
4984 KB |
Output is correct |
| 3 |
Correct |
8 ms |
4984 KB |
Output is correct |
| 4 |
Correct |
8 ms |
4984 KB |
Output is correct |
| 5 |
Correct |
8 ms |
5112 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
5752 KB |
Output is correct |
| 2 |
Correct |
22 ms |
5624 KB |
Output is correct |
| 3 |
Correct |
39 ms |
5880 KB |
Output is correct |
| 4 |
Correct |
15 ms |
5496 KB |
Output is correct |
| 5 |
Correct |
12 ms |
5496 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
5784 KB |
Output is correct |
| 2 |
Correct |
22 ms |
5624 KB |
Output is correct |
| 3 |
Correct |
38 ms |
6008 KB |
Output is correct |
| 4 |
Correct |
14 ms |
5536 KB |
Output is correct |
| 5 |
Correct |
13 ms |
5368 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1928 ms |
45800 KB |
Output is correct |
| 2 |
Execution timed out |
12013 ms |
72188 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1956 ms |
45936 KB |
Output is correct |
| 2 |
Execution timed out |
12011 ms |
71012 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
12046 ms |
60712 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2826 ms |
53472 KB |
Output is correct |
| 2 |
Execution timed out |
12032 ms |
72204 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5033 ms |
43532 KB |
Output is correct |
| 2 |
Execution timed out |
12095 ms |
71908 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5461 ms |
43492 KB |
Output is correct |
| 2 |
Execution timed out |
12016 ms |
71908 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
