好像还是大模拟题。。
熟练运用STL,知晓其底层所用实现效率即可。。。
跟算法倒是没多大关系。。。

因为输入的查询必定晚于输入相关节点生成,实际上确保了查询时刻升序。
为了实现查询给定时刻的状态,记录所有输入与中间的节点传输数据,直到查询时再模拟运行到查询时刻,剩下的不模拟直到下一个查询时刻输入。

链的传输操作(transmission)和新块的创建操作(creation),使用哈希表unordered_map记录。
考虑到操作记录的信息量比较大,怕爆空间,完成操作处理后,会将其从哈希表中擦除。

为了按时间顺序处理,同时保证高效率+记录的时间点不能重复,使用set记录了所有发生变化操作的时间点(timepoints)。
在模拟时,从timepoints中顺序取出,即可按照时间点顺序处理,然后查询是否有对应时刻的transmission与creation。
在完成相应时刻的模拟之后,会移除set中对应的时间点。这是为了后续再次查询时不会重复处理已经处理过的时间点。

虽然transmission和creation擦除后,对应时间点的操作记录已经为空,那么timepoints即使不擦除已处理元素,也不会再影响结果正确性。但是如果不擦除timepoints,遍历时间点时仍然会造成时运行时间上的浪费。
timepoints已处理过的时间点必须动态擦除,否则重复遍历已处理过的时间点,会导致程序运行时间超时。
注意STL容器erase方法的用法

代码长度 3.234KB
编程语言 C0X
评测结果 正确
得分 100
时间使用 3.328s
空间使用 16.00MB

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <bits/stdc++.h>
using namespace std;

using nodeidT = int;
using chainT = vector<nodeidT>;
using broadcastMsg = pair<nodeidT, chainT>; // 发出节点ID,主链
vector<vector<nodeidT> > rel; // 节点-邻接表{相连节点...}
vector<chainT> chain;// 节点-主链{主链节点...}
unordered_map<int, vector<pair<nodeidT, int>>> creation; // 时间- {{节点,块编号}...}
unordered_map<int, vector<broadcastMsg> > transmission; // 时间- {节点,链{接收链组成节点...}}...}
set<int> timepoints;

int n;
int delay;

inline void gen(int node, int t, int id) {
creation[t].push_back({node, id});
timepoints.insert(t);
}

inline void broadcastNeighbor(int node, int tp) {
transmission[tp + delay].push_back({node, chain[node]});
timepoints.insert(tp + delay); // 不要忘记维护时间点表
}

inline void query(int node, int t) {
auto it = timepoints.begin();
for (; it != timepoints.end() && *it <= t; ++it) {
int tp = *it;
// 先处理接收
if (transmission.count(tp)) {
for (const auto &msg: transmission[tp]) {
const auto &fromid = msg.first;
const auto &sentchain = msg.second;
for (const auto &toid: rel[fromid]) {
if (chain[toid].size() < sentchain.size()
|| (chain[toid].size() == sentchain.size() && chain[toid].back() > sentchain.back())
) {
chain[toid] = sentchain; // 接受更新
broadcastNeighbor(toid, tp); // 向邻居广播自己的主链
}
}
}
}
transmission.erase(tp);
// 处理创建
if (creation.count(tp)) {
for (const auto &p: creation[tp]) {
const auto &nodeid = p.first;
const auto &blockid = p.second;
chain[nodeid].push_back(blockid); // 主链延长
broadcastNeighbor(nodeid, tp); // 向邻居广播自己的主链
}
}
creation.erase(tp);
}
timepoints.erase(timepoints.begin(), it); // 此处erase使用注意,不能在循环中擦除当前key,否则当前迭代器失效无法自增至下一元素
// 输出该时间点状态
cout << chain[node].size();
for (int b: chain[node]) {
cout << " " << b;
}
cout << endl;
}

int main() {
ios_base::sync_with_stdio(false);
int m;
cin >> n >> m;
rel.resize(n + 1);
chain.resize(n + 1, chainT(1, 0));
creation.reserve(2000);
transmission.reserve(2000);
for (int i = 1; i <= m; ++i) {
int u, v;
cin >> u >> v;
rel[u].push_back(v);
rel[v].push_back(u);
}
int k;
cin >> delay >> k;
for (int i = 1; i <= k; ++i) {
int a, b, c;
cin >> a >> b;
if (cin.get() == '\n' || cin.eof()) {
query(a, b);
} else {
cin >> c;
gen(a, b, c);
}
}
}