#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++)cout<<ans[i]<<'\n',assert(ans[i]);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
10 ms |
15188 KB |
too many colors |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
15216 KB |
Output is correct |
2 |
Correct |
10 ms |
15188 KB |
Output is correct |
3 |
Correct |
8 ms |
15188 KB |
Output is correct |
4 |
Correct |
8 ms |
15136 KB |
Output is correct |
5 |
Correct |
8 ms |
15228 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
14 ms |
15928 KB |
too many colors |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
15872 KB |
Output is correct |
2 |
Correct |
13 ms |
15828 KB |
Output is correct |
3 |
Correct |
17 ms |
15976 KB |
Output is correct |
4 |
Correct |
15 ms |
15816 KB |
Output is correct |
5 |
Incorrect |
10 ms |
15572 KB |
too many colors |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
539 ms |
63656 KB |
too many colors |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
521 ms |
63724 KB |
too many colors |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
739 ms |
82288 KB |
Output is correct |
2 |
Correct |
792 ms |
89468 KB |
Output is correct |
3 |
Correct |
78 ms |
25148 KB |
Output is correct |
4 |
Incorrect |
684 ms |
75200 KB |
too many colors |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1079 ms |
80084 KB |
Output is correct |
2 |
Correct |
852 ms |
89608 KB |
Output is correct |
3 |
Correct |
868 ms |
88824 KB |
Output is correct |
4 |
Correct |
810 ms |
81512 KB |
Output is correct |
5 |
Correct |
569 ms |
74728 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
637 ms |
66704 KB |
Output is correct |
2 |
Correct |
750 ms |
89508 KB |
Output is correct |
3 |
Correct |
723 ms |
89548 KB |
Output is correct |
4 |
Correct |
732 ms |
81420 KB |
Output is correct |
5 |
Incorrect |
737 ms |
74164 KB |
too many colors |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
629 ms |
66776 KB |
Output is correct |
2 |
Correct |
752 ms |
89452 KB |
Output is correct |
3 |
Correct |
739 ms |
89520 KB |
Output is correct |
4 |
Correct |
152 ms |
31188 KB |
Output is correct |
5 |
Incorrect |
746 ms |
73344 KB |
too many colors |
6 |
Halted |
0 ms |
0 KB |
- |