Submission #13737

#	Time	Username	Problem	Language	Result	Execution time	Memory
13737		gs14004	오두막집 (GA7_cabana)	C++14	0 / 100	142 ms	10700 KiB

cabana

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <utility>
#include <cstring>
using namespace std;
typedef pair<int,int> pi;
typedef long long lint;

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<lint> dists[100005];
vector<lint> act_as_son[100005];
int centre[100005];

// Naive(T,K) - Sum(Naive(STi,K - 2Li) - 1 / 2

void get_dist(int x, vector<lint> &obj){
    queue<int> q, pa;
    queue<lint> d;
    q.push(x);
    d.push(0);
    pa.push(0);
    while (!q.empty()) {
        int qf = q.front();
        lint 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;
        get_dist(i.second,act_as_son[i.second]);
        solve(i.second);
    }
}

lint calc(lint x, vector<lint> &v){
    long long cnt = 0;
    for (int i=0; i<v.size(); i++) {
        for (int j=0; j<v.size(); j++) {
            if(v[i] + v[j] <= x) cnt++;
        }
    }
    return cnt;
}

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

int main(){
    int n,m;
    lint 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);
    lint s = 0, e = 1e10;
    while (s != e) {
        lint m = (s+e)/2;
        memset(vis,0,sizeof(vis));
        lint dbg = trial(m,1);
        if(dbg / 2 < k) s = m+1;
        else e = m;
    }
    printf("%lld",s);
}

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