[Luogu P4149] [IOI2011]Race

[Luogu P4149]  [IOI2011]Race

思路

点分治,每次分治时要维护一个$cnt_i$,表示以分治点为起点,长度为$i$的路径最少由几条边构成。

垃圾Luogu超时会报RE,我一开始还以为是哪里指针指错地方了,结果看了半天没有啊,原来是用memset导致超时了Orz

bzoj也好垃圾啊,这题居然是权限题QAQ,明明同年IOI另外两道题就不是

代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define max_n 200010
#define max_k 1000010
 
struct Edge;
struct Node{
    Edge *head;
    bool vis;
    int siz, mx, dep, len;
}node[max_n], *root;
struct Edge{
    Node *to;
    Edge *ne;
    int val;
    Edge(int x, int y, int z) : to(&node[y]), ne(node[x].head), val(z){}
};
int N, K, SumSiz, cnt[max_k], ans=0x3f3f3f3f;
 
void getroot(Node *x, Node *fa){
    x->siz=1, x->mx=0;
    for(Edge *i=x->head; i; i=i->ne){
        if(i->to==fa || i->to->vis)    continue;
        getroot(i->to, x);
        x->siz+=i->to->siz;
        x->mx=max(x->mx, i->to->siz);
    }
    x->mx=max(x->mx, SumSiz-x->siz);
    if(root==NULL)  root=x;
    if(x->mx<root->mx) root=x;
}
 
void dfs1(Node *x, Node *fa){
    if(x->dep>K)  return;
    ans=min(ans, cnt[K-x->dep]+x->len);
    for(Edge *i=x->head; i; i=i->ne){
        if(i->to->vis || i->to==fa)    continue;
        i->to->len=x->len+1;
        i->to->dep=x->dep+i->val;
        dfs1(i->to, x);
    }
}
 
void dfs2(Node *x, Node *fa, bool fl){
    if(x->dep>K)  return;
    if(fl)	cnt[x->dep]=min(cnt[x->dep], x->len);
    else	cnt[x->dep]=0x3f3f3f3f;
    for(Edge *i=x->head; i; i=i->ne){
        if(i->to->vis || i->to==fa)    continue;
        dfs2(i->to, x, fl);
    }
}
 
void divide(Node *x){
    x->vis=true;
    cnt[0]=0;
    for(Edge *i=x->head; i; i=i->ne){
        if(i->to->vis)    continue;
        i->to->dep=i->val;
        i->to->len=1;
        dfs1(i->to, x);
        dfs2(i->to, x, true);
    }
    for(Edge *i=x->head; i; i=i->ne)
    	if(!i->to->vis)
    		dfs2(i->to, x, false);
    for(Edge *i=x->head; i; i=i->ne){
        if(i->to->vis)    continue;
        SumSiz=i->to->siz, root=NULL;
        getroot(i->to, x);
        divide(root);
    }
}
 
int main(){
    int x, y, z;
    memset(cnt, 0x3f3f3f3f, sizeof(cnt));
    scanf("%d%d", &N, &K);
    for(int i=1; i<N; i++){
        scanf("%d%d%d", &x, &y, &z);
        x++, y++;
        node[x].head=new Edge(x, y, z);
        node[y].head=new Edge(y, x, z);
    }
    root=NULL, SumSiz=N;
    getroot(&node[1], NULL);
    divide(root);
    cout<<(ans==0x3f3f3f3f ? -1 : ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注