The 2021 ICPC Asia Regionals Online Contest (I)

比赛链接

A. Busiest Computing Nodes

把每个请求分成开始请求(开始时间)和结束请求(结束时间)。对请求按时间排序,先在 s e t \rm set set 中插入 0 ∼ k − 1 0\sim k -1 0k1

  1. 对于每个开始请求,若 s e t \rm set set 非空,则在 s e t \rm set set l o w e r _ b o u n d ( i d % k ) \rm lower\_bound(id\%k) lower_bound(id%k) ,若不存在则选择 s e t \rm set set 的第一个元素,打标记并将其从 s e t \rm set set 中删除。
  2. 对于每个结束请求,如果对应的开始请求被处理了,就把处理开始请求的机器放回 s e t \rm set set

O ( n log ⁡ n ) O(n\log n) O(nlogn)

#include<bits/stdc++.h>

#define fp(i, a, b) for(int i = (a), _##i = (b) + 1; i < _##i; ++i)
using namespace std;

int main() { 
    int n, m;
    scanf("%d%d\n", &n, &m);
    set<int> s;
    fp(i, 0, n - 1) s.insert(i);
    vector<int> cnt(n), b(m + 1, -1), c;
    vector<pair<int, int>> a(2 * m);
    for (int x, y, i = 0; i < m; ++i)
        scanf("%d%d", &x, &y), a[i << 1] = { x, i + 1}, a[i << 1 | 1] = { x + y, -i - 1};
    sort(a.begin(), a.end());
    for (int i = 0, id; i < a.size() - 1; ++i)
        if ((id = a[i].second) < 0) { 
            if (~b[-id]) s.insert(b[-id]);
        } else if (!s.empty()) { 
            auto t = s.lower_bound((id - 1) % n);
            t = t != s.end() ? t : s.begin();
            ++cnt[b[id] = *t], s.erase(t);
        }
    int mx = *max_element(cnt.begin(), cnt.end());
    fp(i, 0, n - 1) if (cnt[i] == mx) c.push_back(i);
    fp(i, 0, c.size() - 1) printf("%d%c", c[i], " \0"[i == c.size() - 1]);
    return 0;
}

B. Convex Polygon

题目实际上没有所谓的“非法”输入。题目要判断是输入的所有点能否构成一个凸多边形,并且任意 3 3 3 点不共线。 先判断点数 ≥ 3 \ge 3 3 , 然后 O ( n 3 ) O(n^3) O(n3) 暴力判断三点共线,最后求凸包判断凸包上的点是否等于总点数即可。

O ( n 3 ) O(n^3) O(n3)

#include<bits/stdc++.h>

#define fp(i, a, b) for(int i = (a), _##i = (b) + 1; i < _##i; ++i)
#define fd(i, a, b) for(int i = (a), _##i = (b) - 1; i > _##i; --i)
using namespace std;
const int N = 2e5 + 5;
using ll = long long;

struct Vec { 
    ll x, y;
    bool operator==(Vec b) const {  return x == b.x && y == b.y; }
    bool operator<(Vec b) const {  return x == b.x ? y < b.y : x < b.x; }
    Vec operator-(Vec b) const {  return { x - b.x, y - b.y}; }
    ll cross(Vec a) const {  return x * a.y - y * a.x; }
    ll cross(Vec a, Vec b) {  return (a - *this).cross(b - *this); }
    ll L2() const {  return x * x + y * y; }
};

vector<Vec> convex(vector<Vec> &a) { 
    if (a.size() == 1)return a;
    sort(a.begin(), a.end());
    vector<Vec> h(a.size() + 1);
    int s = 0, t = 0;
    for (int it = 2; it--; s = --t, reverse(a.begin(), a.end()))
        for (Vec p: a) { 
            while (t >= s + 2 && h[t - 2].cross(h[t - 1], p) <= 0) t--;
            h[t++] = p;
        }
    return { h.begin(), h.begin() + t - (t == 2 && h[0] == h[1])};
}

