#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define fs first
#define sc second
struct Edge{
int id;
int to;
Edge(){
id = to = -1;
}
Edge(int ii,int tt){
id = ii;
to = tt;
}
};
const int mxn = 2e5+10;
bitset<mxn> done;
vector<Edge> paths[mxn];
int deg[mxn],ans[mxn*3];
set<int> col[mxn];
int mex[mxn];
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int L,R,M;
cin>>L>>R>>M;
for(int i = 1;i<=M;i++){
int a,b;
cin>>a>>b;
paths[a].push_back(Edge(i,L+b));
paths[L+b].push_back(Edge(i,a));
deg[a]++;
deg[L+b]++;
}
priority_queue<pair<int,int>,vector<pair<int,int>>,less<pair<int,int>>> pq;
pair<int,int> s;
vector<pair<int,int>> ord;
for(int i = 1;i<=L+R;i++){
ord.push_back({deg[i],i});
}
sort(ord.rbegin(),ord.rend());
fill(mex,mex+mxn,1);
for(auto &kkk:ord){
if(done[kkk.sc])continue;
pq.push(kkk);
while(!pq.empty()){
auto now = pq.top();
pq.pop();
if(done[now.sc])continue;
done[now.sc] = true;
while(col[now.sc].find(mex[now.sc]) != col[now.sc].end())mex[now.sc]++;
for(auto nxt:paths[now.sc]){
//cout<<now.sc<<":"<<nxt.to;for(auto &i:col[now.sc])cout<<i<<' ';cout<<',';for(auto &i:col[nxt.to])cout<<i<<' ';cout<<'\n';
if(ans[nxt.id])continue;
int v = nxt.to;
int u = now.sc;
int tmp;
for(tmp = mex[u];col[u].find(tmp) != col[u].end()||col[v].find(tmp) != col[v].end();tmp++);
col[u].insert(tmp);col[v].insert(tmp);
ans[nxt.id] = tmp;
while(col[now.sc].find(mex[now.sc]) != col[now.sc].end())mex[now.sc]++;
deg[nxt.to]--;
if(deg[nxt.to])pq.push({deg[nxt.to],nxt.to});
}
}
}
int mx = *max_element(ans+1,ans+M+1);
cout<<mx<<'\n';
for(int i = 1;i<=M;i++){
if(!ans[i]){
for(int j = 0;j<1e9;j++)cout<<1;
return 0;
}
}
for(int i = 1;i<=M;i++)cout<<ans[i]<<'\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
8 ms |
15188 KB |
too many colors |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
15188 KB |
Output is correct |
2 |
Correct |
8 ms |
15188 KB |
Output is correct |
3 |
Correct |
9 ms |
15188 KB |
Output is correct |
4 |
Correct |
8 ms |
15188 KB |
Output is correct |
5 |
Correct |
9 ms |
15188 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
13 ms |
15956 KB |
too many colors |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
15828 KB |
Output is correct |
2 |
Correct |
12 ms |
15828 KB |
Output is correct |
3 |
Correct |
14 ms |
16000 KB |
Output is correct |
4 |
Correct |
12 ms |
15844 KB |
Output is correct |
5 |
Incorrect |
9 ms |
15572 KB |
too many colors |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
578 ms |
63644 KB |
too many colors |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
582 ms |
63604 KB |
too many colors |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
762 ms |
82216 KB |
Output is correct |
2 |
Correct |
810 ms |
83916 KB |
Output is correct |
3 |
Correct |
78 ms |
24712 KB |
Output is correct |
4 |
Incorrect |
705 ms |
70904 KB |
too many colors |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1041 ms |
79976 KB |
Output is correct |
2 |
Correct |
807 ms |
83892 KB |
Output is correct |
3 |
Correct |
894 ms |
83740 KB |
Output is correct |
4 |
Correct |
765 ms |
76092 KB |
Output is correct |
5 |
Correct |
566 ms |
70144 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
619 ms |
66712 KB |
Output is correct |
2 |
Correct |
801 ms |
83788 KB |
Output is correct |
3 |
Correct |
840 ms |
83820 KB |
Output is correct |
4 |
Correct |
833 ms |
76168 KB |
Output is correct |
5 |
Incorrect |
763 ms |
70172 KB |
too many colors |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
606 ms |
66712 KB |
Output is correct |
2 |
Correct |
806 ms |
83952 KB |
Output is correct |
3 |
Correct |
765 ms |
83916 KB |
Output is correct |
4 |
Correct |
173 ms |
30504 KB |
Output is correct |
5 |
Incorrect |
738 ms |
69496 KB |
too many colors |
6 |
Halted |
0 ms |
0 KB |
- |