oj.uz

Submission #13739

# Submission time Handle Problem Language Result Execution time Memory
13739 2015-03-30T11:49:22 Z gs14004 오두막집 (GA7_cabana) C++14
100 / 100
 2177 ms 43352 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12912 KB Output is correct
2 Correct 4 ms 12912 KB Output is correct
3 Correct 0 ms 12912 KB Output is correct
4 Correct 5 ms 12912 KB Output is correct
5 Correct 2 ms 12912 KB Output is correct
6 Correct 4 ms 12912 KB Output is correct
7 Correct 2 ms 12912 KB Output is correct
8 Correct 4 ms 12912 KB Output is correct
9 Correct 0 ms 12912 KB Output is correct
10 Correct 0 ms 12912 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 13040 KB Output is correct
2 Correct 46 ms 13400 KB Output is correct
3 Correct 73 ms 13556 KB Output is correct
4 Correct 206 ms 15468 KB Output is correct
5 Correct 589 ms 20600 KB Output is correct
6 Correct 1059 ms 33220 KB Output is correct
7 Correct 1121 ms 28540 KB Output is correct
8 Correct 1473 ms 40400 KB Output is correct
9 Correct 1327 ms 30148 KB Output is correct
10 Correct 1464 ms 38984 KB Output is correct
11 Correct 1537 ms 42952 KB Output is correct
12 Correct 1557 ms 43140 KB Output is correct
13 Correct 1441 ms 43352 KB Output is correct
14 Correct 1507 ms 43348 KB Output is correct
15 Correct 1489 ms 43348 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12912 KB Output is correct
2 Correct 4 ms 12912 KB Output is correct
3 Correct 0 ms 12912 KB Output is correct
4 Correct 0 ms 12912 KB Output is correct
5 Correct 5 ms 12912 KB Output is correct
6 Correct 0 ms 12912 KB Output is correct
7 Correct 4 ms 12912 KB Output is correct
8 Correct 0 ms 12912 KB Output is correct
9 Correct 2 ms 12912 KB Output is correct
10 Correct 0 ms 12912 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12912 KB Output is correct
2 Correct 45 ms 13300 KB Output is correct
3 Correct 211 ms 14156 KB Output is correct
4 Correct 1544 ms 18488 KB Output is correct
5 Correct 586 ms 15792 KB Output is correct
6 Correct 1078 ms 17508 KB Output is correct
7 Correct 1277 ms 19696 KB Output is correct
8 Correct 1759 ms 23824 KB Output is correct
9 Correct 1574 ms 18616 KB Output is correct
10 Correct 1749 ms 23272 KB Output is correct
11 Correct 75 ms 13304 KB Output is correct
12 Correct 1632 ms 18748 KB Output is correct
13 Correct 2069 ms 32740 KB Output is correct
14 Correct 1665 ms 18752 KB Output is correct
15 Correct 1994 ms 32220 KB Output is correct
16 Correct 1560 ms 18476 KB Output is correct
17 Correct 1602 ms 18476 KB Output is correct

Subtask #5
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 13040 KB Output is correct
2 Correct 54 ms 13300 KB Output is correct
3 Correct 72 ms 13304 KB Output is correct
4 Correct 226 ms 14548 KB Output is correct
5 Correct 714 ms 17912 KB Output is correct
6 Correct 1456 ms 25604 KB Output is correct
7 Correct 1464 ms 23452 KB Output is correct
8 Correct 1954 ms 30588 KB Output is correct
9 Correct 1811 ms 23292 KB Output is correct
10 Correct 1979 ms 31952 KB Output is correct
11 Correct 2008 ms 31804 KB Output is correct
12 Correct 2103 ms 35540 KB Output is correct
13 Correct 2177 ms 32588 KB Output is correct
14 Correct 2066 ms 36196 KB Output is correct
15 Correct 2024 ms 32532 KB Output is correct
16 Correct 1551 ms 40544 KB Output is correct
17 Correct 393 ms 24804 KB Output is correct
18 Correct 1255 ms 34088 KB Output is correct