Submission #1259408

#TimeUsernameProblemLanguageResultExecution timeMemory
1259408dangkhoiUsmjeravanje (COCI22_usmjeravanje)C++20
0 / 110
0 ms324 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...