int main() { 
    int x, y, n, p = 0;
    vector<Vec> a;
    while (~scanf("%d,%d,", &x, &y))
        a.push_back({ (ll) x, (ll) y});
    if (a.size() < 3)
        return printf("ERROR"), 0;
    n = a.size();    
    fp(i, 0, n - 1) fp(j, i + 1, n - 1) fp(k, j + 1, n - 1)
        if (a[i].cross(a[j], a[k]) == 0)
            return printf("ERROR"), 0;
    auto h = convex(a);
    if (h.size() != n) return printf("ERROR"), 0;
    vector<Vec> ans;
    fp(i, 0, h.size() - 1) if (h[i].L2() < h[p].L2()) p = i;
    fd(i, p, 0) ans.push_back(h[i]);
    fd(i, h.size() - 1, p + 1) ans.push_back(h[i]);
    fp(i, 0, ans.size() - 2) printf("%d,%d,", ans[i].x, ans[i].y);
    printf("%d,%d", ans.back().x, ans.back().y);
    return 0;
}

C. Driver Licenses

首先先缩点。对于每次询问,对起点打个标记,按拓扑排序的方式下传标记,若一个点本身有标记且被下传了标记则 I n v a l i d \rm Invalid Invalid (有两个起点在同一个强连通分量也是 I n v a l i d \rm Invalid Invalid ),若标记能传到终点则为 Y e s \rm Yes Yes 。而实际上传递标记只涉及 b o o l \rm bool bool 运算,所以可以开一个长度为 q q q b i t s e t \rm bitset bitset 同时处理所有询问。

O ( n q ω ) O(\frac{nq}\omega) O(ωnq)

#include<bits/stdc++.h>

#define fp(i, a, b) for(int i = (a), _##i = (b) + 1; i < _##i; ++i)
using namespace std;
const int N = 1e5 + 5, M = 1e4 + 5;

struct Tarjan { 
    int dft{ }, scc{ }, top{ }, s[N]{ };
    bitset<N> in;
    vector<int> G[N], dfn, low, bl;
    void dfs(int u) { 
        low[u] = dfn[u] = ++dft, s[++top] = u, in[u].flip();
        for (auto v: G[u])
            if (!dfn[v])dfs(v), low[u] = min(low[u], low[v]);
            else if (in[v]) low[u] = min(low[u], dfn[v]);
        if (low[u] == dfn[u]) { 
            int v = ++scc;
            do bl[v = s[top--]] = scc, in[v].flip(); while (u != v);
        }
    }
    vector<int> work(int n) { 
        dfn.assign(n, 0), low = bl = dfn, in = 0;
        fp(u, 0, n - 1) if (!dfn[u]) dfs(u);
        return bl;
    }
} T;
int n, q, in[N];
bitset<M> err, f[N], g[N];
vector<int> G[N];
unordered_map<string, int> mp;
vector<int> trans(string s) { 
    string k;
    vector<int> v;
    for (auto h = s.begin(), t = s.end(); h < t; v.push_back(mp[k]), k = "")
        for (k += *h++; h < t && !isalpha(*h);) k += *h++;
    return v;
}
void Solve() { 
    vector<string> S(n);
    mp.clear(), T.scc = T.dft = 0;
    fp(i, 0, n - 1) { 
        string s; getline(cin, s);
        int m = s.find(':'); T.G[i].clear();
        mp[string(s, 0, m)] = i, S[i] = m + 1 != s.length() ? string(s, m + 2, s.length()) : "";
    }
    fp(u, 0, n - 1) if(!S[u].empty()) { 
        auto t = trans(S[u]);
        for (auto v : t) T.G[u].push_back(v);
    }
    auto bl = T.work(n);
    fp(u, 1, T.scc) G[u].clear(), f[u] = g[u] = in[u] = 0;
    fp(u, 0, n - 1) for (auto v : T.G[u])
        if (bl[u] != bl[v]) G[bl[u]].push_back(bl[v]), ++in[bl[v]];
    scanf("%d\n", &q), err = 0;
    vector<int> ans(q), ed(q);
    fp(i, 0, q - 1) { 
        string s; getline(cin, s); int m = s.find(':');
        ed[i] = bl[mp[string(s, m + 2, s.length())]];
        for (auto u : trans(string(s, 0, m)))
            if(!f[u = bl[u]][i]) f[u][i] = g[u][i] = true;
            else {  err[i] = true; break; }
        if(err[i]) continue;
    }
    queue<int> Q;
    fp(u, 1, T.scc) if (!in[u]) Q.push(u);
    while (!Q.empty()) { 
        int u = Q.front(); Q.pop();
        for (auto v: G[u]) { 
            f[v] |= f[u], err |= g[v] & f[u];
            if (!--in[v]) Q.push(v);
        }
    }
    fp(i, 0, q - 1) puts(err[i] ? "Invalid" : (f[ed[i]][i] ? "Yes" : "No"));
}

