#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
typedef long long ll;
int l,r,m;
int kol=1;
map<pair<int,int>,int>ma;
void dfs(int g,vector<vector<int>>&b,vector<pair<int,int>>&a,vector<pair<int,int>>&j,vector<pair<int,int>>&d,int &c, vector<vector<int>>&czy)
{//cout<<"AAA"<<endl;
for(int i=0;i<b[g].size();i++)
{
while(czy[min(g,b[g][i])][max(g,b[g][i])]>0)
{
czy[min(g,b[g][i])][max(g,b[g][i])]--;
dfs(b[g][i],b,a,j,d,c,czy);
if(c==0)
{
if(min(g,b[g][i])>0)
{
pair<int,int> f;
f.st=min(g,b[g][i]);
f.nd=max(g,b[g][i]);
j.push_back(f);
}
}
else
{
if(min(g,b[g][i])>0)
{
pair<int,int> f;
f.st=min(g,b[g][i]);
f.nd=max(g,b[g][i]);
d.push_back(f);
}
}
c=(c+1)%2;
}
}
}
void q(vector<pair<int,int>>&a,vector<int>&wynik,vector<vector<int>>&czy)
{
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<b.size();i++)
{
if(b[i].size()>1)
{
p=false;
}
}
// cout<<"B"<<endl;
if(p)
{
for(int i=0;i<a.size();i++)
{
wynik[ma[a[i]]]=kol;
}
kol++;
// cout<<"P"<<endl;
return;
}
for(int i=0;i<b.size();i++)
{
if(b[i].size()%2==1)
{
b[i].push_back(0);
b[0].push_back(i);
czy[0][i]++;
}
}
for(int i=0;i<a.size();i++)
{
czy[a[i].st][a[i].nd]++;
}
vector<pair<int,int>>j;
vector<pair<int,int>>d;
// cout<<"A"<<endl;
int c=0;
for(int i=0;i<l+r+1;i++)
{
dfs(i,b,a,j,d,c,czy);
}
q(j,wynik,czy);
q(d,wynik,czy);
}
int main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>l>>r>>m;
vector<vector<int>>czy(l+1,vector<int>(l+r+1));
vector<pair<int,int>>a(m);
//cout<<"Q"<<endl;
for(int i=0;i<m;i++)
{
cin>>a[i].st>>a[i].nd;
a[i].nd+=l;
ma[a[i]]=i;
}
vector<int>wynik(m,0);
q(a,wynik,czy);
cout<<kol-1<<endl;
for(int i=0;i<m;i++)
{
cout<<wynik[i]<<endl;
}
}
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<std::pair<int, int> >&, int&, std::vector<std::vector<int> >&)':
teoreticar.cpp:12:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
12 | for(int i=0;i<b[g].size();i++)
| ~^~~~~~~~~~~~
teoreticar.cpp: In function 'void q(std::vector<std::pair<int, int> >&, std::vector<int>&, std::vector<std::vector<int> >&)':
teoreticar.cpp:46: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]
46 | for(int i=0;i<a.size();i++)
| ~^~~~~~~~~
teoreticar.cpp:52:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for(int i=0;i<b.size();i++)
| ~^~~~~~~~~
teoreticar.cpp:62: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]
62 | 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=0;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 |
604 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
58 ms |
73360 KB |
Output is correct |
2 |
Correct |
32 ms |
10076 KB |
Output is correct |
3 |
Correct |
136 ms |
145020 KB |
Output is correct |
4 |
Correct |
10 ms |
9560 KB |
Output is correct |
5 |
Correct |
10 ms |
9600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
50 ms |
3252 KB |
Output is correct |
2 |
Correct |
32 ms |
10172 KB |
Output is correct |
3 |
Correct |
159 ms |
199896 KB |
Output is correct |
4 |
Correct |
11 ms |
4704 KB |
Output is correct |
5 |
Correct |
7 ms |
1692 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
96 ms |
262144 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
97 ms |
262144 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
12036 ms |
128232 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4794 ms |
145352 KB |
Output is correct |
2 |
Runtime error |
93 ms |
262144 KB |
Execution killed with signal 9 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
12027 ms |
173828 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8068 ms |
105012 KB |
Output is correct |
2 |
Runtime error |
93 ms |
262144 KB |
Execution killed with signal 9 |
3 |
Halted |
0 ms |
0 KB |
- |