oj.uz

Submission #31996

# Submission time Handle Problem Language Result Execution time Memory
31996 2017-09-21T06:38:25 Z kazel 오두막집 (GA7_cabana) C++14
40 / 100
 6000 ms 16220 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;
        unordered_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 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 3 ms 5348 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5480 KB Output is correct
2 Correct 33 ms 5792 KB Output is correct
3 Correct 13 ms 5984 KB Output is correct
4 Correct 429 ms 7236 KB Output is correct
5 Correct 2089 ms 10408 KB Output is correct
6 Execution timed out 6000 ms 16220 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 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 3 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 13 ms 5612 KB Output is correct
3 Correct 53 ms 6140 KB Output is correct
4 Correct 333 ms 9044 KB Output is correct
5 Correct 119 ms 7196 KB Output is correct
6 Correct 259 ms 8120 KB Output is correct
7 Correct 296 ms 8648 KB Output is correct
8 Correct 693 ms 9360 KB Output is correct
9 Correct 469 ms 9044 KB Output is correct
10 Correct 509 ms 9320 KB Output is correct
11 Correct 23 ms 5612 KB Output is correct
12 Correct 389 ms 9176 KB Output is correct
13 Correct 739 ms 9580 KB Output is correct
14 Correct 483 ms 9176 KB Output is correct
15 Correct 406 ms 9580 KB Output is correct
16 Correct 146 ms 8912 KB Output is correct
17 Correct 299 ms 8912 KB Output is correct

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 5480 KB Output is correct
2 Correct 63 ms 5612 KB Output is correct
3 Correct 29 ms 5612 KB Output is correct
4 Correct 369 ms 6140 KB Output is correct
5 Execution timed out 6000 ms 7884 KB Execution timed out
6 Halted 0 ms 0 KB -