Submission #13739

#	Time	Username	Problem	Language	Result	Execution time	Memory
13739		gs14004	오두막집 (GA7_cabana)	C++14	100 / 100	2177 ms	43352 KiB

cabana

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <utility>
#include <cstring>
using namespace std;
typedef pair<int,int> pi;
vector<pi> graph[100005];

int vis[100005];
int size[100005], maxv[100005];
int imp[100005];

vector<int> cand;

int dfs(int x, int pa){
    if(vis[x]) return 0;
    cand.push_back(x);
    size[x] = 1;
    maxv[x] = 0;
    for (auto &i : graph[x]){
        if(i.second == pa) continue;
        int t = dfs(i.second,x);
        maxv[x] = max(t,maxv[x]);
        size[x] += t;
    }
    return size[x];
}

int get_center(int x){
    cand.clear();
    dfs(x,0);
    int t = x, v = 1e9;
    for (auto &i : cand){
        if(v > max((int)cand.size() - size[i],maxv[i])){
            v = max((int)cand.size() - size[i],maxv[i]);
            t = i;
        }
    }
    return t;
}

vector<int> dists[100005];
vector<int> candidate[100005];
vector<int> act_as_son[100005];
int piv;
int centre[100005];

void get_dist(int x, vector<int> &obj){
    queue<int> q, pa;
    queue<int> d;
    q.push(x);
    d.push(0);
    pa.push(0);
    while (!q.empty()) {
        int qf = q.front();
        int df = d.front();
        int pf = pa.front();
        if(imp[qf]) obj.push_back(df);
        q.pop();
        d.pop();
        pa.pop();
        for (auto &i : graph[qf]){
            if(vis[i.second]) continue;
            if(i.second == pf) continue;
            q.push(i.second);
            d.push(df + i.first);
            pa.push(qf);
        }
    }
    sort(obj.begin(),obj.end());
}

void solve(int x){
    int t = get_center(x);
    vis[t] = 1;
    get_dist(t,dists[t]);
    for (auto &i : graph[t]){
        if(vis[i.second]) continue;
        candidate[t].push_back(piv);
        get_dist(i.second,act_as_son[piv++]);
        solve(i.second);
    }
}

long long calc(int x, vector<int> &v){
    long long cnt = 0;
    int p = (int)v.size();
    for (int i=0; p && i < v.size(); i++) {
        while (p && v[i] + v[p-1] > x) p--;
        cnt += p;
    }
    return cnt;
}

long long trial(int k, int x){
    int t = get_center(x);
    vis[t] = 1;
    int p = 0;
    long long ret = calc(k,dists[t]);
    for (auto &i : graph[t]){
        if(!vis[i.second]){
            ret -= calc(k - 2 * i.first,act_as_son[candidate[t][p++]]);
        }
    }
    if(imp[t]) ret--;
    for (auto &i : graph[t]){
        if(vis[i.second]) continue;
        ret += trial(k,i.second);
    }
    return ret;
}

// 1 3 3 4 4 5 6 8 9 11

int main(){
    int n,m;
    long long k;
    scanf("%d %d %lld",&n,&m,&k);
    for (int i=2; i<=n; i++) {
        int e,x;
        scanf("%d %d",&e,&x);
        graph[e].push_back(pi(x,i));
        graph[i].push_back(pi(x,e));
    }
    while (m--) {
        int t;
        scanf("%d",&t);
        imp[t] = 1;
    }
    solve(1);
    int s = 0, e = 3e7;
    while (s != e) {
        int m = (s+e)/2;
        memset(vis,0,sizeof(vis));
        if(trial(m,1) < k * 2) s = m+1;
        else e = m;
    }
    printf("%d",s);
}

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 12 / 12
• Subtask 4: 21 / 21
• Subtask 5: 37 / 37