이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//author: Ahmet Alp Orakci
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define ONLINE_JUDGE
void solve() {
int l, r, m;
cin >> l >> r >> m;
vector <vector <pair <int, int>>> adj[2];
adj[0].resize(l +1);
adj[1].resize(r +1);
map <pair <int, int>, int> edg;
vector <int> ans(m +1);
for(int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
edg[{u, v}] = i;
adj[0][u].emplace_back(v, 0);
adj[1][v].emplace_back(u, 0);
}
vector <bool> vis[2];
vis[0].resize(l +1);
vis[1].resize(r +1);
int res = 1;
function <void(int, int)> dfs = [&](int gr, int node) -> void {
if(vis[gr][node]) {
return;
}
cerr << gr << " " << node << "\n";
vis[gr][node] = true;
map <int, bool> mp;
for(auto &[child, fl] : adj[gr][node]) {
mp[fl] = true;
}
int ind = 1;
for(auto &[child, fl] : adj[gr][node]) {
if(fl == 0) {
while(mp[ind])
ind++;
mp[ind] = true;
fl = ind;
auto it = find(adj[gr ^ 1][child].begin(), adj[gr ^ 1][child].end(), pair <int, int> {node, 0});
it->second = fl;
ind++;
if(gr == 0) {
ans[edg[{node, child}]] = fl;
} else {
ans[edg[{child, node}]] = fl;
}
cerr << gr << " " << node << " " << child << " " << fl << "\n";
dfs(gr ^ 1, child);
}
}
res = max(res, ind -1);
};
for(int i = 1; i <= l; i++) {
dfs(0, i);
cerr << "\n";
}
for(int j = 1; j <= r; j++) {
dfs(1, j);
cerr << "\n";
}
cout << res << "\n";
for(int i = 1; i <= m; i++) {
cout << ans[i] << "\n";
}
return;
}
signed main() {
#ifndef ONLINE_JUDGE
freopen(".in", "r", stdin);
freopen(".out", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int t = 1; //cin >> t;
for(int i = 1; i <= t; i++) {
solve();
}
return 0;
}
# | 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... |