---
tags: IOICamp
---

# Day4 個人賽

:::spoiler Description
pG 被砍ㄌQQ
:::

:::spoiler Scoreboard
:::

:::spoiler pA**
:::

:::spoiler pB
:::

:::spoiler pC**
:::

:::spoiler pD**
[Sample Input](https://www.csie.ntu.edu.tw/~b08902100/sample.in) [Sample Output](https://www.csie.ntu.edu.tw/~b08902100/sample.ans)
:::

:::spoiler pE
:::

:::spoiler pF**
:::

:::spoiler pG
:::

---

[TOC]

#### **pA. 可愛的優希**

#### **pB. 最短路 feat. 紅綠燈**

:::spoiler Solution (SorahISA)

#pragma GCC optimize("Ofast", "unroll-loops")

#include <bits/stdc++.h>
using namespace std;

using lli = long long;
using pii = pair<lli, int>;

#define Push push_back
#define X first
#define Y second

#ifdef LOCAL
    inline int nextint() {
        int n; scanf("%d", &n);
        return n;
    }

    inline lli nextlli() {
        lli n; scanf("%lld", &n);
        return n;
    }
#else
    inline char readchar() {
    #define B 1048576
        static char buf[B], *p, *q;
        if(p == q and (q = (p = buf) + fread(buf, 1, B, stdin)) == buf) return EOF;
        return *p++;
    #undef B
    }

    inline int nextint() {
        int x = 0, c = readchar();
        while('0' >  c  or c >  '9') c = readchar();
        while('0' <= c and c <= '9') x = x * 10 + (c ^ '0'), c = readchar();
        return x;
    }

    inline lli nextlli() {
        lli x = 0, c = readchar();
        while('0' >  c  or c >  '9') c = readchar();
        while('0' <= c and c <= '9') x = x * 10 + (c ^ '0'), c = readchar();
        return x;
    }
#endif

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
auto gen = bind(uniform_int_distribution<int>(1, 1E9), rng);

static inline uint64_t rotl(const uint64_t x, int k) {
    return (x << k) | (x >> (64 - k));
}

static uint64_t s[2] = {18444, 78745145}; // init seed

uint64_t RandomBigInt() {
    uint64_t s0 = s[0], s1 = s[1], result = s0 + s1;
    s1 ^= s0;
    s[0] = rotl(s0, 24) ^ s1 ^ (s1 << 16);
    s[1] = rotl(s1, 37);
    return result;
}

const int maxn = 2E5 + 5;

vector<pair<int, lli>> adj[maxn];
lli ai[maxn], bi[maxn];
lli minT[maxn];
bool vis[maxn];

lli check_time(int nowNode, lli nowTime) {
    /// ai, ai+2bi, ai+4bi, ai+6bi ... ///
    if (nowTime < ai[nowNode]) {
        return nowTime;
    }
    nowTime -= ai[nowNode];
    if (nowTime % (2 * bi[nowNode]) >= bi[nowNode]) {
        return nowTime + ai[nowNode];
    }
    else {
        return nowTime / bi[nowNode] * bi[nowNode] + bi[nowNode] + ai[nowNode];
    }
}

priority_queue<pii, vector<pii>, greater<pii>> pq;

void dijkstra(int now, int goal) {
    for (auto x : adj[now]) {
        if (vis[x.X]) continue;
        if (x.X == goal) {
            lli tmp = minT[now] + x.Y;
            if (tmp < minT[x.X]) {
                minT[x.X] = tmp;
            }
        }
        else {
            lli tmp = check_time(x.X, minT[now] + x.Y);
            if (tmp < minT[x.X]) {
                minT[x.X] = tmp;
                pq.push({minT[x.X], x.X});
            }
        }
    }
    
    while (!pq.empty()) {
        pii nxt = pq.top(); pq.pop();
        if (vis[nxt.Y]) continue;
        vis[nxt.Y] = 1;
        dijkstra(nxt.Y, goal);
    }
}

int main() {
    memset(minT, 0x3f, sizeof(minT));
    
    int n = nextint(), m = nextint(), s = nextint() - 1, t = nextint() - 1, u, v;
    lli w;
    
    for (int i = 0; i < n; ++i) {
        ai[i] = nextlli();
        bi[i] = nextlli();
    }
    
    for (int i = 0; i < m; ++i) {
        u = nextint() - 1;
        v = nextint() - 1;
        w = nextlli();
        adj[u].Push({v, w});
        adj[v].Push({u, w});
    }
    
    vis[s] = 1;
    minT[s] = 0;
    dijkstra(s, t);
    
    printf("%lld\n", minT[t]);
    
    return 0;
}

:::

#### **pC. 彗星**

#### **pD. 小風愛貓咪**

#### **pE. 小風愛迴文**

:::spoiler Solution (SorahISA)

#pragma GCC optimize("Ofast", "unroll-loops")

#include <bits/stdc++.h>
using namespace std;

using lli = long long;

#ifdef LOCAL
    inline int nextint() {
        int n; scanf("%d", &n);
        return n;
    }

    inline lli nextlli() {
        lli n; scanf("%lld", &n);
        return n;
    }
#else
    inline char readchar() {
    #define B 1048576
        static char buf[B], *p, *q;
        if(p == q and (q = (p = buf) + fread(buf, 1, B, stdin)) == buf) return EOF;
        return *p++;
    #undef B
    }

    inline int nextint() {
        int x = 0, c = readchar();
        while('0' >  c  or c >  '9') c = readchar();
        while('0' <= c and c <= '9') x = x * 10 + (c ^ '0'), c = readchar();
        return x;
    }

    inline lli nextlli() {
        lli x = 0, c = readchar();
        while('0' >  c  or c >  '9') c = readchar();
        while('0' <= c and c <= '9') x = x * 10 + (c ^ '0'), c = readchar();
        return x;
    }
#endif

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
auto gen = bind(uniform_int_distribution<int>(1, 1E9), rng);

static inline uint64_t rotl(const uint64_t x, int k) {
    return (x << k) | (x >> (64 - k));
}

static uint64_t s[2] = {18444, 78745145}; // init seed

uint64_t RandomBigInt() {
    uint64_t s0 = s[0], s1 = s[1], result = s0 + s1;
    s1 ^= s0;
    s[0] = rotl(s0, 24) ^ s1 ^ (s1 << 16);
    s[1] = rotl(s1, 37);
    return result;
}

const int maxn = 2E5 + 5;

vector<int> adj[maxn];
int num[maxn];
bool vis[maxn];

void dfs(int now, int fil) {
//    printf("fill %d with %d\n", now, fil);
    num[now] = fil;
    vis[now] = 1;
    for (auto x : adj[now]) {
        if (!vis[x]) dfs(x, fil);
    }
}

int main() {
    int n = nextint();
    
    int v[n];
    for (int i = 0; i < n; ++i) v[i] = nextint();
    
    for (int i = 1; i < n; ++i) {
        if (v[i] != 1) {
            adj[i].push_back(i - v[i] + 1);
            adj[i - v[i] + 1].push_back(i);
        }
    }
    
    for (int i = 0; i < n; ++i) {
        if (!vis[i]) dfs(i, i + 1);
    }
    
    for (int i = 0; i < n; ++i) cout << num[i] << " \n"[i == n-1];
    
    return 0;
}

:::

#### **pF. 美麗的座位**

#### **pG. 小風愛種樹 (被砍掉ㄌQQ)**

:::spoiler Solution (SorahISA, did not test)

#pragma GCC optimize("Ofast", "unroll-loops")

#include <bits/stdc++.h>
using namespace std;

using lli = long long;

#define Push push_back

#ifdef LOCAL
    inline int nextint() {
        int n; scanf("%d", &n);
        return n;
    }

    inline lli nextlli() {
        lli n; scanf("%lld", &n);
        return n;
    }
#else
    inline char readchar() {
    #define B 1048576
        static char buf[B], *p, *q;
        if(p == q and (q = (p = buf) + fread(buf, 1, B, stdin)) == buf) return EOF;
        return *p++;
    #undef B
    }

    inline int nextint() {
        int x = 0, c = readchar();
        while('0' >  c  or c >  '9') c = readchar();
        while('0' <= c and c <= '9') x = x * 10 + (c ^ '0'), c = readchar();
        return x;
    }

    inline lli nextlli() {
        lli x = 0, c = readchar();
        while('0' >  c  or c >  '9') c = readchar();
        while('0' <= c and c <= '9') x = x * 10 + (c ^ '0'), c = readchar();
        return x;
    }
#endif

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
auto gen = bind(uniform_int_distribution<int>(1, 1E9), rng);

static inline uint64_t rotl(const uint64_t x, int k) {
    return (x << k) | (x >> (64 - k));
}

static uint64_t s[2] = {18444, 78745145}; // init seed

uint64_t RandomBigInt() {
    uint64_t s0 = s[0], s1 = s[1], result = s0 + s1;
    s1 ^= s0;
    s[0] = rotl(s0, 24) ^ s1 ^ (s1 << 16);
    s[1] = rotl(s1, 37);
    return result;
}

const int maxn = 5E5 + 5;
const int lgmx = 19 + 1;

int num[maxn], inv[maxn], dep[maxn], par[maxn][lgmx], tok = 0;
vector<int> adj[maxn];

void dfs(int now, int lst) {
    for (auto x : adj[now]) {
        if (x == lst) continue;
        par[x][0] = now;
        dep[x] = dep[now] + 1;
        ++tok;
        num[x] = tok;
        inv[tok] = x;
        dfs(x, now);
    }
}

void build(int n) {
    for (int t = 1; t < lgmx; ++t) {
        for (int i = 1; i <= n; ++i) {
            par[inv[i]][0] = par[par[inv[i]][0]][0];
        }
    }
}

int lca(int u, int v) {
    if (u == v) return u;
    if (dep[u] < dep[v]) swap(u, v);
    
    for (int i = lgmx-1; i >= 0; --i) {
        if (dep[par[u][i]] >= dep[v]) {
            u = par[u][i];
        }
    }
    
    if (u == v) return u;
    
    for (int i = lgmx-1; i >= 0; --i) {
        if (par[u][i] != par[v][i]) {
            u = par[u][i]; v = par[v][i];
        }
    }
    
    return par[u][0];
}

int main() {
    int n = nextint(), q = nextint(), u, v, L, x, y, lastans;
    
    for (int i = 0; i < n-1; ++i) {
        u = nextint(); v = nextint();
        adj[u].Push(v); adj[v].Push(u);
    }
    
    L = n;
    for (int i = 0; i < q; ++i) {
        ++L;
        x = nextint(); y = nextint();
        /// y^lastans = L -> y^L = lastans ///
        lastans = y ^ L;
        
        x ^= lastans; y ^= lastans;
        adj[x].Push(y); adj[y].Push(x);
        
        if (i) printf("%d\n", lastans);
    }
    
    /// LCA find diameter ///
    
    dep[1] = 0;
    dfs(1, 0);
    build(n);
    
    int _now = 1, maxDis = 0, _tmp;
    for (int i = 1; i <= n+q; ++i) {
        if (dep[i] > dep[_now]) _now = i;
    }
    
    for (int i = 1; i <= n+q; ++i) {
        _tmp = dep[_now] + dep[i] - 2 * dep[lca(_now, i)];
        if (_tmp > maxDis) maxDis = _tmp;
    }
    
    printf("%d\n", maxDis);
    
    return 0;
}

:::