#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
typedef long long ll;
int l,r,m;
int kol=1;
int c=0;
map<pair<int,int>,int>ma;
int wynik[500000];
void dfs(int g,vector<vector<int>>&b,vector<pair<int,int>>&j,vector<pair<int,int>>&d, vector<bool>&czy,vector<bool>&czy2)
{
for(int i=0;i<b[g].size();i++)
{
if(min(g,b[g][i])==0)
{
if(czy2[max(g,b[g][i])]==true)
{
czy2[max(g,b[g][i])]=false;
dfs(b[g][i],b,j,d,czy,czy2);
c=(c+1)%2;
}
}
else
{
if(czy[ma[{min(g,b[g][i]),max(g,b[g][i])}]]==true)
{
czy[ma[{min(g,b[g][i]),max(g,b[g][i])}]]=false;
dfs(b[g][i],b,j,d,czy,czy2);
if(c==0)
{
j.push_back({min(g,b[g][i]),max(g,b[g][i])});
}
else
{
d.push_back({min(g,b[g][i]),max(g,b[g][i])});
}
c=(c+1)%2;
}
}
}
}
void q(vector<pair<int,int>>&a,vector<bool>&czy,vector<bool>&czy2)
{
vector<vector<int>>b(l+r+1);
for(int i=0;i<a.size();i++)
{
b[a[i].nd].push_back(a[i].st);
b[a[i].st].push_back(a[i].nd);
}
bool p=true;
for(int i=0;i<a.size();i++)
{
if(b[a[i].st].size()>1 or b[a[i].nd].size()>1)
{
p=false;
break;
}
}
if(p)
{
for(int i=0;i<a.size();i++)
{
wynik[ma[a[i]]]=kol;
}
kol++;
return;
}
for(int i=1;i<b.size();i++)
{
if(b[i].size()%2==1)
{
b[i].push_back(0);
b[0].push_back(i);
czy2[i]=true;;
}
}
for(int i=0;i<a.size();i++)
{
czy[ma[a[i]]]=true;
}
vector<pair<int,int>>j;
vector<pair<int,int>>d;
for(int i=0;i<l+r+1;i++)
{
dfs(i,b,j,d,czy,czy2);
}
q(j,czy,czy2);
q(d,czy,czy2);
}
int main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>l>>r>>m;
vector<bool>czy(m);
vector<bool>czy2(l+r+1);
vector<pair<int,int>>a(m);
for(int i=0;i<m;i++)
{
cin>>a[i].st>>a[i].nd;
a[i].nd+=l;
ma[a[i]]=i;
}
q(a,czy,czy2);
cout<<kol-1<<endl;
for(int i=0;i<m;i++)
{
cout<<wynik[i]<<'\n';
}
}
Compilation message
teoreticar.cpp: In function 'void dfs(int, std::vector<std::vector<int> >&, std::vector<std::pair<int, int> >&, std::vector<std::pair<int, int> >&, std::vector<bool>&, std::vector<bool>&)':
teoreticar.cpp:13:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
13 | for(int i=0;i<b[g].size();i++)
| ~^~~~~~~~~~~~
teoreticar.cpp: In function 'void q(std::vector<std::pair<int, int> >&, std::vector<bool>&, std::vector<bool>&)':
teoreticar.cpp:47:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for(int i=0;i<a.size();i++)
| ~^~~~~~~~~
teoreticar.cpp:53:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for(int i=0;i<a.size();i++)
| ~^~~~~~~~~
teoreticar.cpp:63:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for(int i=0;i<a.size();i++)
| ~^~~~~~~~~
teoreticar.cpp:70:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | for(int i=1;i<b.size();i++)
| ~^~~~~~~~~
teoreticar.cpp:79:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | for(int i=0;i<a.size();i++)
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
2764 KB |
Output is correct |
| 2 |
Correct |
47 ms |
2152 KB |
Output is correct |
| 3 |
Correct |
92 ms |
3752 KB |
Output is correct |
| 4 |
Correct |
8 ms |
1628 KB |
Output is correct |
| 5 |
Correct |
8 ms |
1628 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
103 ms |
2876 KB |
Output is correct |
| 2 |
Correct |
38 ms |
2136 KB |
Output is correct |
| 3 |
Correct |
98 ms |
3924 KB |
Output is correct |
| 4 |
Correct |
15 ms |
1884 KB |
Output is correct |
| 5 |
Correct |
14 ms |
1112 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6511 ms |
118268 KB |
Output is correct |
| 2 |
Execution timed out |
12066 ms |
139556 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6495 ms |
118268 KB |
Output is correct |
| 2 |
Execution timed out |
12090 ms |
147840 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
12032 ms |
53976 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
12091 ms |
79700 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
12010 ms |
49236 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
12050 ms |
51452 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
