列表

详情

NC19460. Tower Attack

描述

There was a civil war between two factions in Skyrim, a province of the Empire on the continent of Tamriel. The

Stormcloaks, led by Ulfric Stormcloak, are made up of Skyrim's native Nord race. Their goal is an independent

Skyrim free from Imperial interference. The Imperial Legion, led by General Tullius, is the military of the Empire

that opposes the Stormcloaks and seeks to reunite and pacify the province.

The current target of Ulfric Stormcloak is to attack Whiterun City, which is under controlled by General Tullius.

Near by this city there are N  towers under the Empire's control. There are N - 1 roads linking these towers, so

soldiers can move from any tower to another one through these roads.

In military affairs, tactical depth means the longest path between two of all towers. Larger the tactical depth is,

more stable these towers are.

Your mission, should you choose to accept it. In each turn, Ulfric tells you two roads. You need to figure out the

tactical depth after destroying these two roads.



输入描述

The first line of input contains an integer t which is the number of test cases. Then t test cases follow. For each test
case, the first line contains two integers N (N  <= 100000), representing the number of towers, and Q (Q <= 100000),
represeting the number of queries.
In the next N - 1 lines, the i-th line describes the i-th road and contains three integers u, v and w (0  <= w <= 5000)
corressponding to a path between u and v of length w .
In the next Q lines, each line contains two integers u and v representing that the u -th road and the v -th road would
be destroyed in this turn. It is guaranteed that u != v .

输出描述

For each query, output the tactical depth.

示例1

输入: 

1
8 3
2 1 7
3 1 7
4 2 5
5 2 6
4 6 3
7 2 8
1 8 2
4 6
2 3
5 6

输出: 

22
17
20

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 2909ms, 内存消耗: 43136K, 提交时间: 2018-10-07 12:26:20 

#include <stdio.h>
#include <algorithm>

using namespace std;

const int N = 2e5 + 5;

int T, n, m;

int len, head[N], ST[20][N];

struct edge{int u, v, w;}ee[N];

int cnt, fa[N], log_2[N], st[N], en[N], dfn[N], dis[N], dep[N], pos[N];

struct edges{int to, next, cost;}e[N];

inline void add(int u, int v, int w) {
    e[++ len] = (edges){v, head[u], w}, head[u] = len;
    e[++ len] = (edges){u, head[v], w}, head[v] = len;
}

inline void dfs1(int u) {
    st[u] = ++ cnt, dfn[cnt] = u;
    for (int v, i = head[u]; i; i = e[i].next) {
        v = e[i].to;
        if (v == fa[u]) continue;
        fa[v] = u, dep[v] = dep[u] + 1;
        dis[v] = dis[u] + e[i].cost, dfs1(v);
    }
    en[u] = cnt;
}

inline void dfs2(int u) {
    dfn[++ cnt] = u, pos[u] = cnt;
    for (int v, i = head[u]; i; i = e[i].next) {
        v = e[i].to;
        if (v == fa[u]) continue;
        dfs2(v), dfn[++ cnt] = u;
    }
}

int mmin(int x, int y) {
    if (dep[x] < dep[y]) return x;
    return y;
}

inline int lca(int u, int v) {
    static int w;
    if (pos[u] > pos[v]) swap(u, v);
    w = log_2[pos[v] - pos[u] + 1];
    return mmin(ST[w][pos[u]], ST[w][pos[v] - (1 << w) + 1]);
}

inline int dist(int u, int v) {
    int Lca = lca(u, v);
    return dis[u] + dis[v] - dis[Lca] * 2;
}

inline void build() {
    for (int i = 1; i <= cnt; i ++)
        ST[0][i] = dfn[i];
    for (int i = 1; i < 20; i ++)
        for (int j = 1; j <= cnt; j ++)
            if (j + (1 << (i - 1)) > cnt) ST[i][j] = ST[i - 1][j];
            else ST[i][j] = mmin(ST[i - 1][j], ST[i - 1][j + (1 << (i - 1))]); 
}

int M;

struct node {
    int l, r, dis;
}tr[N << 1];

inline void update(int o, int o1, int o2) {
    static int d;
    static node tmp;
    if (tr[o1].dis == -1) {tr[o] = tr[o2]; return;}
    if (tr[o2].dis == -1) {tr[o] = tr[o1]; return;}
    if (tr[o1].dis > tr[o2].dis) tmp = tr[o1];
    else tmp = tr[o2]; 
    d = dist(tr[o1].l, tr[o2].l);
    if (d > tmp.dis) tmp.l = tr[o1].l, tmp.r = tr[o2].l, tmp.dis = d;
    d = dist(tr[o1].l, tr[o2].r);
    if (d > tmp.dis) tmp.l = tr[o1].l, tmp.r = tr[o2].r, tmp.dis = d;
    d = dist(tr[o1].r, tr[o2].l);
    if (d > tmp.dis) tmp.l = tr[o1].r, tmp.r = tr[o2].l, tmp.dis = d;
    d = dist(tr[o1].r, tr[o2].r);
    if (d > tmp.dis) tmp.l = tr[o1].r, tmp.r = tr[o2].r, tmp.dis = d;
    tr[o] = tmp;
}

