oj.uz

Submission #13737

# Submission time Handle Problem Language Result Execution time Memory
13737 2015-03-30T03:14:12 Z gs14004 오두막집 (GA7_cabana) C++14
0 / 100
 142 ms 10700 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10568 KB Output is correct
2 Incorrect 0 ms 10568 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 142 ms 10700 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10568 KB Output is correct
2 Incorrect 4 ms 10568 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 10568 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 75 ms 10696 KB Output isn't correct
2 Halted 0 ms 0 KB -