int main() { 
    int T; scanf("%d", &T);
    for (int i = 1; i <= T; ++i, puts(""))
        scanf("%d\n", &n), printf("Case #%d:\n", i), Solve();
    return 0;
}

D. Edge of Taixuan

答案就是总边权减去最小生成树的权值。最小生成树一定是一条链,考虑 i → i + 1 i\rightarrow i+1 ii+1 的边权,一定是覆盖二者的最小权值。贪心,把所有操作按 W W W 倒序排序,然后在线段树上区间覆盖即可,最后 d f s \rm dfs dfs 整颗线段树得到的权值和即为最小生成树的权值。实际上最终答案可以到 1 0 20 10^{20} 1020 ,需要 i n t 128 \rm int128 int128 ,但是出题人并没有出这种数据。

O ( m log ⁡ n ) O(m\log n) O(mlogn)

#include<bits/stdc++.h>

#define fp(i, a, b) for(int i = (a), _##i = (b) + 1; i < _##i; ++i)
#define fd(i, a, b) for(int i = (a), _##i = (b) - 1; i > _##i; --i)
using namespace std;
using ll = long long;
const ll Inf = 1e13;
const int N = 2e5 + 5;
ll tr[N << 2];
#define lc (p << 1)
#define rc (p << 1 | 1)
void Build(int p, int L, int R) { 
    tr[p] = Inf;
    if (L == R)return;
    int m = (L + R) >> 1;
    Build(lc, L, m), Build(rc, m + 1, R);
}
void mdy(int p, int L, int R, int a, int b, int w) { 
    if (a <= L && R <= b) return tr[p] = w, void();
    int m = (L + R) >> 1;
    if (a <= m) mdy(lc, L, m, a, b, w);
    if (b > m) mdy(rc, m + 1, R, a, b, w);
}
ll dfs(int p, int L, int R) { 
    if (L == R)return tr[p];
    tr[lc] = min(tr[lc], tr[p]);
    tr[rc] = min(tr[rc], tr[p]);
    int m = (L + R) >> 1;
    return dfs(lc, L, m) + dfs(rc, m + 1, R);
}
int n, q;
struct Data{ int l,r,w;};
void print(__int128 x){ 
    if (x > 9) print(x / 10);
    putchar('0' + x % 10);
}
void Solve(){ 
    __int128 ans = 0;
    vector<Data> a(q);
    for (auto &x: a)
        scanf("%d%d%d", &x.l, &x.r, &x.w), ans += (ll) (x.r - x.l + 1) * (x.r - x.l) / 2 * x.w;
    sort(a.begin(), a.end(), [](Data x, Data y) {  return x.w > y.w; });
    Build(1, 1, n - 1);
    for (auto x: a) mdy(1, 1, n - 1, x.l, x.r - 1, x.w);
    ll res = dfs(1, 1, n - 1);
    if(res > Inf) printf("Gotta prepare a lesson");
    else print(ans - res);
}
int main() { 
    int T; scanf("%d",&T);
    for (int i = 1; i <= T; ++i) { 
        scanf("%d%d",&n,&q);
        printf("Case #%d: ", i), Solve();
        if (i < T) puts("");
    }
    return 0;
}

