#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int a,b,m;
if(!(cin>>a>>b>>m)) return 0;
vi X(m), Y(m);
vector<vector<int>> adjX(a+1), adjY(b+1);
for(int i=0;i<m;++i){
cin>>X[i]>>Y[i];
adjX[X[i]].push_back(i);
adjY[Y[i]].push_back(i);
}
vector<char> usedEdge(m, 0);
vi orient(m, -1); // 0: X->Y, 1: Y->X
vector<char> assignedX(a+1,0), assignedY(b+1,0);
vi posX(a+1,0), posY(b+1,0);
auto advance_posX = [&](int idx){
while(posX[idx] < (int)adjX[idx].size() && usedEdge[ adjX[idx][ posX[idx] ] ]) ++posX[idx];
};
auto advance_posY = [&](int idx){
while(posY[idx] < (int)adjY[idx].size() && usedEdge[ adjY[idx][ posY[idx] ] ]) ++posY[idx];
};
// functions to get next candidate (smallest index not yet assigned and having unused incident edge)
int curX = 1, curY = 1;
auto move_curX = [&](){
while(curX <= a){
if(assignedX[curX]) { ++curX; continue; }
advance_posX(curX);
if(posX[curX] < (int)adjX[curX].size()) break;
++curX;
}
};
auto move_curY = [&](){
while(curY <= b){
if(assignedY[curY]) { ++curY; continue; }
advance_posY(curY);
if(posY[curY] < (int)adjY[curY].size()) break;
++curY;
}
};
move_curX();
move_curY();
// main paired-interval expansion: only while both sides have candidates
while(curX <= a && curY <= b){
int xL = curX, xR = curX;
int yL = curY, yR = curY;
int ix = xL, iy = yL;
while(ix <= xR || iy <= yR){
while(ix <= xR){
if(!assignedX[ix]){
for(int ei: adjX[ix]){
if(usedEdge[ei]) continue;
usedEdge[ei] = 1;
orient[ei] = 1; // discovered from X => Y -> X
if(Y[ei] > yR) yR = Y[ei];
}
}
++ix;
}
while(iy <= yR){
if(!assignedY[iy]){
for(int ei: adjY[iy]){
if(usedEdge[ei]) continue;
usedEdge[ei] = 1;
orient[ei] = 0; // discovered from Y => X -> Y
if(X[ei] > xR) xR = X[ei];
}
}
++iy;
}
}
// mark assigned nodes
for(int xx = xL; xx <= xR; ++xx) assignedX[xx] = 1;
for(int yy = yL; yy <= yR; ++yy) assignedY[yy] = 1;
// advance to next candidate on both sides
if(curX <= xR) curX = xR + 1;
if(curY <= yR) curY = yR + 1;
move_curX();
move_curY();
}
// any un-oriented edge (no discovery due to isolated one-side situation) -> set default 0
for(int i=0;i<m;++i) if(orient[i] == -1) orient[i] = 0;
// build directed graph: nodes 0..a-1 (river1), a..a+b-1 (river2)
int N = a + b;
vector<vi> G(N), GR(N);
auto add_edge = [&](int u,int v){
G[u].push_back(v);
GR[v].push_back(u);
};
// river downstream edges
for(int i=0;i+1<a;++i) add_edge(i, i+1);
for(int i=0;i+1<b;++i) add_edge(a + i, a + i + 1);
// flights according to orient
for(int i=0;i<m;++i){
if(orient[i] == 0){
int u = X[i]-1, v = a + (Y[i]-1);
add_edge(u, v);
} else {
int u = a + (Y[i]-1), v = X[i]-1;
add_edge(u, v);
}
}
// Kosaraju (iterative)
vector<char> vis(N,0);
vector<int> order; order.reserve(N);
for(int s=0;s<N;++s) if(!vis[s]){
// iterative DFS: stack of pair(node, nextchildindex)
vector<pair<int,int>> st;
st.emplace_back(s,0);
vis[s]=1;
while(!st.empty()){
int node = st.back().first;
int &it = st.back().second;
if(it < (int)G[node].size()){
int to = G[node][it++];
if(!vis[to]) { vis[to]=1; st.emplace_back(to,0); }
} else {
order.push_back(node);
st.pop_back();
}
}
}
vector<int> comp(N, -1);
int compcnt = 0;
for(int i = (int)order.size()-1; i>=0; --i){
int v = order[i];
if(comp[v] != -1) continue;
// iterative DFS on GR
vector<int> st; st.push_back(v);
comp[v] = compcnt;
while(!st.empty()){
int node = st.back(); st.pop_back();
for(int to: GR[node]){
if(comp[to] == -1){ comp[to] = compcnt; st.push_back(to); }
}
}
++compcnt;
}
cout << compcnt << '\n';
for(int i=0;i<m;++i){
if(i) cout << ' ';
cout << orient[i];
}
cout << '\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... |