#include <bits/stdc++.h>
using namespace std;
int num[500005];
vector<array<int, 2>> adj[100005];
set<int> C[100005];
int num_cnt = 0;
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});
}
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';
}
# |
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 |
7376 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 |
7768 KB |
too many colors |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
7764 KB |
Output is correct |
2 |
Correct |
7 ms |
7636 KB |
Output is correct |
3 |
Correct |
7 ms |
7704 KB |
Output is correct |
4 |
Incorrect |
6 ms |
7636 KB |
too many colors |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
475 ms |
31724 KB |
too many colors |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
466 ms |
31408 KB |
too many colors |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
12059 ms |
15328 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4174 ms |
40284 KB |
Output is correct |
2 |
Correct |
942 ms |
46988 KB |
Output is correct |
3 |
Correct |
1692 ms |
46712 KB |
Output is correct |
4 |
Correct |
605 ms |
42732 KB |
Output is correct |
5 |
Correct |
421 ms |
39108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
12060 ms |
21372 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
12057 ms |
21652 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |