#include <bits/stdc++.h>
using namespace std;
int num[500005];
vector<array<int, 2>> adj[100005];
set<int> C[100005];
int num_cnt = 0;
array<int, 2> Edge[500005];
signed main() {
cin.sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int L, R, M;
cin >> L >> R >> M;
int i, j;
for(i=0;i<M;i++) {
int a, b;
cin >> a >> b;
adj[a-1].push_back({b-1, i});
Edge[i] = {a-1, b-1};
}
if(M <= 200000) {
vector<int> V;
for(i=0;i<L;i++) V.push_back(i);
sort(V.begin(),V.end(),[&](int x, int y) {
return adj[x].size()>adj[y].size();
});
for(int i : V) {
set<int> S;
for(auto n : adj[i]) {
bool isPos = false;
for(j=0;j<num_cnt;j++) {
if(S.find(j) == S.end() && C[j].find(n[0])==C[j].end()) {
num[n[1]] = j;
C[j].insert(n[0]);
S.insert(j);
isPos = true;
break;
}
}
if(!isPos) {
num[n[1]] = num_cnt;
C[num_cnt].insert(n[0]);
S.insert(num_cnt);
num_cnt++;
}
}
}
cout << num_cnt << '\n';
for(i=0;i<M;i++) cout << num[i] + 1 << '\n';
return 0;
}
vector<int> idx;
for(i=0;i<M;i++) {
idx.push_back(Edge[i][0]^Edge[i][1]);
num[i] = Edge[i][0]^Edge[i][1];
}
sort(idx.begin(),idx.end());
idx.erase(unique(idx.begin(),idx.end()),idx.end());
for(i=0;i<M;i++) {
num[i] = lower_bound(idx.begin(),idx.end(),num[i]) - idx.begin();
}
cout << idx.size() << '\n';
for(i=0;i<M;i++) cout << num[i]+1 << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
7380 KB |
too many colors |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7380 KB |
Output is correct |
2 |
Correct |
4 ms |
7268 KB |
Output is correct |
3 |
Correct |
4 ms |
7380 KB |
Output is correct |
4 |
Correct |
4 ms |
7380 KB |
Output is correct |
5 |
Correct |
4 ms |
7380 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
7 ms |
7764 KB |
too many colors |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
7912 KB |
Output is correct |
2 |
Correct |
8 ms |
7780 KB |
Output is correct |
3 |
Correct |
7 ms |
7764 KB |
Output is correct |
4 |
Incorrect |
7 ms |
7764 KB |
too many colors |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
204 ms |
20276 KB |
too many colors |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
213 ms |
20276 KB |
too many colors |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
206 ms |
22656 KB |
too many colors |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
183 ms |
23628 KB |
too many colors |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
150 ms |
20500 KB |
Output is correct |
2 |
Incorrect |
271 ms |
31308 KB |
too many colors |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
148 ms |
19536 KB |
Output is correct |
2 |
Incorrect |
257 ms |
31328 KB |
too many colors |
3 |
Halted |
0 ms |
0 KB |
- |