答えで二分探索を行います。整数 \(X\) を固定し、\(f(S) \geq X\) となる \(S\) が存在するか？という問題を考えます。

このようにすると、発表者 \(U_k,V_k\) の時間関係から \(S_{U_k}\) と \(S_{V_k}\) に関する制約が定まります。これは、例えば「\(S_1=\) 1 かつ \(S_2=\) 0 である場合は差の絶対値が \(X\) 未満となるため不適」といった形の制約となり、論理式の形で書くと\(\neg((S_{U_i}=c_1)) \land (S_{V_i}=c_2))\) という形になり、これは \((S_{U_i} \neq c_1) \lor (S_{V_i} \neq c_2)\) と同値です。そして、この形の制約が複数与えられた時にそれらを充足する解が存在するかは 2-SAT を用いることで高速に判定することができます。

以上を実装することで \(f(S)\) の最大値を求めることができます。

あとは \(f(S)\) が最大となる \(S\) のうち辞書順最小のものを求めれば良いですが、これは \(S\) の先頭の文字から順にそこを 0 にして充足解が存在する場合は 0 に、存在しない場合は 1 にすることで求めることができます。

実装例(Python3)

import sys
from atcoder.twosat import TwoSAT

input = sys.stdin.readline
n, m = map(int, input().split())
a = [0] * n
d = [0] * n
for i in range(n):
    a[i], d[i] = map(int, input().split())
edges = []
for _ in range(m):
    u, v = map(int, input().split())
    edges.append((u - 1, v - 1))
ok, ng = 0, 10**10
while ng - ok != 1:
    vs = (ok + ng) // 2
    ts = TwoSAT(n)
    for u, v in edges:
        for f in range(2):
            for g in range(2):
                tu = a[u] + f * d[u]
                tv = a[v] + g * d[v]
                if abs(tu - tv) < vs:
                    ts.add_clause(u, not f, v, not g)
    if ts.satisfiable():
        ok = vs
    else:
        ng = vs
ans = [-1] * n
for st in range(n):
    ans[st] = 0
    ts = TwoSAT(n)
    for i in range(st + 1):
        ts.add_clause(i, ans[i], i, ans[i])
    for u, v in edges:
        for f in range(2):
            for g in range(2):
                if ans[u] != -1 and ans[u] != f:
                    continue
                if ans[v] != -1 and ans[v] != g:
                    continue
                tu = a[u] + f * d[u]
                tv = a[v] + g * d[v]
                if abs(tu - tv) < ok:
                    ts.add_clause(u, not f, v, not g)
    if not ts.satisfiable():
        ans[st] = 1
print(ok)
print("".join(map(str, ans)))