inline void ask(int s, int t) {
    if (s > t) return;
    for (s += M - 1, t += M + 1; s ^ t ^ 1; s >>= 1, t >>= 1) {
        if (~s&1) update(0, 0, s ^ 1);
        if ( t&1) update(0, 0, t ^ 1);
    }
}

inline int get_char() {
    static const int SIZE = 1 << 23;
    static char *T, *S = T, buf[SIZE];
    if (S == T) {
        T = fread(buf, 1, SIZE, stdin) + (S = buf);
        if (S == T) return -1;
    }
    return *S ++;
}
 
inline void in(int &x) {
    static int ch;
    while (ch = get_char(), ch > 57 || ch < 48);x = ch - 48;
    while (ch = get_char(), ch > 47 && ch < 58) x = x * 10 + ch - 48;
}

int main() {
    int u, v, w, ans;
    log_2[1] = 0;
    for (int i = 2; i <= 200000; i ++) 
        if (i == 1 << (log_2[i - 1] + 1))
            log_2[i] = log_2[i - 1] + 1;
        else log_2[i] = log_2[i - 1];
    for (in(T); T --; ) {
        in(n), in(m), cnt = len = 0;
        for (int i = 1; i <= n; i ++)
            head[i] = 0;
        for (int i = 1; i < n; i ++) {
            in(ee[i].u), in(ee[i].v), in(ee[i].w);
            add(ee[i].u, ee[i].v, ee[i].w);
        }
        dfs1(1);
        for (M = 1; M < n + 2; M <<= 1);
        for (int i = 1; i <= n; i ++)
            tr[i + M].l = tr[i + M].r = dfn[i], tr[i + M].dis = 0;
        for (int i = n + M + 1; i <= (M << 1) + 1; i ++)
            tr[i].dis = -1;
        cnt = 0, dfs2(1), build();
        for (int i = M; i; i --) 
            update(i, i << 1, i << 1 | 1);
        for (int i = 1; i < n; i ++) 
            if (dep[ee[i].u] > dep[ee[i].v])
                swap(ee[i].u, ee[i].v);
        for (int u, v, i = 1; i <= m; i ++) {
            in(u), in(v), ans = 0;
            u = ee[u].v, v = ee[v].v, w = lca(u, v);
            if (w == u || w == v) {
                if (w != u) swap(u, v);
                tr[0].dis = -1, ask(1, st[u] - 1), ask(en[u] + 1, n), ans = max(ans, tr[0].dis);
                tr[0].dis = -1, ask(st[u], st[v] - 1), ask(en[v] + 1, en[u]), ans = max(ans, tr[0].dis);
                tr[0].dis = -1, ask(st[v], en[v]), ans = max(ans, tr[0].dis);
            }
            else {
                if (st[u] > st[v]) swap(u, v);
                tr[0].dis = -1, ask(1, st[u] - 1), ask(en[u] + 1, st[v] - 1), ask(en[v] + 1, n), ans = max(ans, tr[0].dis);
                tr[0].dis = -1, ask(st[u], en[u]), ans = max(ans, tr[0].dis);
                tr[0].dis = -1, ask(st[v], en[v]), ans = max(ans, tr[0].dis);
            }
            printf("%d\n", ans);
        }
    }
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 4325ms, 内存消耗: 48512K, 提交时间: 2018-10-09 10:46:01 

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cassert>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<queue>
#include<utility>
#include<bitset>
#include<complex>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<stack>

using namespace std;

#define mem(a,b) memset(a,b,sizeof(a))
#define REP(i,a,b) for(int i=a; i<=b; ++i)
#define PER(i,a,b) for(int i=a; i>=b; --i)
#define MP make_pair
#define PB push_back
#define fi first
#define se second
#define lson (x<<1)
#define rson (x<<1|1)
#define mid ((l+r)>>1)
typedef long long LL;
typedef pair<int,int> pii;

const int maxn = 1e5;
const int Step = 16;

int n, m;
int uu[maxn+5], ww[maxn+5];
int dep[maxn+5], dis[maxn+5], st[maxn+5][Step+2];
vector<pii> G[maxn+5];

int DFN, dfn[maxn+5], in[maxn+5], out[maxn+5];
void dfs(int x, int p, int id) {
    in[x] = ++DFN, dfn[DFN] = x;
    uu[id] = x;
    dep[x] = dep[p]+1, dis[x] = dis[p]+ww[id];
    mem(st[x],0);
    st[x][0] = p;
    for(int i = 0; st[x][i]; ++i) st[x][i+1] = st[st[x][i]][i];
    for(auto pp : G[x]) if(pp.fi!=p) {
        dfs(pp.fi, x, pp.se);
    }
    out[x] = DFN;
}

int LCA(int u, int v) {
    if(u==v) return u;
    if(dep[u]<dep[v]) swap(u,v);
    int del = dep[u]-dep[v];
    for(int i = Step; i >= 0; --i)
        if(del>>i&1) u = st[u][i];
    if(u==v) return u;
    for(int i = Step; i >= 0; --i)
        if(st[u][i]!=st[v][i])
            u = st[u][i], v = st[v][i];
    return st[u][0];
}

int GetDist(int u, int v) {
    return dis[u] + dis[v] - dis[LCA(u,v)]*2;
}

struct Node {
    int p1, p2, d;
    Node() {}
    Node(int _p1, int _p2, int _d) : p1(_p1), p2(_p2), d(_d) {}
    void Merge(Node a) {
        if(d==-1) { p1 = a.p1, p2 = a.p2, d = a.d; return; }
        int tp1 = p1, tp2 = p2;
        if(d < a.d) p1 = a.p1, p2 = a.p2, d = a.d;
        int tmp;
        tmp = GetDist(tp1, a.p1);
        if(d < tmp) p1 = tp1, p2 = a.p1, d = tmp;

        tmp = GetDist(tp1, a.p2);
        if(d < tmp) p1 = tp1, p2 = a.p2, d = tmp;

        tmp = GetDist(tp2, a.p1);
        if(d < tmp) p1 = tp2, p2 = a.p1, d = tmp;

        tmp = GetDist(tp2, a.p2);
        if(d < tmp) p1 = tp2, p2 = a.p2, d = tmp;
    }
};

Node rmq[maxn+5][Step+2];
void Build() {
    REP(i,1,n) rmq[i][0] = Node(dfn[i], dfn[i], 0);
    for(int k = 1; (1<<k) <= n; ++k) {
        for(int i = 1; i+(1<<k)-1 <= n; ++i) {
            rmq[i][k] = rmq[i][k-1];
            rmq[i][k].Merge( rmq[i+(1<<(k-1))][k-1] );
        }
    }
}

Node Query(int l, int r) {
    int k = 0, t = 1;
    while(l+t-1 < r-t+1) ++k, t<<=1;
    Node ret = rmq[l][k];
    ret.Merge( rmq[r-t+1][k] );
    return ret;
}

int main() {
    int _; scanf("%d", &_);
    while(_--) {
        scanf("%d%d", &n, &m);
        REP(i,1,n) G[i].clear();
        for(int i = 1, u,v,w; i < n; ++i) {
            scanf("%d%d%d", &u, &v, &w);
            ww[i] = w;
            G[u].PB( pii(v,i) );
            G[v].PB( pii(u,i) );
        }
        DFN = 0;
        dfs(1,0,0);
        //REP(i,1,n) printf("dfn[%d] = %d\n", i, dfn[i]);
        Build();
        while(m--) {
            int e1, e2; scanf("%d%d", &e1, &e2);
            int l1 = in[uu[e1]], r1 = out[uu[e1]];
            int l2 = in[uu[e2]], r2 = out[uu[e2]];
            if(l1>l2) swap(l1,l2), swap(r1,r2);
            if(r1 < l2) {
                Node ans1 = Query(l1, r1);
                Node ans2 = Query(l2, r2);
                Node ans3 = Node(-1,-1,-1);
                if(l1-1>=1) ans3.Merge( Query(1,l1-1) );
                if(r1+1<=l2-1) ans3.Merge( Query(r1+1,l2-1) );
                if(r2+1<=n) ans3.Merge( Query(r2+1,n) );
                printf("%d\n", max(ans1.d, max(ans2.d,ans3.d)) );
            }
            else {
                Node ans1 = Query(l2, r2);
                Node ans2 = Node(-1,-1,-1);
                if(l1-1>=1) ans2.Merge( Query(1,l1-1) );
                if(r1+1<=n) ans2.Merge( Query(r1+1,n) );
                Node ans3 = Node(-1,-1,-1);
                if(l1<=l2-1) ans3.Merge( Query(l1,l2-1) );
                if(r2+1<=r1) ans3.Merge( Query(r2+1,r1) );
                printf("%d\n", max(ans1.d, max(ans2.d,ans3.d)) );
            }
        }
    }
    return 0;
}

上一题

© 2024 nowcoder.com