#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]){
//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(!done[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',assert(ans[i]);
}
# |
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 |
8 ms |
15228 KB |
Output is correct |
4 |
Correct |
9 ms |
15188 KB |
Output is correct |
5 |
Correct |
10 ms |
15152 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
17 ms |
15956 KB |
too many colors |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
15936 KB |
Output is correct |
2 |
Correct |
12 ms |
15828 KB |
Output is correct |
3 |
Correct |
13 ms |
15956 KB |
Output is correct |
4 |
Correct |
11 ms |
15828 KB |
Output is correct |
5 |
Incorrect |
11 ms |
15600 KB |
too many colors |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
604 ms |
64020 KB |
too many colors |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
596 ms |
63952 KB |
too many colors |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
793 ms |
83112 KB |
Output is correct |
2 |
Correct |
804 ms |
84028 KB |
Output is correct |
3 |
Correct |
75 ms |
24760 KB |
Output is correct |
4 |
Incorrect |
669 ms |
70912 KB |
too many colors |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1004 ms |
80012 KB |
Output is correct |
2 |
Correct |
805 ms |
84092 KB |
Output is correct |
3 |
Correct |
930 ms |
83896 KB |
Output is correct |
4 |
Correct |
776 ms |
76380 KB |
Output is correct |
5 |
Correct |
615 ms |
70456 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
580 ms |
66808 KB |
Output is correct |
2 |
Correct |
838 ms |
84204 KB |
Output is correct |
3 |
Correct |
768 ms |
84040 KB |
Output is correct |
4 |
Correct |
827 ms |
76292 KB |
Output is correct |
5 |
Incorrect |
793 ms |
70296 KB |
too many colors |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
649 ms |
66788 KB |
Output is correct |
2 |
Correct |
792 ms |
84176 KB |
Output is correct |
3 |
Correct |
752 ms |
84212 KB |
Output is correct |
4 |
Correct |
174 ms |
30272 KB |
Output is correct |
5 |
Incorrect |
746 ms |
69356 KB |
too many colors |
6 |
Halted |
0 ms |
0 KB |
- |