Submission #1259408

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259408		dangkhoi	Usmjeravanje (COCI22_usmjeravanje)	C++20	0 / 110	0 ms	324 KiB

Main

#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;
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 60