E. Infinite File System

文件系统是一个树结构,每个节点有个两个权值 f , g f,g f,g 。操作可以简化为:

  1. 对一个子树做取 m a x \rm max max 操作,即 f u = max ⁡ ( f u , l e v e l ) f_u=\max(f_u,\rm level) fu=max(fu,level) g u = max ⁡ ( g u , l e v e l ) g_u=\max(g_u,\rm level) gu=max(gu,level)
  2. 永久将一颗子树的 f f f 置为 0 ;
  3. 询问节点 u u u max ⁡ ( f u , g u ) \max(f_u,g_u) max(fu,gu)
  4. 询问一颗子树的最大的 max ⁡ ( f u , g u ) \max(f_u,g_u) max(fu,gu)

字符串处理建出树结构,求出 d f s \rm dfs dfs 序转化为序列问题,对默认权限 f u f_u fu 和严格权限 g u g_u gu 分别建一颗线段树,再套用 S e g m e n t T r e e B e a t s \rm Segment Tree Beats SegmentTreeBeats 即可。

O ( q log ⁡ n ) O(q\log n) O(qlogn)

以上为出题人本来想出的题的题解。实际上赛时的题目描述应该是还要对节点 u u u 到根路径上所有点的权值取 max ⁡ \max max ,由于本身路径也是完整读入的,所以直接暴力跳父亲复杂度也是没问题的,但是这么做会 W A \rm WA WA 。所以只能求和出题人心意想通了。

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5, Inf = 1e9;
struct Seg { 
    struct Data { 
        int mx, mn, se;
        Data operator+(Data b) {  return { max(mx, b.mx), min(mn, b.mn), min({ mn != b.mn ? max(mn, b.mn) : Inf, se, b.se})}; }
    } tr[N << 2];
    int ban[N << 2], tag[N << 2];
#define lc (p << 1)
#define rc (p << 1 | 1)
    void Up(int p) {  tr[p] = tr[lc] + tr[rc]; }
    void upd(int p, int a, int b) {  tr[p].mn = max(tr[p].mn, a), tr[p].mx = max(tr[p].mx, b), tag[p] = max(tag[p], b); }
    void Down(int p) {  int a = tr[p].mn, b = tag[p]; upd(lc, a, b), upd(rc, a, b); }
    void Build(int p, int L, int R) { 
        tr[p].se = Inf;
        if (L == R) return;
        int m = (L + R) >> 1;
        Build(lc, L, m), Build(rc, m + 1, R);
    }
    void Max(int p, int L, int R, int a, int b, int w) { 
        if (ban[p] || tr[p].mn >= w) return;
        if (a <= L && R <= b && w < tr[p].se) return upd(p, w, w);
        int m = (L + R) >> 1; Down(p);
        if (a <= m) Max(lc, L, m, a, b, w);
        if (b > m) Max(rc, m + 1, R, a, b, w);
        Up(p);
    }
    void del(int p, int L, int R, int a, int b) { 
        if (ban[p]) return;
        if (a <= L && R <= b) return tr[p] = { 0, 0, Inf}, ban[p] = 1, void();
        int m = (L + R) >> 1; Down(p);
        if (a <= m) del(lc, L, m, a, b);
        if (b > m) del(rc, m + 1, R, a, b);
        Up(p);
    }
    int qry(int p, int L, int R, int a, int b) { 
        if (ban[p]) return 0;
        if (a <= L && R <= b) return tr[p].mx;
        int m = (L + R) >> 1, w = 0; Down(p);
        if (a <= m) w = qry(lc, L, m, a, b);
        if (b > m) w = max(w, qry(rc, m + 1, R, a, b));
        return w;
    }
} A, B;
struct Qry {  int op, u, w; };
int n, dft, dfn[N], ed[N];
char s[1 << 20];
vector<int> G[N];
unordered_map<string, int> mp[N];
int getID(char *h, const char *t) { 
    int u = 1;
    for (; h < t && *h != '/'; ++h);
    for (string k; ++h < t; u = mp[u][k], k = "") { 
        for (; h < t && *h != '/'; ++h) k += *h;
        if (!mp[u].count(k)) mp[u][k] = ++n, G[u].push_back(n);
    }
    return u;
}
void dfs(int u) {  dfn[u] = ++dft; for (auto v: G[u]) dfs(v); ed[u] = dft; }
int main() { 
    vector<Qry> q; n = 1;
    for (int w = 0, op; ~scanf("%[^\n]", s); getchar()) { 
        char *p = s + 2, *e = s + strlen(s);
        if (s[0] == 'g') op = 2;
        else op = s[0] == 's', w = strtol(p, &p, 10);
        q.push_back({ op, getID(p, e), w});
    }
    dfs(1), A.Build(1, 1, n), B.Build(1, 1, n);
    auto qry = [&](int L, int R) {  return max(A.qry(1, 1, n, L, R), B.qry(1, 1, n, L, R)); };
    for(int i = 0; i < q.size(); ++i) { 
        int u = q[i].u;
        switch (q[i].op) { 
            case 0: A.Max(1, 1, n, dfn[u], ed[u], q[i].w); break;
            case 1: A.del(1, 1, n, dfn[u], ed[u]), B.Max(1, 1, n, dfn[u], ed[u], q[i].w); break;
            default: printf("%d %d%c", qry(dfn[u], dfn[u]), qry(dfn[u], ed[u]), "\n\0"[i == q.size() - 1]); break;
        }
    }
    return 0;
}

