oj.uz

Submission #31995

# Submission time Handle Problem Language Result Execution time Memory
31995 2017-09-21T06:30:08 Z kazel 오두막집 (GA7_cabana) C++14
40 / 100
 6000 ms 16672 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];
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, map<int,int> & mp)
{
    if(b[c]) mp[w]++;
    for(auto e : g[c])
    {
        if(e.t == p || v[e.t]) continue;
        dfs(e.t,c,w+e.w,mp);
    }
}

long long foo(int d)
{
    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;
            map<int,int> cu;
            dfs(e.t,i,e.w,cu);
            for(auto p : pr)
            {
                int a = p.first;
                long long b = p.second;
                for(auto q : cu)
                {
                    if(a+q.first > d) break;
                    ret += b * q.second;
                    if(ret > k) return ret;
                }
            }
            for(auto p : cu)
            {
                if(p.first>=d) break;
                pr[p.first] += p.second;
            }
        }
    }
    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;
        for(auto e : g[r])
        {
            if(v[e.t]) continue;
            q.push(e.t);
        }
    }
    int ans = r--;
    while(r>=l)
    {
        int c = (l+r)/2;
        if(foo(c)>=k)
        {
            ans = c;
            r = c - 1;
        }
        else l = c + 1;
    }
    printf("%d\n",ans);
}

Compilation message

cabana.cpp: In function 'int main()':
cabana.cpp:98: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:102: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:110: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 5344 KB Output is correct
2 Correct 0 ms 5344 KB Output is correct
3 Correct 0 ms 5344 KB Output is correct
4 Correct 0 ms 5344 KB Output is correct
5 Correct 0 ms 5344 KB Output is correct
6 Correct 3 ms 5344 KB Output is correct
7 Correct 0 ms 5344 KB Output is correct
8 Correct 0 ms 5344 KB Output is correct
9 Correct 3 ms 5344 KB Output is correct
10 Correct 3 ms 5344 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5476 KB Output is correct
2 Correct 29 ms 5780 KB Output is correct
3 Correct 23 ms 5984 KB Output is correct
4 Correct 463 ms 7228 KB Output is correct
5 Correct 2869 ms 10396 KB Output is correct
6 Execution timed out 6000 ms 16672 KB Execution timed out
7 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

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

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5344 KB Output is correct
2 Correct 9 ms 5608 KB Output is correct
3 Correct 49 ms 6136 KB Output is correct
4 Correct 279 ms 9040 KB Output is correct
5 Correct 129 ms 7192 KB Output is correct
6 Correct 239 ms 8116 KB Output is correct
7 Correct 256 ms 8644 KB Output is correct
8 Correct 516 ms 9356 KB Output is correct
9 Correct 253 ms 9040 KB Output is correct
10 Correct 466 ms 9316 KB Output is correct
11 Correct 16 ms 5608 KB Output is correct
12 Correct 309 ms 9172 KB Output is correct
13 Correct 809 ms 9576 KB Output is correct
14 Correct 839 ms 9172 KB Output is correct
15 Correct 456 ms 9576 KB Output is correct
16 Correct 219 ms 8908 KB Output is correct
17 Correct 323 ms 8908 KB Output is correct

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 5476 KB Output is correct
2 Correct 66 ms 5608 KB Output is correct
3 Correct 26 ms 5608 KB Output is correct
4 Correct 443 ms 6136 KB Output is correct
5 Execution timed out 6000 ms 7852 KB Execution timed out
6 Halted 0 ms 0 KB -