#include <bits/stdc++.h>
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;
const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod=1000000007;
const int MAXN=100010, LOG=20;
int n, nn, m, k, u, v, x, y, t, a, b;
int A[MAXN*2], deg[MAXN*2];
int E[MAXN*5][2];
int P[MAXN*5], color[MAXN*5], pw;
bool mark[MAXN*5];
vector<int> G[MAXN];
void tour(int node){
while (G[node].size()){
int id=G[node].back();
G[node].pop_back();
if (mark[id]) continue ;
mark[id]=1;
int v=(node^E[id][0]^E[id][1]);
deg[node]--;
deg[v]--;
if (node<n) color[id]|=(1<<pw);
//debug(id)
// add edge
tour(v);
return ;
}
}
void Solve(int tl, int tr){
memset(deg, 0, sizeof(deg));
bool good=1;
for (int i=tl; i<tr; i++){
mark[P[i]]=0;
for (int t:{0, 1}){
G[E[P[i]][t]].pb(P[i]);
if (deg[E[P[i]][t]]++) good=0;
}
}
if (good) return ;
/*
debug2(tl, tr)
for (int i=tl; i<tr; i++) debug2(P[i], color[P[i]])
debug(pw)
cerr<<'\n';
*/
for (int i=tl; i<tr; i++) for (int t:{0, 1}){
if (deg[E[P[i]][t]]&1) tour(E[P[i]][t]);
}
for (int i=tl; i<tr; i++) for (int t:{0, 1}){
tour(E[P[i]][t]);
}
for (int i=tl; i<tr; i++) mark[P[i]]=1;
sort(P+tl, P+tr, [](int i, int j){
return color[i]<color[j];
});
for (int i=tl+1; i<tr; i++) if (color[P[i]]!=color[P[i-1]]){
pw++;
Solve(tl, i);
Solve(i, tr);
pw--;
return ;
}
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
cin>>n>>nn>>m;
for (int i=1; i<=m; i++){
cin>>E[i][0]>>E[i][1];
E[i][0]--;
E[i][1]--;
E[i][1]+=n;
P[i]=i;
//debug2(E[i][0], E[i][1])
}
Solve(1, m+1);
cout<<(*max_element(color+1, color+m+1))+1<<'\n';
for (int i=1; i<=m; i++) cout<<color[i]+1<<'\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
3584 KB |
not colored properly |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
3456 KB |
Output is correct |
| 2 |
Correct |
8 ms |
3456 KB |
Output is correct |
| 3 |
Correct |
7 ms |
3328 KB |
Output is correct |
| 4 |
Correct |
6 ms |
3456 KB |
Output is correct |
| 5 |
Correct |
6 ms |
3456 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
3840 KB |
not colored properly |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
3712 KB |
not colored properly |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
125 ms |
31768 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
151 ms |
34680 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
276 ms |
41424 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1362 ms |
23648 KB |
not colored properly |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1220 ms |
19064 KB |
too many colors |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1194 ms |
19112 KB |
not colored properly |
| 2 |
Halted |
0 ms |
0 KB |
- |