F. Land Overseer

注意这题是要求了先到位于 ( a , b ) (a,b) (a,b) 的圆,然后再到 ( 2 a , 0 ) (2a,0) (2a,0) 的圆。注意特判 b < R b<R b<R 的情况。

O ( 1 ) O(1) O(1)

#include<bits/stdc++.h>

int main() { 
    int T, i = 1, a, b, r; scanf("%d", &T);
    for (; i <= T; ++i)
        scanf("%d%d%d", &a, &b, &r),
        printf("Case #%d: %.2lf%c", i, 2 * (b > r ? sqrt(1.0 * a * a + 1.0 * (b - r) * (b - r)) : 1.0 * a) - r, "\n\0"[i == T]);
    return 0;
}

G. Longest Prefix Matching

题意

给出 n n n 32 32 32 01 01 01 s i s_i si 和掩码 L i L_i Li q q q 次询问,每次询问一个 32 32 32 01 01 01 t t t ,求出 t t t s i s_i si最长公共前缀 ≥ L i \ge L_i Li最长公共前缀最长的匹配串 s i s_i si

题解

对于每个 s s s ,将其前 i ≥ L i\ge L iL 位和 i d id id 插入到 m p [ i ] mp[i] mp[i] 中。对于每个询问 t t t ,从大到小枚举长度 i i i ,在 m p [ i ] mp[i] mp[i] 中查询 t t t 的前 i i i 位是否存在即可。注意特判 i = 0 i=0 i=0 的情况。 O ( 32 ( n + q ) ) O(32(n+q)) O(32(n+q))

#include<bits/stdc++.h>

using namespace std;

uint32_t IP2N(const int *a) {  return a[0] << 24 | a[1] << 16 | a[2] << 8 | a[3]; }

int main() { 
    int n, q, a[4];
    scanf("%d\n", &n);
    vector<string> w(n);
    unordered_map<int, int> mp[33];
    for (int L, u; n--;) { 
        scanf("%d.%d.%d.%d %d %s", a, a + 1, a + 2, a + 3, &L, w[n].data()), u = IP2N(a);
        for (int d = 0; d <= 32 - L; ++d) mp[d][u >> d] = n;
    }
    scanf("%d", &q);
    for (int64_t u; q--;) { 
        scanf("%d.%d.%d.%d", a, a + 1, a + 2, a + 3), u = IP2N(a);
        for (int d = 0; d < 33; ++d)
            if (mp[d].count(u >> d)) { 
                printf("%s%c", w[mp[d][u >> d]].data(), "\n\0"[!q]);
                break;
            }
    }
    return 0;
}

