이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define pii pair<int,int>
#define ft first
#define sd second
#define MP make_pair
#define sz(x) ((int)x.size())
#define PB push_back
using namespace std;
typedef long long ll;
const int N = 100100;
const int M = 700100;
const int oo = 2e9;
stack<pii> st;
vector<int> g[2][N];
vector<pii> vc;
int col[M], l, r, m, deep, x[M], y[M], tt = 0, mrk[2][N], ptr[2][N], used[M], n, lst;
void calc(vector<int> &edges){
bool bad = 0;
tt++;
vc.clear();
for (int cr : edges){
int v = x[cr], u = y[cr];
if (mrk[0][v] < tt) {
mrk[0][v] = tt;
vc.PB(MP(v, 0));
g[0][v].clear();
ptr[0][v] = 0;
}
if (mrk[1][u] < tt) {
mrk[1][u] = tt;
vc.PB(MP(u, 1));
g[1][u].clear();
ptr[1][u] = 0;
}
g[0][v].PB(cr);
g[1][u].PB(cr);
if (sz(g[0][v]) > 1 || sz(g[1][u]) > 1)
bad = 1;
}
if (!bad) return;
g[0][n].clear();
g[1][n].clear();
ptr[1][n] = ptr[0][n] = 0;
lst = m;
for (pii cr : vc) {
int v = cr.ft;
int tp = cr.sd;
if (sz(g[tp][v]) & 1){
x[lst] = n; y[lst] = v;
if (!tp) swap(x[lst], y[lst]);
g[tp][v].PB(lst);
g[tp ^ 1][n].PB(lst);
lst++;
}
}
if (sz(g[0][n]) & 1){
x[lst] = n; y[lst] = n;
g[0][n].PB(lst);
g[1][n].PB(lst);
lst++;
}
tt++;
int ite = 0;
for (pii vr : vc){
int v = vr.ft, tp = vr.sd;
if (ptr[tp][v] != 0) continue;
st.push(vr);
while (sz(st)){
pii cr = st.top();
bool was = 0;
v = cr.ft; tp = cr.sd;
for (; ptr[tp][v] < sz(g[tp][v]); ptr[tp][v]++){
int id = g[tp][v][ptr[tp][v]];
if (used[id] == tt) continue;
was = 1;
int nw = (tp == 0 ? y[id] : x[id]);
st.push(MP(nw, tp ^ 1));
used[id] = tt;
col[id] = (ite << deep);
ite ^= 1;
break;
}
if (!was) st.pop();
}
}
vector<int> A, B;
A.clear();
B.clear();
for (int cr : edges)
if (col[cr] & (1 << deep))
A.PB(cr);
else B.PB(cr);
deep++;
calc(A);
calc(B);
deep--;
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> l >> r >> m;
n = max(l, r);
vector<int> edges;
edges.clear();
for (int i = 0; i < m; i++){
cin >> x[i] >> y[i];
x[i]--; y[i]--;
edges.PB(i);
}
calc(edges);
int mx = 0;
for (int i = 0; i < m; i++)
mx = max(mx, col[i]);
cout << mx + 1 << '\n';
for (int i = 0; i < m; i++)
cout << col[i] + 1 << '\n';
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... |