In addition to complaints about lighting, a lot of complaints about insufficient radio signal covering has been received by Bertown city hall recently. 𝑛 complaints were sent to the mayor, all of which are suspiciosly similar to each other: in the 𝑖-th complaint, one of the radio fans has mentioned that the signals of two radio stations 𝑥𝑖 and 𝑦𝑖 are not covering some parts of the city, and demanded that the signal of at least one of these stations can be received in the whole city.

Of cousre, the mayor of Bertown is currently working to satisfy these complaints. A new radio tower has been installed in Bertown, it can transmit a signal with any integer power from 1 to 𝑀 (let's denote the signal power as 𝑓). The mayor has decided that he will choose a set of radio stations and establish a contract with every chosen station. To establish a contract with the 𝑖-th station, the following conditions should be met:

the signal power 𝑓 should be not less than 𝑙𝑖, otherwise the signal of the 𝑖-th station won't cover the whole city;
the signal power 𝑓 should be not greater than 𝑟𝑖, otherwise the signal will be received by the residents of other towns which haven't established a contract with the 𝑖-th station.
All this information was already enough for the mayor to realise that choosing the stations is hard. But after consulting with specialists, he learned that some stations the signals of some stations may interfere with each other: there are 𝑚 pairs of stations (𝑢𝑖, 𝑣𝑖) that use the same signal frequencies, and for each such pair it is impossible to establish contracts with both stations. If stations 𝑥 and 𝑦 use the same frequencies, and 𝑦 and 𝑧 use the same frequencies, it does not imply that 𝑥 and 𝑧 use the same frequencies.

The mayor finds it really hard to analyze this situation, so he hired you to help him. You have to choose signal power 𝑓 and a set of stations to establish contracts with such that:

all complaints are satisfied (formally, for every 𝑖∈[1,𝑛] the city establishes a contract either with station 𝑥𝑖, or with station 𝑦𝑖);
no two chosen stations interfere with each other (formally, for every 𝑖∈[1,𝑚] the city does not establish a contract either with station 𝑢𝑖, or with station 𝑣𝑖);
for each chosen station, the conditions on signal power are met (formally, for each chosen station 𝑖 the condition 𝑙𝑖≤𝑓≤𝑟𝑖 is met).

链接🔗

「CodeForces 1007B」Pave the Parallelepiped

Sooke巨佬

代码

const ll maxd = 2e6+10;

V G[maxd];
ll dfn[maxd],low[maxd],belong[maxd],s[maxd],top,scc,idx;
ll m0,n,m,m1;
bool ins[maxd];

void tarjan(int u)
{
dfn[u] = low[u] = ++idx;
s[top++] = u;
ins[u] = true;
for(auto v:G[u])
{
if (!dfn[v])
{
tarjan(v);
low[u] = min(low[u], low[v]);
}
else if (ins[v])
low[u] = min(low[u], dfn[v]);
}
if(dfn[u] == low[u])
{
++scc;
do
{
belong[s[--top]] = scc;
ins[s[top]] = false;
} while (s[top] != u);
}
}
ll yes(ll x){ return x<<1; }
ll no(ll x){ return x<<1|1; }

void insert(ll x,ll y)
{
//PLP(x);PLN(y);
G[x].pb(y);
G[y^1].pb(x^1);
}
bool solve()
{
FOR(i,0,no(n+m)) if(!dfn[i]) tarjan(i);
FOR(i,0,n+m)
{
//PLN(belong[i]);
if(belong[yes(i)] == belong[no(i)]) return false;
}
return true;
}
int main()
{
//__IN;__OUT;
ll x,y;
RLL(m0);RLL(n);RLL(m);RLL(m1);
F(m0)
{
RLL(x);RLL(y);x--,y--;
insert(no(x),yes(y)); // 如果不选x，则必须选y
}
F(m) insert(yes(n+i),yes(n+i+1)); //
insert(yes(n),no(n)); // 使 0 不合法
F(n)
{
RLL(x);RLL(y);
insert(yes(i),no(n+x-1)); // 如果选i，则频段不在 n+x-1范围内
insert(yes(i),yes(n+y)); // 且频段在 n+y范围内
}
F(m1)
{
RLL(x);RLL(y); x--,y--;
insert(yes(x),no(y)); // 如果选了x，则不能选y
}
ll k = 0;
if(solve())
{
F(n) if(belong[yes(i)] < belong[no(i)]) k++;
FOR(i,1,m)
if(belong[yes(n+i)] < belong[no(n+i)]) // 遇到合法选项
{
printf("%lld %lld\n",k,i);
break;
}

F(n) if(belong[yes(i)] < belong[no(i)]) PLP(i+1);
}
else PS("-1");

return 0;
}