#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;
//cout<<endl;
//cout<<kkk.sc<<":"<<endl;
pq.push(kkk);
while(!pq.empty()){
auto now = pq.top();
//cout<<now.sc<<',';
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]){
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(!done[nxt.to])pq.push({deg[nxt.to],nxt.to});
}
}
}
int mx = *max_element(ans+1,ans+M+1);
int big = 0;
for(int i = 1;i<=L+R;i++)big = max(big,(int)paths[i].size());
assert(mx == big);
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 |
Runtime error |
22 ms |
30676 KB |
Execution killed with signal 6 |
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 |
10 ms |
15104 KB |
Output is correct |
4 |
Correct |
10 ms |
15204 KB |
Output is correct |
5 |
Correct |
8 ms |
15188 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
24 ms |
32212 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
15936 KB |
Output is correct |
2 |
Correct |
12 ms |
15828 KB |
Output is correct |
3 |
Correct |
12 ms |
15956 KB |
Output is correct |
4 |
Correct |
12 ms |
15780 KB |
Output is correct |
5 |
Runtime error |
22 ms |
31444 KB |
Execution killed with signal 6 |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
512 ms |
128168 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
530 ms |
128024 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
792 ms |
83000 KB |
Output is correct |
2 |
Correct |
802 ms |
83988 KB |
Output is correct |
3 |
Correct |
76 ms |
24752 KB |
Output is correct |
4 |
Runtime error |
617 ms |
141324 KB |
Execution killed with signal 6 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1078 ms |
80036 KB |
Output is correct |
2 |
Correct |
818 ms |
84008 KB |
Output is correct |
3 |
Correct |
922 ms |
83924 KB |
Output is correct |
4 |
Correct |
794 ms |
76260 KB |
Output is correct |
5 |
Correct |
669 ms |
70504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
646 ms |
66740 KB |
Output is correct |
2 |
Correct |
848 ms |
84128 KB |
Output is correct |
3 |
Correct |
867 ms |
84040 KB |
Output is correct |
4 |
Correct |
814 ms |
76232 KB |
Output is correct |
5 |
Runtime error |
672 ms |
139336 KB |
Execution killed with signal 6 |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
662 ms |
66768 KB |
Output is correct |
2 |
Correct |
811 ms |
84072 KB |
Output is correct |
3 |
Correct |
855 ms |
84140 KB |
Output is correct |
4 |
Runtime error |
166 ms |
60488 KB |
Execution killed with signal 6 |
5 |
Halted |
0 ms |
0 KB |
- |