#include <bits/stdc++.h>
#define eb emplace_back
#define printv(a, b) {\
bool ps = false;\
for(auto pv : a){\
if(ps) b << ' '; ps = true;\
b << pv;\
}\
b << "\n";\
}
#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))
#define mp make_pair
#define F first
#define S second
using namespace std;
typedef long long ll;
using pii = pair<int, int>;
vector<set<int>> g;
vector<int> mt;
vector<pii> e;
vector<int> ans;
int another(int id, int t){
return e[id].F ^ e[id].S ^ t;
}
vector<bool> vst;
bool dfs(int now){
//cerr << "dfs " << now << "\n";
vst[now] = true;
for(int i : g[now]){
int v = another(i, now);
if(mt[v] == -1 || (!vst[another(mt[v], v)] && dfs(another(mt[v], v)))){
mt[v] = i;
//cerr << "match " << now << " " << v << " " << i << "\n";
return true;
}
}
return false;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int l, r, m;
cin >> l >> r >> m;
g.resize(l + 1);
mt.resize(r + 1);
e.resize(m);
ans.resize(m);
vst.resize(l + 1);
for(int i = 0; i < m; i++){
int u, v;
cin >> u >> v;
e[i] = mp(u, v);
g[u].insert(i);
}
int cnt = 0;
while(true){
fill(iter(mt), -1);
fill(iter(vst), false);
bool ok = false;
//cerr << "test\n";
for(int i = 1; i <= l; i++){
//cerr << "qq\n";
if(!vst[i] && dfs(i)) ok = true;
}
if(!ok) break;
//printv(mt, cerr);
cnt++;
for(int i = 1; i <= r; i++){
if(mt[i] == -1) continue;
int id = mt[i];
g[another(id, i)].erase(id);
ans[id] = cnt;
}
}
cout << cnt << "\n";
for(int i = 0; i < m; i++) cout << ans[i] << "\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
364 KB |
too many colors |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
492 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
876 KB |
too many colors |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
748 KB |
Output is correct |
2 |
Correct |
3 ms |
748 KB |
Output is correct |
3 |
Correct |
4 ms |
1004 KB |
Output is correct |
4 |
Incorrect |
3 ms |
768 KB |
too many colors |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
492 ms |
30828 KB |
too many colors |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
502 ms |
30964 KB |
too many colors |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8812 ms |
36988 KB |
Output is correct |
2 |
Incorrect |
965 ms |
41656 KB |
too many colors |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1053 ms |
35804 KB |
too many colors |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
12070 ms |
26988 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
339 ms |
28780 KB |
Output is correct |
2 |
Execution timed out |
12011 ms |
40556 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |