Submission #1259493

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

Main

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int a,b,m;
    if(!(cin>>a>>b>>m)) return 0;
    vector<int> X(m), Y(m);
    vector<vector<pii>> adjA(a+1), adjB(b+1); // store (other, edge_id)
    for(int i=0;i<m;i++){
        cin>>X[i]>>Y[i];
        adjA[X[i]].push_back({Y[i], i});
        adjB[Y[i]].push_back({X[i], i});
    }

    vector<int> compA(a+1, 0), compB(b+1, 0);
    vector<int> ans(m, -1); // -1 = not set, 0 = A->B, 1 = B->A
    int compId = 0;

    // helper to find next index >= pos with (not yet assigned) and deg>0
    auto nextA_with_deg = [&](int start)->int{
        for(int i=start;i<=a;i++){
            if(compA[i]==0 && !adjA[i].empty()) return i;
        }
        return -1;
    };
    auto nextB_with_deg = [&](int start)->int{
        for(int j=start;j<=b;j++){
            if(compB[j]==0 && !adjB[j].empty()) return j;
        }
        return -1;
    };

    int curA = 1, curB = 1;
    while(true){
        // find leftmost unprocessed with flights on each river
        int la = nextA_with_deg(curA);
        int lb = nextB_with_deg(curB);
        if(la==-1 && lb==-1) break; // no more multi-node components to form

        // If one side missing, we must still start from the other side's leftmost with flights
        if(la == -1) { la = ++a; /* won't actually happen because adjB has edges -> assures both exist */ }
        if(lb == -1) { lb = ++b; }

        // expand intervals
        int ra = la, rb = lb;
        int pA = la, pB = lb;

        // We'll only expand over nodes that are not yet assigned; that's ensured since la/lb found unassigned nodes.
        while(pA <= ra || pB <= rb){
            while(pA <= ra){
                // process all edges of pA
                for(auto [y,eid] : adjA[pA]){
                    if(y > rb){
                        // this flight causes expansion of rb: orient it B->A (1)
                        if(ans[eid] == -1) ans[eid] = 1;
                        rb = max(rb, y);
                    } else {
                        // edge to already-in-range y: leave for later (or set arbitrary)
                        // do nothing now
                    }
                }
                ++pA;
            }
            while(pB <= rb){
                for(auto [x,eid] : adjB[pB]){
                    if(x > ra){
                        // this flight causes expansion of ra: orient it A->B (0)
                        if(ans[eid] == -1) ans[eid] = 0;
                        ra = max(ra, x);
                    } else {
                        // internal edge: leave for later
                    }
                }
                ++pB;
            }
        }

        // assign component id to the whole interval pair
        ++compId;
        for(int i=la;i<=ra;i++) compA[i] = compId;
        for(int j=lb;j<=rb;j++) compB[j] = compId;

        // move curA/curB forward
        while(curA <= a && compA[curA] != 0) ++curA;
        while(curB <= b && compB[curB] != 0) ++curB;
    }

    // Remaining cities (those that never had flights or were not covered) become singleton components
    for(int i=1;i<=a;i++){
        if(compA[i]==0) compA[i] = ++compId;
    }
    for(int j=1;j<=b;j++){
        if(compB[j]==0) compB[j] = ++compId;
    }

    // For any edge not assigned during expansion, orient it from earlier component -> later component
    for(int i=0;i<m;i++){
        if(ans[i] != -1) continue;
        int ca = compA[X[i]];
        int cb = compB[Y[i]];
        if(ca < cb) ans[i] = 0; // A->B
        else ans[i] = 1;        // B->A
    }

    // Number of SCCs equals compId
    cout << compId << '\n';
    for(int i=0;i<m;i++){
        if(i) cout << ' ';
        cout << ans[i];
    }
    cout << '\n';
    return 0;
}

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