H. Mesh Analysis

队友写的。

#include <bits/stdc++.h>
using namespace std;
const int M = 500000, N = 100000;
map<int, int> id1, id2, rev;
struct line { 
    int from;
    int to;
    int id;
    int next;
};
struct line que[M + 5];
int cnt, headers[N + 5];
void add(int from, int to, int id) { 
    cnt++;
    que[cnt].from = from;
    que[cnt].to = to;
    que[cnt].id = id;
    que[cnt].next = headers[from];
    headers[from] = cnt;
}
string temp;
int main() { 
    int n, m, x, type, q, a, b, c;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) { 
        scanf("%d", &x);
        rev[x] = i;
        id1[i] = x;
        cin >> temp;
        cin >> temp;
        cin >> temp;
    }
    for (int i = 1; i <= m; i++) { 
        scanf("%d%d", &x, &type);
        id2[i] = x;
        if (type == 102) { 
            scanf("%d%d", &a, &b);
            add(a, b, x);
            add(b, a, x);

        } else { 
            scanf("%d%d%d", &a, &b, &c);
            add(a, b, x);
            add(b, a, x);
            add(a, c, x);
            add(c, a, x);
            add(b, c, x);
            add(c, b, x);
        }
    }
    // printf("FINE!\n");
    scanf("%d", &q);
    while (q--) { 
        scanf("%d", &x);
        printf("%d\n", x);
        x = rev[x];
        set<int> ele, node;
        for (int i = headers[x]; i; i = que[i].next) { 
            ele.insert(que[i].to);
            node.insert(que[i].id);
        }
        printf("[");
        bool flag = 0;
        for (auto i : ele) { 
            if (flag)
                printf(",");
            else
                flag = 1;
            printf("%d", id1[i]);
        }
        printf("]\n[");
        flag = 0;
        for (auto i : node) { 
            if (flag)
                printf(",");
            else
                flag = 1;
            printf("%d", i);
        }
        printf("]");
        if (q)
            printf("\n");
    }
    return 0;
}

I. Neiborhood Search

直接把所有数读进来,然后按题意模拟即可。

O ( n log ⁡ n ) O(n\log n) O(nlogn)

出题人赛后补充数据范围是 16 − b i t s \rm 16-bits 16bits 整数,不是很懂赛时为啥开 i n t ,   l o n g   l o n g \rm int,\ long\ long int, long long W A \rm WA WA 了。

#include<bits/stdc++.h>

const int N = 1e5 + 5;
int n, m, a[N], b[N];
int main() { 
    while (~scanf("%d", &a[++n]));
    for (int i = 1; i < n - 2; ++i)
        if (abs(a[i] - a[n - 2]) <= a[n - 1])
            b[++m] = a[i];
    std::sort(b + 1, b + m + 1);
    for (int i = m; i; --i) printf("%d ", b[i]);
    return 0;
}

J. Red-Black Paths

R → B R\rightarrow B RB 为一条红点到黑点的路径,注意到 l e n ( R → B ) × c n t ( R → B ) < 5 × 1 0 7 len(R\rightarrow B)\times cnt(R\rightarrow B)<5\times10^7 len(RB)×cnt(RB)<5×107 ,所以考虑暴力。离线,对于每个操作纪录时间。将所有边都加上,由于题目只满足 l e n ( R → B ) < 10 len(R\rightarrow B)<10 len(RB)<10 ,所以先 d f s \rm dfs dfs 标记所有能到达黑点的点,然后删掉所有边,再把那些两端点都能到达黑点的边加上。

