#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
constexpr int N = 1e5;
constexpr int M = 5e5;
constexpr int K = 18;
struct kraw{
int nr;
int a;
int b;
};
vector<kraw> krawedzie[(1<<K)+9];
bool zmien[M+9];
int deg[2*N+9];
vector<pair<int,int>> graf[2*N+9];
int gdzie[M+9];
int odp[M+9];
bool bylo[M+9];
int ter;
void dfs(int v){
while(!graf[v].empty()){
pair<int,int> temp = graf[v].back(); graf[v].pop_back();
if (bylo[temp.second]) continue;
bylo[temp.second] = 1;
dfs(temp.first);
if (temp.second!=-1) gdzie[temp.second] = ter%2;
ter++;
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int l,r,m,a,b;
cin >> l >> r >> m;
for (int x=0;x<m;x++){
cin >> a >> b;
b += l;
kraw temp; temp.nr = x; temp.a = a; temp.b = b;
krawedzie[0].push_back(temp);
}
set<int> sed;
vector<int> ind;
int pot=0;
for (int k=0;k<K;k++){
bool ok=1;
for (int kol=0;kol<(1<<k);kol++){
for (kraw x:krawedzie[kol]){
deg[x.a] = 0; deg[x.b] = 0;
}
for (kraw x:krawedzie[kol]){
deg[x.a]++; deg[x.b]++;
}
for (kraw x:krawedzie[kol]){
if (deg[x.a]>1 || deg[x.b]>1) ok = 0;
}
}
if (ok){
pot = k;
break;
}
for (int kol=0;kol<(1<<k);kol++){
if (krawedzie[kol].empty()) continue;
sed.clear();
for (int x=0;x<krawedzie[kol].size();x++){
sed.insert(krawedzie[kol][x].a);
sed.insert(krawedzie[kol][x].b);
}
ind.clear();
for (int x:sed){
ind.push_back(x);
deg[x] = 0;
graf[x].clear();
}
for (kraw x:krawedzie[kol]){
zmien[x.nr] = 0;
deg[x.a]++;
deg[x.b]++;
graf[x.a].push_back({x.b,x.nr});
graf[x.b].push_back({x.a,x.nr});
bylo[x.nr] = 0;
}
graf[l+r+1].clear(); deg[l+r+1] = 0;
graf[l+r+2].clear(); deg[l+r+2] = 0;
for (int x:ind){
if (deg[x]%2==1){
if (x<=l){
graf[l+r+2].push_back({x,-1});
graf[x].push_back({l+r+2,-1});
deg[x]++;
deg[l+r+2]++;
}
else{
graf[l+r+1].push_back({x,-1});
graf[x].push_back({l+r+1,-1});
deg[x]++;
deg[l+r+1]++;
}
}
}
if (deg[l+r+1]%2==1){
graf[l+r+2].push_back({l+r+1,-1});
graf[l+r+1].push_back({l+r+2,-1});
deg[l+r+1]++;
deg[l+r+2]++;
}
ter = 0;
dfs(ind[0]);
vector<kraw> kop = krawedzie[kol]; krawedzie[kol].clear();
for (kraw x:kop){
if (gdzie[x.nr] == 0){
krawedzie[kol].push_back(x);
}
else{
krawedzie[kol + (1<<k)].push_back(x);
}
}
}
}
for (int x=0;x<(1<<K);x++){
for (kraw y:krawedzie[x]){
if (y.nr != -1) odp[y.nr] = x+1;
}
}
cout << (1<<pot) << '\n';
for (int x=0;x<m;x++) cout << odp[x] << '\n';
return 0;
}
Compilation message
teoreticar.cpp: In function 'int main()':
teoreticar.cpp:68:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<kraw>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for (int x=0;x<krawedzie[kol].size();x++){
| ~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
11176 KB |
Integer 32767 violates the range [1, 1] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
11220 KB |
Integer 2049 violates the range [1, 1] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
12488 KB |
Integer 262143 violates the range [1, 1] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
12240 KB |
Integer 262144 violates the range [1, 1] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3975 ms |
92432 KB |
Integer 262144 violates the range [1, 1] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3933 ms |
92312 KB |
Integer 262144 violates the range [1, 1] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3208 ms |
108720 KB |
Integer 4 violates the range [1, 1] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1968 ms |
107496 KB |
Integer 262050 violates the range [1, 1] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1425 ms |
89236 KB |
Integer 262123 violates the range [1, 1] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1439 ms |
89324 KB |
Integer 38 violates the range [1, 1] |
| 2 |
Halted |
0 ms |
0 KB |
- |
