求dalao指点!!!官方数据AC了,Vijos上WA掉4个点,不是long long的问题。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<algorithm>
#define MAXN 50002
#define MAXM MAXN
using namespace std;
typedef long long ll;

template<typename T>
inline void getint(T &num){
    char ch;
    while(!isdigit(ch = getchar()));
    num = ch - '0';
    while(isdigit(ch = getchar())) num = (num << 1) + (num << 3) + ch - '0';
}

int n, m;
int army[MAXM];

struct tEdge{
    int np; ll w;
    tEdge *nxt; 
};

struct tGraph{
    #define MAXV MAXN
    #define MAXE (MAXN * 2)
    tEdge E[MAXE], *V[MAXV];
    int tope;
    
    tGraph(): tope(0) {}
    
    inline void addedge(int u, int v, ll w){
        E[++tope].np = v, E[tope].w = w;
        E[tope].nxt = V[u], V[u] = &E[tope];
    }
} G;

int fa[MAXN];
ll fadis[MAXN];
bool isborder[MAXN];

inline void Init_fa(int u){
    isborder[u] = 1;
    for(register tEdge *ne = G.V[u]; ne; ne = ne->nxt){
        if(ne->np == fa[u]) continue;
        fa[ne->np] = u, fadis[ne->np] = ne->w, isborder[u] = 0;
        Init_fa(ne->np);
    }
}

int jmp[16][MAXN];
ll jmpdis[16][MAXN];

inline void Init_redbl(){
    for(register int i = 1; i <= n; i++) jmp[0][i] = fa[i], jmpdis[0][i] = fadis[i];
    for(register int dbl = 1; dbl < 16; dbl++)
        for(register int i = 1; i <= n; i++){
            jmp[dbl][i] = jmp[dbl - 1][jmp[dbl - 1][i]];
            jmpdis[dbl][i] = jmpdis[dbl - 1][i] + jmpdis[dbl - 1][jmp[dbl - 1][i]];
        }
}

int dep[MAXM], insub[MAXM];

inline void Init_army(){
    for(register int i = 1; i <= m; i++){
        int cur = army[i];
        for(register int dbl = 15; dbl >= 0; dbl--)
            if(jmp[dbl][cur] > 1) dep[i] += jmpdis[dbl][cur], cur = jmp[dbl][cur];
        insub[i] = cur, dep[i] += fadis[cur];
    }
}

struct tSupply{
    int rem, id;
    inline bool operator < (const tSupply sup2) const {return rem > sup2.rem;}
} supply[MAXM];

struct tDemand{
    int req, sub;
    inline bool operator < (const tDemand dem2) const {return req > dem2.req;}
} demand[MAXM];

int tops, topd;
int mins[MAXM];  // 根的每个子树各自的军队中能走到根且剩余距离最小的编号 
bool isundercon[MAXN], used[MAXN];

inline bool dfs(int u){
    if(isundercon[u]) return 0;
    if(isborder[u]) return 1;
    for(register tEdge *ne = G.V[u]; ne; ne = ne->nxt)
        if(ne->np != fa[u] && dfs(ne->np)) return 1;
    return 0;
}

inline bool check(int tim){
    supply[0].rem = 0x3f3f3f3f;
    memset(isundercon, 0, sizeof(isundercon)), tops = 0, topd = 0;
    memset(mins, 0, sizeof(mins)), memset(used, 0, sizeof(used));
    for(register int i = 1; i <= m; i++){
        if(tim >= dep[i]){
            supply[++tops].rem = tim - dep[i], supply[tops].id = tops;
            if(supply[tops].rem < supply[mins[insub[i]]].rem) mins[insub[i]] = tops;
        }
        else{
            int cur = army[i], rem = tim;
            for(register int dbl = 15; dbl >= 0; dbl--)
                if(jmp[dbl][cur] && rem >= jmpdis[dbl][cur])
                    rem -= jmpdis[dbl][cur], cur = jmp[dbl][cur];
            isundercon[cur] = 1;
        }
    }
    for(register tEdge *ne = G.V[1]; ne; ne = ne->nxt)
        if(dfs(ne->np)) demand[++topd].req = ne->w, demand[topd].sub = ne->np;
    sort(supply + 1, supply + tops + 1), sort(demand + 1, demand + topd + 1);
    for(register int i = 1, j = 1; j <= topd; j++){
        if(mins[demand[j].sub] && !used[mins[demand[j].sub]]) {used[mins[demand[j].sub]] = 1; continue;}
        while(i <= tops && used[supply[i].id]) i++;
        if(i > tops || demand[j].req > supply[i].rem) return 0;
        used[supply[i++].id] = 1;
    }
    return 1;
}

int main(){
    getint(n);
    for(register int i = 1; i < n; i++){
        int u, v; ll w;
        getint(u), getint(v), getint(w);
        G.addedge(u, v, w), G.addedge(v, u, w);
    }
    Init_fa(1), Init_redbl();
    getint(m);
    for(register int i = 1; i <= m; i++) getint(army[i]);
    Init_army();
    int lft = 0, rt = 500000;
    while(lft < rt){
        int mid = lft + rt >> 1;
        if(check(mid)) rt = mid;
        else lft = mid + 1;
    }
    if(lft < 500000) printf("%d\n", lft);
    else printf("-1\n");
}

0 条评论

目前还没有评论...

信息

ID
1783
难度
8
分类
贪心 | 数据结构 点击显示
标签
递交数
2180
已通过
283
通过率
13%
被复制
14
上传者