比賽鏈接

A. Busiest Computing Nodes

把每個請求分成開始請求（開始時間）和結束請求（結束時間），對請求按時間排序，先在 s e t \rm set set 中插入 0 ～ k ? 1 0\sim k -1 0～k?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 中洗掉，
對于每個結束請求，如果對應的開始請求被處理了，就把處理開始請求的機器放回 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 i→i+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 ，操作可以簡化為：

對一個子樹做取 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) ；
永久將一顆子樹的 f f f 置為 0 ；
詢問節點 u u u 的 max ? ( f u , g u ) \max(f_u,g_u) max(fu?,gu?) ；
詢問一顆子樹的最大的 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 i≥L 位和 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 16?bits 整數，不是很懂賽時為啥開 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 R→B 為一條紅點到黑點的路徑，注意到 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(R→B)×cnt(R→B)<5×107 ，所以考慮暴力，離線，對于每個操作紀錄時間，將所有邊都加上，由于題目只滿足 l e n ( R → B ) < 10 len(R\rightarrow B)<10 len(R→B)<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}} ansqryi??⊕ansqryi?1?? 即可，

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

#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;
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/302836.html

標籤：其他

上一篇：HTML+CSS+JS實作 ??love520愛心表白??

下一篇：特斯拉完全自動駕駛涉嫌誤導性宣傳，媒體批評馬斯克：怕不是個PUA大師？

The 2021 ICPC Asia Regionals Online Contest (I)