이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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];
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;
for(auto nxt:paths[now.sc]){
if(ans[nxt.id])col[now.sc].insert(ans[nxt.id]);
}
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]--;
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';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |