#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
const int maxN = 5e5 + 10;
struct Node
{
int to, next;
}edge[maxN * 5 + 1];
int L, R, M, n, cnt, col;
int tot, head[maxN + 1];
int tl[maxN + 1], tr[maxN + 1];
int dl[maxN + 1], dr[maxN + 1];
int ans[maxN + 1], stk[maxN * 5 + 1], top;
bool vis[maxN * 5 + 1];
vector<pii> E[maxN * 2 + 1];
vector<int> vl[maxN * 2 + 1], vr[maxN * 2 + 1];
map<pii, int> G;
inline void clear(int node)
{
for(int i = 2; i <= tot; i++) vis[i] = false;
for(int i = 0; i < vl[node].size(); i++)
{
int x = vl[node][i];
dl[x] = head[x] = 0;
}
for(int i = 0; i < vr[node].size(); i++)
{
int x = vr[node][i] + n;
dr[x - n] = head[x] = 0;
}
head[2 * n + 1] = head[2 * n + 2] = 0;
tot = 1;
}
inline void add(int x, int y)
{
edge[++ tot] = (Node){y, head[x]}; head[x] = tot;
edge[++ tot] = (Node){x, head[y]}; head[y] = tot;
}
inline void dfs(int u)
{
for(int &i = head[u]; i; i = edge[i].next)
{
if(vis[i]) continue;
vis[i] = vis[i ^ 1] = true;
dfs(edge[i].to);
}
stk[++ top] = u;
}
inline void solve(int node)
{
for(int i = 0; i < E[node].size(); i++)
{
int u = E[node][i].first, v = E[node][i].second;
add(u, v + n);
dl[u] ++, dr[v] ++;
}
bool flag = true;
for(int i = 0; i < vl[node].size(); i++)
if(dl[ vl[node][i] ] > 1) { flag = false; break; }
for(int i = 0; i < vr[node].size(); i++)
if(dr[ vr[node][i] ] > 1) { flag = false; break; }
if(flag)
{
col ++;
for(int i = 0; i < E[node].size(); i++) ans[ G[ E[node][i] ] ] = col;
clear(node);
return;
};
int d1 = 0, d2 = 0;
for(int i = 0; i < vl[node].size(); i++)
if(dl[ vl[node][i] ] & 1) add(vl[node][i], 2 * n + 2), d2 ++;
for(int i = 0; i < vr[node].size(); i++)
if(dr[ vr[node][i] ] & 1) add(2 * n + 1, vr[node][i] + n), d1 ++;
if(d1 & 1) add(2 * n + 1, 2 * n + 2);
int nl = ++ cnt, nr = ++ cnt;
for(int i = 0; i < vl[node].size(); i++)
{
top = 0;
dfs(vl[node][i]);
while(top > 1)
{
int u = stk[top], v = stk[top - 1];
top --;
if(u > 2 * n || v > 2 * n) continue;
if(u > n) swap(u, v);
v -= n;
if(top & 1) E[nl].push_back( pii(u, v) );
else E[nr].push_back( pii(u, v) );
}
}
clear(node);
for(int i = 0; i < E[nl].size(); i++)
tl[ E[nl][i].first ] = tr[ E[nl][i].second ] = nl;
for(int i = 0; i < vl[node].size(); i++)
if(tl[ vl[node][i] ] == nl) vl[nl].push_back(vl[node][i]);
for(int i = 0; i < vr[node].size(); i++)
if(tr[ vr[node][i] ] == nl) vr[nl].push_back(vr[node][i]);
for(int i = 0; i < E[nr].size(); i++)
tl[ E[nr][i].first ] = tr[ E[nr][i].second ] = nr;
for(int i = 0; i < vl[node].size(); i++)
if(tl[ vl[node][i] ] == nr) vl[nr].push_back(vl[node][i]);
for(int i = 0; i < vr[node].size(); i++)
if(tr[ vr[node][i] ] == nr) vr[nr].push_back(vr[node][i]);
solve(nl), solve(nr);
}
int main()
{
scanf("%d %d %d", &L, &R, &M);
n = max(L, R);
cnt ++;
for(int i = 1; i <= M; i++)
{
int x, y;
scanf("%d %d", &x, &y);
G[ pii(x, y) ] = i;
E[cnt].push_back( pii(x, y) );
dl[x] ++, dr[y] ++;
}
for(int i = 1; i <= L; i++)
if(dl[i]) vl[cnt].push_back(i);
for(int i = 1; i <= R; i++)
if(dr[i]) vr[cnt].push_back(i);
for(int i = 1; i <= L; i++) dl[i] = 0;
for(int i = 1; i <= R; i++) dr[i] = 0;
tot = 1;
solve(1);
printf("%d\n", col);
for(int i = 1; i <= M; i++) printf("%d\n", ans[i]);
return 0;
}
Compilation message
teoreticar.cpp: In function 'void clear(int)':
teoreticar.cpp:28:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | for(int i = 0; i < vl[node].size(); i++)
| ~~^~~~~~~~~~~~~~~~~
teoreticar.cpp:33:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | for(int i = 0; i < vr[node].size(); i++)
| ~~^~~~~~~~~~~~~~~~~
teoreticar.cpp: In function 'void solve(int)':
teoreticar.cpp:61:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for(int i = 0; i < E[node].size(); i++)
| ~~^~~~~~~~~~~~~~~~
teoreticar.cpp:68:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for(int i = 0; i < vl[node].size(); i++)
| ~~^~~~~~~~~~~~~~~~~
teoreticar.cpp:70:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | for(int i = 0; i < vr[node].size(); i++)
| ~~^~~~~~~~~~~~~~~~~
teoreticar.cpp:75:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for(int i = 0; i < E[node].size(); i++) ans[ G[ E[node][i] ] ] = col;
| ~~^~~~~~~~~~~~~~~~
teoreticar.cpp:80:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for(int i = 0; i < vl[node].size(); i++)
| ~~^~~~~~~~~~~~~~~~~
teoreticar.cpp:82:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | for(int i = 0; i < vr[node].size(); i++)
| ~~^~~~~~~~~~~~~~~~~
teoreticar.cpp:86:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | for(int i = 0; i < vl[node].size(); i++)
| ~~^~~~~~~~~~~~~~~~~
teoreticar.cpp:102:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | for(int i = 0; i < E[nl].size(); i++)
| ~~^~~~~~~~~~~~~~
teoreticar.cpp:104:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | for(int i = 0; i < vl[node].size(); i++)
| ~~^~~~~~~~~~~~~~~~~
teoreticar.cpp:106:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | for(int i = 0; i < vr[node].size(); i++)
| ~~^~~~~~~~~~~~~~~~~
teoreticar.cpp:108:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | for(int i = 0; i < E[nr].size(); i++)
| ~~^~~~~~~~~~~~~~
teoreticar.cpp:110:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | for(int i = 0; i < vl[node].size(); i++)
| ~~^~~~~~~~~~~~~~~~~
teoreticar.cpp:112:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
112 | for(int i = 0; i < vr[node].size(); i++)
| ~~^~~~~~~~~~~~~~~~~
teoreticar.cpp: In function 'int main()':
teoreticar.cpp:119:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
119 | scanf("%d %d %d", &L, &R, &M);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
teoreticar.cpp:125:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
125 | scanf("%d %d", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
70892 KB |
Output is correct |
| 2 |
Correct |
48 ms |
70892 KB |
Output is correct |
| 3 |
Correct |
46 ms |
70892 KB |
Output is correct |
| 4 |
Correct |
47 ms |
71040 KB |
Output is correct |
| 5 |
Correct |
48 ms |
70892 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
70820 KB |
Output is correct |
| 2 |
Correct |
46 ms |
70892 KB |
Output is correct |
| 3 |
Correct |
49 ms |
70892 KB |
Output is correct |
| 4 |
Correct |
46 ms |
70892 KB |
Output is correct |
| 5 |
Correct |
46 ms |
70892 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
52 ms |
72172 KB |
Output is correct |
| 2 |
Correct |
52 ms |
72044 KB |
Output is correct |
| 3 |
Correct |
55 ms |
72428 KB |
Output is correct |
| 4 |
Correct |
50 ms |
71660 KB |
Output is correct |
| 5 |
Correct |
50 ms |
71660 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
72576 KB |
Output is correct |
| 2 |
Correct |
53 ms |
72044 KB |
Output is correct |
| 3 |
Correct |
55 ms |
72556 KB |
Output is correct |
| 4 |
Correct |
53 ms |
71788 KB |
Output is correct |
| 5 |
Correct |
51 ms |
71532 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1012 ms |
139856 KB |
Output is correct |
| 2 |
Correct |
2608 ms |
246868 KB |
Output is correct |
| 3 |
Correct |
1690 ms |
180128 KB |
Output is correct |
| 4 |
Correct |
1071 ms |
149864 KB |
Output is correct |
| 5 |
Correct |
870 ms |
140500 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1048 ms |
139992 KB |
Output is correct |
| 2 |
Correct |
1741 ms |
179924 KB |
Output is correct |
| 3 |
Correct |
1980 ms |
208364 KB |
Output is correct |
| 4 |
Correct |
1120 ms |
149716 KB |
Output is correct |
| 5 |
Correct |
232 ms |
92896 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2348 ms |
262144 KB |
Output is correct |
| 2 |
Correct |
2221 ms |
213076 KB |
Output is correct |
| 3 |
Correct |
158 ms |
88932 KB |
Output is correct |
| 4 |
Correct |
1351 ms |
171476 KB |
Output is correct |
| 5 |
Correct |
410 ms |
109404 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1664 ms |
197716 KB |
Output is correct |
| 2 |
Correct |
2788 ms |
255316 KB |
Output is correct |
| 3 |
Correct |
2237 ms |
224596 KB |
Output is correct |
| 4 |
Correct |
1410 ms |
170680 KB |
Output is correct |
| 5 |
Correct |
1060 ms |
149960 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1431 ms |
197336 KB |
Output is correct |
| 2 |
Runtime error |
2683 ms |
262144 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1506 ms |
197524 KB |
Output is correct |
| 2 |
Runtime error |
2683 ms |
262144 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
