软件包管理器(离线+二分答案+拓扑排序)

描述

传送门:美团2018年CodeM大赛-复赛 - Problem B

点点现在有$n$个软件包。他想设计一个软件包管理器。不可避免地,他要解决软件包之间的依赖问题。

一开始这些软件包之间没有依赖关系。但是每次点点会添加一条依赖关系$a$,$b$,表示软件包$a$依赖$b$。当这些软件包的依赖关系没有环的时候,那么这个软件包的管理器是好的,否则就是不好的。

环的定义如下:
对于任意$k$($k≥2$)个软件包$ \lbrace a_1,a_2,…,a_k \rbrace$,若对于所有的$i<k$满足$a_i$依赖$a_{i+1}$,且$a_1=a_k$成立,则这$k$个软件包构成一个环。

点点想让你回答他每次加入一条依赖关系之后这个软件包是不是好的,如果是好的那么输出$1$,否则输出$0$。同时,点点希望他在加入每一条关系之后你都能回答他,所以他会在读入中对数据进行加密。你只有回答了问题才能知道下一条依赖关系是什么。

输入描述

第一行两个正整数$n$,$m$ ($1≤n≤100,000$, $1≤m≤200,000$),表示软件包的个数和操作个数。软件包的标号为$1$到$n$。
接下来m行,每行两个正整数$u’$, $v’$,表示加密后的依赖关系,保证$u’≠v’$。如果上一个回答为$ans$,实际的依赖关系为$u$, $v$,那么$u’=(u+ans) \mod n+1$, $v’=(v+ans) \mod n+1$。一开始的$ans$为$0$。

输出描述

输出$m$行,每行一个数$0$或$1$,表示加入了一条依赖关系之后的回答。

示例

输入

1
2
3
4
5
3 4
2 3
1 2
3 2
2 3

输出

1
2
3
4
1
1
1
0

说明

解密后的输入为

1
2
3
4
5
3 4
1 2
2 3
1 3
3 1

思路

  • 有向图判环,可以想到用拓扑排序。
  • 拓扑排序不是要离线处理吗?
  • 那就离线呗,没有强制在线吧。
  • 一朝有环,之后必然有环。答案只有$0$和$1$,所以这个加密一看就是骗骗你的。
  • 我们只需要二分第一次出现环的依赖的位置,然后用拓扑排序去判断就好了。
  • 难点在于解密。$u’ - 1 \equiv u + 1 \pmod n$。因此编号从$0$开始比较方便。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <bits/stdc++.h>
using namespace std;

#pragma optimize("-O3")

typedef long long ll;
typedef long double ld;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;

void go();

int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
go();
return 0;
}

/****************************************************************************************************/

vector<PII> q;

bool ok(int x, int n)
{
vector<VI> G(n);
VI deg(n);
for (int i = 0; i < x; i++)
{
G[q[i].first].push_back(q[i].second);
++deg[q[i].second];
}
queue<int> q;
for (int i = 0; i < n; i++)
if (!deg[i]) q.push(i);
int tot = 0;
while (!q.empty())
{
int u = q.front();
q.pop();
++tot;
for (auto& v : G[u])
if (--deg[v] == 0) q.push(v);
}
return tot == n;
}

void go()
{
int n, m;
cin >> n >> m;
q.resize(m);
for (int i = 0; i < m; i++)
{
cin >> q[i].first >> q[i].second;
q[i].first = (q[i].first - (i != 0) + n - 1) % n;
q[i].second = (q[i].second - (i != 0) + n - 1) % n;
}
int l = 1, r = m, ans;
while (l <= r)
{
int mid = l + r >> 1;
if (ok(mid, n))
l = mid + 1, ans = mid;
else
r = mid - 1;
}
for (int i = 0; i < ans; i++) cout << 1 << endl;
for (int i = ans; i < m; i++) cout << 0 << endl;
}
捐助作者
0%