제출 #1289609

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1289609		sirnick	Toy Train (IOI17_train)	C++20	0 / 100	6 ms	2112 KiB

train

#include <bits/stdc++.h>
using namespace std;

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
    int n = a.size();
    int m = u.size();

    vector<vector<int>> adj(n), radj(n);
    for(int i=0;i<m;i++){
        adj[u[i]].push_back(v[i]);
        radj[v[i]].push_back(u[i]);
    }

    // 1) find SCC with Tarjan
    vector<int> disc(n,-1), low(n), comp(n), st;
    vector<bool> inst(n,false);
    int timer=0, scc_count=0;

    function<void(int)> dfs = [&](int x){
        disc[x]=low[x]=timer++;
        st.push_back(x);
        inst[x]=true;
        for(int y:adj[x]){
            if(disc[y]<0){
                dfs(y);
                low[x]=min(low[x],low[y]);
            }else if(inst[y]){
                low[x]=min(low[x],disc[y]);
            }
        }
        if(low[x]==disc[x]){
            while(true){
                int w=st.back(); st.pop_back();
                inst[w]=false;
                comp[w]=scc_count;
                if(w==x) break;
            }
            scc_count++;
        }
    };

    for(int i=0;i<n;i++)
        if(disc[i]<0) dfs(i);

    // 2) condensed graph edges + charge info
    vector<vector<int>> cadj(scc_count);
    vector<int> charge_scc(scc_count,0);

    for(int i=0;i<n;i++)
        if(r[i]) charge_scc[comp[i]]=1;

    for(int i=0;i<m;i++){
        int cu=comp[u[i]], cv=comp[v[i]];
        if(cu!=cv) cadj[cu].push_back(cv);
    }

    // 3) Build full graph of states, not SCC-level
    // win[i] = -1 unknown, 0 lose, 1 win
    vector<int> win(n,-1), outdeg(n);
    for(int i=0;i<n;i++)
        outdeg[i] = adj[i].size();

    queue<int> q;

    // Any node in SCC with charge is winning (cycle with recharge)
    for(int i=0;i<n;i++){
        if(charge_scc[comp[i]]){
            win[i]=1;
            q.push(i);
        }
    }

    // 4) backward game propagation
    while(!q.empty()){
        int x=q.front(); q.pop();
        for(int p:radj[x]){
            if(win[p]!=-1) continue;
            if(a[p]==1){
                // p belongs to Arezou
                // If she can point to a winning, p is winning
                win[p]=1;
                q.push(p);
            }else{
                // p belongs to Borzou
                // remove x from safe choices
                outdeg[p]--;
                if(outdeg[p]==0){
                    // all moves lead to winners => p is losing (Borzou can't force a lose)
                    win[p]=0;
                    q.push(p);
                }
            }
        }
    }

    // Remaining unknown:
    // For any node still -1:
    // - If Arezou node: all outgoing lead to nodes not confirmed winning => losing
    // - If Borzou node: there exists some outgoing not winning => winning
    for(int i=0;i<n;i++){
        if(win[i]!=-1) continue;
        if(a[i]==1){
            // Arezou: if there's at least one edge to a non-losing, but unknown = losing
            bool canWin=false;
            for(int nx:adj[i])
                if(win[nx]==1) canWin=true;
            win[i]= canWin?1:0;
        } else {
            // Borzou: if there's at least one edge to a losing
            bool canLose=false;
            for(int nx:adj[i])
                if(win[nx]==0) canLose=true;
            win[i]= canLose?0:1;
        }
    }

    vector<int> ans(n);
    for(int i=0;i<n;i++)
        ans[i] = (win[i]==1?1:0);

    return ans;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 11
• Subtask 4: 0 / 11
• Subtask 5: 0 / 12
• Subtask 6: 0 / 51