然后对于每个红点暴力 d f s \rm dfs dfs ,遇到黑点就更新 a n s t ans_t anst t t t 表示红点染红的时间、黑点染黑的时间、路径上所有边加上的时间的最大值, t t t 可以作为 d f s \rm dfs dfs 的参数更新。对 a n s t ans_t anst 求前缀异或和,对于每个询问回答 a n s q r y i ⊕ a n s q r y i − 1 ans_{qry_i}\oplus ans_{qry_{i-1}} ansqryiansqryi1 即可。

O ( l e n ⋅ c n t ) O(len\cdot cnt) O(lencnt)

#include<bits/stdc++.h>

#define fp(i, a, b) for(int i = (a), _##i = (b) + 1; i < _##i; ++i)
using namespace std;
const int N = 1.1e5 + 5;
using arr = int[N];
arr T, col, ok, ans;
struct Edge {  int u, v, t; };
bitset<N> vis;
vector<Edge> E;
vector<pair<int, int>> G[N];

void chk(int u) { 
    vis[u] = true;
    if (col[u] == 2) ok[u] = 1;
    for (auto e: G[u]) { 
        int v = e.first;
        if (!vis[v]) chk(v);
        ok[u] |= ok[v];
    }
}

void dfs(int u, int L, int s, int t) { 
    s += u * L, ++L;
    if (col[u] == 2) ans[max(t, T[u])] ^= s;
    for (auto e: G[u]) dfs(e.first, L, s, max(t, e.second));
}

int main() { 
    int q, n = 0;
    scanf("%d", &q);
    vector<int> R, qry;
    for (int i = 1, op, u, v; i <= q; ++i) { 
        scanf("%d", &op);
        switch (op) { 
            case 1:
                scanf("%d%d", &u, &v), n = max({ n, u, v});
                G[u].emplace_back(v, i), E.push_back({ u, v, i});
                break;
            case 2: scanf("%d", &u), R.push_back(u), col[u] = 1, T[u] = i; break;
            case 3: scanf("%d", &u), col[u] = 2, T[u] = i; break;
            default: qry.push_back(i); break;
        }
    }
    fp(i, 1, n) if (!vis[i]) chk(i);
    fp(i, 1, n) vector<pair<int, int>>().swap(G[i]);
    for (auto e: E) if (ok[e.u] && ok[e.v]) G[e.u].emplace_back(e.v, e.t);
    for (auto u: R) dfs(u, 1, 0, T[u]);
    fp(i, 1, q) ans[i] ^= ans[i - 1];
    printf("%d", ans[qry[0]]);
    fp(i, 1, qry.size() - 1) printf("\n%d", ans[qry[i]] ^ ans[qry[i - 1]]);
    return 0;
}

K. Segment Routing

队友写的。注意 C a s e   # 1 : \rm Case\ \#1: Case #1: 后还有一个空格。

#include<bits/stdc++.h>

using namespace std;
const int N = 1e5 + 5;
using ll = long long;
int n, m;
vector<int> edge[N + 5];
void Solve() { 
    int x, a;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) edge[i].clear();
    for (int i = 1; i <= n; i++) { 
        scanf("%d", &x);
        for (int j = 1; j <= x; j++)
            scanf("%d", &a), edge[i].push_back(a);
    }
    int s, l;
    for (int i = 1; i <= m; i++) { 
        bool flag = 0;
        scanf("%d%d", &s, &l);
        for (int j = 1; j <= l; j++) { 
            scanf("%d", &x);
            if (flag)
                continue;
            if (edge[s].size() < x) { 
// printf("T:%d %d %d\n", s, edge[s].size(), x);
                printf("Packet Loss");
                flag = 1;
            } else s = edge[s][x - 1];
        }
        if (!flag) printf("%d", s);
        if (i != m) printf("\n");
    }
}
int main() { 
    int T;
    scanf("%d", &T);
    for (int i = 1; i <= T; ++i) { 
        printf("Case #%d: \n", i), Solve();
        if (i < T) puts("");
    }
    return 0;
}

    原文作者:Kelin__
    原文地址: https://blog.csdn.net/BeNoble_/article/details/120454819
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