oj.uz

Submission #32001

# Submission time Handle Problem Language Result Execution time Memory
32001 2017-09-21T07:39:11 Z kazel 오두막집 (GA7_cabana) C++14
77 / 100
 6000 ms 20292 KB 
#include<bits/stdc++.h>
using namespace std;

struct edge
{
    int t, w;
    edge(int t, int w) : t(t), w(w) {}
};

vector<edge> g[100005];
bool b[100005], v[100005];
int cnt[100005], cb[100005], d;
long long k;
vector<int> ord;

void init(int c, int p)
{
    cnt[c] = 1;
    cb[c] += b[c];
    for(auto e : g[c])
    {
        if(e.t == p) continue;
        init(e.t,c);
        cnt[c] += cnt[e.t];
        cb[c] += cb[e.t];
    }
}

int center(int c)
{
    int n = cnt[c], m = cb[c];
    int mxi = 0;
    for(auto e : g[c])
    {
        if(v[e.t]) continue;
        if(cnt[e.t] > cnt[mxi])
            mxi = e.t;
    }
    if(cnt[mxi]>n/2)
    {
        cnt[c] = n - cnt[mxi];
        cb[c] = m - cb[mxi];
        cnt[mxi] = n;
        cb[mxi] = m;
        return center(mxi);
    }
    return c;
}

void dfs(int c, int p, int w, vector<int> & cu)
{
    if(w > d) return;
    if(b[c]) cu.push_back(w);
    for(auto e : g[c])
    {
        if(e.t == p || v[e.t]) continue;
        dfs(e.t,c,w+e.w,cu);
    }
}

long long foo()
{
    long long ret = 0;
    memset(v,0,sizeof(v));
    for(int i : ord)
    {
        v[i] = true;
        map<int,int> pr;
        if(b[i]) pr[0] = 1;
        for(auto e : g[i])
        {
            if(v[e.t]) continue;
            vector<int> cu;
            vector<pair<int,int>> cs;
            dfs(e.t,i,e.w,cu);
            sort(cu.begin(),cu.end());
            int sum = 0, sz = cu.size();
            for(int j=0;j<sz;j++)
            {
                sum++;
                if(j+1<sz && cu[j] == cu[j+1]) continue;
                cs.emplace_back(cu[j],sum);
            }
            for(auto p : pr)
            {
                long long b = p.second;
                while(!cs.empty() && cs.back().first+p.first > d) cs.pop_back();
                if(cs.empty()) break;
                ret += b * cs.back().second;
                if(ret > k) return ret;
            }
            for(int p : cu)
                pr[p]++;
        }
    }
    return ret;
}

int main()
{
    int n,m,l=1,r=0;
    scanf("%d%d%lld",&n,&m,&k);
    for(int i=2;i<=n;i++)
    {
        int a,w;
        scanf("%d%d",&a,&w);
        g[i].push_back(edge(a,w));
        g[a].push_back(edge(i,w));
        r += w;
    }
    for(int i=0;i<m;i++)
    {
        int x;
        scanf("%d",&x);
        b[x] = true;
    }
    init(1,0);
    queue<int> q;
    q.push(1);
    while(!q.empty())
    {
        int r = q.front();
        q.pop();
        if(cb[r]<2) continue;
        r = center(r);
        ord.push_back(r);
        v[r] = true;
        sort(g[r].begin(),g[r].end(),[](edge & a, edge & b){
                return cb[a.t] < cb[b.t];
                });
        for(auto e : g[r])
        {
            if(v[e.t]) continue;
            q.push(e.t);
        }
    }
    int ans = r--;
    while(r>=l)
    {
        d = (l+r)/2;
        if(foo()>=k)
        {
            ans = d;
            r = d - 1;
        }
        else l = d + 1;
    }
    printf("%d\n",ans);
}

Compilation message

cabana.cpp: In function 'int main()':
cabana.cpp:102:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%lld",&n,&m,&k);
                               ^
cabana.cpp:106:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&a,&w);
                            ^
cabana.cpp:114:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&x);
                       ^

Subtask #1
7.0 / 7.0

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

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5480 KB Output is correct
2 Correct 16 ms 5788 KB Output is correct
3 Correct 6 ms 5984 KB Output is correct
4 Correct 149 ms 7232 KB Output is correct
5 Correct 573 ms 10300 KB Output is correct
6 Correct 3539 ms 15812 KB Output is correct
7 Correct 2286 ms 15020 KB Output is correct
8 Correct 4159 ms 19300 KB Output is correct
9 Correct 1373 ms 15724 KB Output is correct
10 Correct 4736 ms 19000 KB Output is correct
11 Correct 5336 ms 19936 KB Output is correct
12 Correct 4746 ms 20060 KB Output is correct
13 Execution timed out 6000 ms 20292 KB Execution timed out
14 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

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

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5348 KB Output is correct
2 Correct 0 ms 5612 KB Output is correct
3 Correct 6 ms 6140 KB Output is correct
4 Correct 83 ms 9044 KB Output is correct
5 Correct 26 ms 7196 KB Output is correct
6 Correct 53 ms 8120 KB Output is correct
7 Correct 69 ms 8648 KB Output is correct
8 Correct 73 ms 9220 KB Output is correct
9 Correct 83 ms 9044 KB Output is correct
10 Correct 86 ms 9316 KB Output is correct
11 Correct 0 ms 5612 KB Output is correct
12 Correct 69 ms 9044 KB Output is correct
13 Correct 99 ms 9580 KB Output is correct
14 Correct 79 ms 9044 KB Output is correct
15 Correct 103 ms 9576 KB Output is correct
16 Correct 186 ms 8912 KB Output is correct
17 Correct 79 ms 8912 KB Output is correct

Subtask #5
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 5480 KB Output is correct
2 Correct 33 ms 5612 KB Output is correct
3 Correct 23 ms 5612 KB Output is correct
4 Correct 129 ms 6140 KB Output is correct
5 Correct 763 ms 7728 KB Output is correct
6 Correct 1383 ms 8648 KB Output is correct
7 Correct 1963 ms 9968 KB Output is correct
8 Correct 2266 ms 9972 KB Output is correct
9 Correct 1439 ms 9456 KB Output is correct
10 Correct 5186 ms 12008 KB Output is correct
11 Correct 2699 ms 10080 KB Output is correct
12 Correct 4626 ms 12696 KB Output is correct
13 Correct 2489 ms 9768 KB Output is correct
14 Correct 3783 ms 12372 KB Output is correct
15 Correct 2926 ms 9772 KB Output is correct
16 Correct 3623 ms 17932 KB Output is correct
17 Correct 2279 ms 9976 KB Output is correct
18 Correct 3263 ms 15072 KB Output is correct