The problem can be found here

My Thought Process

Problems that asks for two similar-ish things are usually actually two different problems. So, we should solve them seperately.

To maximize the reachable nodes, lets consider the how the direction of the undirected edge affect the answer. If we point it toward a reachable node, it doesn’t change much as the reachable node is reachable. If, instead, we point toward another unreachable node, we will increase the answer as we can reach a new node. As a result, we can just dfs from $s$.

Now to minimize the reachable nodes, lets first ignore all the undirected edges and just look at the directed edge and dfs starting at $s$. The number of edges reached this way is the minimum answer we can have since we cannot remove the directed edges. Ok, lets look at the directed edges.

If the undirected edge connect from one reachable node to another, its irrelvant and doesn’t change the answer. If it instead go from a reachable to an unreachable node, we can just direct it to point toward the reachable node. This way, the unreachable node is stil unreachable! Lastly, a node from an unreachable to another unreachable node is also irrelvant because it cannot be reached from $s$.

Implementation

This was probably the hardest part of the problem. I spend way too long trying to implement it. There are probably many, many better ways to implement it, this is the way I implemented it.

$g$ is a vector of vectors of {node, index} where index is 0 if its directed and the index of the list of edges

$vis$ is the visited array

$res$ is the vector to help us determine whether ‘+’ or ‘-‘

$ve$ is our vector of edges

o1 & ans1 stores the answer for minimum amount of nodes and o2 & ans2 for maximum (…I know this is backwards).

Note that the undirected edges will be ‘+’ if they does not appear in dfs because of the else statement.

#include <bits/stdc++.h>

using ll = long long;
#define pb push_back

using namespace std;

const int MOD = 1e9+7;
const int MAXN = 2e6+1;
const int INF = 2e9;    
const long long IINF = 2e18;

vector<vector<pair<int, int>>> g(MAXN);
vector<bool> vis(MAXN, false);
vector<int> res(MAXN, -1);
vector<vector<int>> ve;

void dfs1(int v){
    if(vis[v]){
        return;
    }
    vis[v] = true;

    for(auto u : g[v]){
        if(res[u.second] == 0 && u.second){
            res[u.second] = 1; continue;
        }
        dfs1(u.first);
    }
}

void dfs2(int v){
    if(vis[v]){
        return;
    }
    vis[v] = true;

    for(auto u : g[v]){
        if(res[u.second] == 0 && u.second){
            if(u.first == ve[u.second][2]){
                res[u.second] = 2;
            }
            else{
                res[u.second] = 1;
            }
        }
        dfs2(u.first);
    }
}

void solve() { 
    int n, m, s;
    cin >> n >> m >> s;

    ve.pb({0});
    for(int i = 1; i <= m; ++i){
        int x, y, z; cin >> x >> y >> z;
        ve.pb({x, y, z});
        if(x == 2){
            res[i] = 0;
            g[y].pb({z, i});
        }
        else{
            g[y].pb({z, 0});
        }
    }

    dfs1(s);

    int ans1 = 0; vector<char> o1;
    int ans2 = 0; vector<char> o2;
    for(int i = 1; i <= n; ++i){
        if(vis[i]){
            ans1++;
        }
    }

    for(int i = 1; i <= m; ++i){
        if(res[i] == -1){continue;}
        if(res[i] == 1){
            o1.pb('-');
        }
        else{
            o1.pb('+');
        }
    }

    for(int i = 1; i <= n; ++i){
        vis[i] = false;
        res[i] = -1;
    }

    for(int i = 1; i <= m; ++i){
        if(ve[i][0] == 2){
            res[i] = 0;
            g[ve[i][2]].pb({ve[i][1], i});
        }
    }

    dfs2(s);
    for(int i = 1; i <= n; ++i){
        if(vis[i]){
            ans2++;
        }
    }

    for(int i = 1; i <= m; ++i){
        if(res[i] == -1){continue;}
        if(res[i] == 1){
            o2.pb('-');
        }
        else{
            o2.pb('+');
        }
    }

    cout << ans2 << endl;
    for(auto i : o2){cout << i;}
    cout << endl;
    cout << ans1 << endl;
    for(auto i : o1){cout << i;}
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    // freopen("test.in", "r", stdin);
    // freopen("test.out", "w", stdout);
    solve();

    return 0;
}

Final Thoughts

This was a pretty simple problem in term of how complex it was, but the implementation was a bit long. Looking back on it though, the implementation is not very complex or difficult just that it was very long.