oj.uz

Submission #31997

# Submission time Handle Problem Language Result Execution time Memory
31997 2017-09-21T06:49:27 Z kazel 오두막집 (GA7_cabana) C++14
40 / 100
 6000 ms 16228 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, map<int,int> & mp)
{
    if(w > d) return;
    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()
{
    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)
                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;
        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:96: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:100: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:108: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 5352 KB Output is correct
2 Correct 0 ms 5352 KB Output is correct
3 Correct 0 ms 5352 KB Output is correct
4 Correct 0 ms 5352 KB Output is correct
5 Correct 0 ms 5352 KB Output is correct
6 Correct 0 ms 5352 KB Output is correct
7 Correct 0 ms 5352 KB Output is correct
8 Correct 3 ms 5352 KB Output is correct
9 Correct 3 ms 5352 KB Output is correct
10 Correct 3 ms 5352 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5484 KB Output is correct
2 Correct 23 ms 5792 KB Output is correct
3 Correct 6 ms 5992 KB Output is correct
4 Correct 473 ms 7240 KB Output is correct
5 Correct 2259 ms 10408 KB Output is correct
6 Execution timed out 6000 ms 16228 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 5352 KB Output is correct
2 Correct 0 ms 5352 KB Output is correct
3 Correct 0 ms 5352 KB Output is correct
4 Correct 0 ms 5352 KB Output is correct
5 Correct 0 ms 5352 KB Output is correct
6 Correct 0 ms 5352 KB Output is correct
7 Correct 3 ms 5352 KB Output is correct
8 Correct 0 ms 5352 KB Output is correct
9 Correct 0 ms 5352 KB Output is correct
10 Correct 0 ms 5352 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5352 KB Output is correct
2 Correct 3 ms 5616 KB Output is correct
3 Correct 9 ms 6144 KB Output is correct
4 Correct 59 ms 9048 KB Output is correct
5 Correct 26 ms 7200 KB Output is correct
6 Correct 43 ms 8124 KB Output is correct
7 Correct 53 ms 8652 KB Output is correct
8 Correct 76 ms 9224 KB Output is correct
9 Correct 66 ms 9048 KB Output is correct
10 Correct 73 ms 9320 KB Output is correct
11 Correct 0 ms 5616 KB Output is correct
12 Correct 59 ms 9048 KB Output is correct
13 Correct 79 ms 9584 KB Output is correct
14 Correct 66 ms 9048 KB Output is correct
15 Correct 76 ms 9580 KB Output is correct
16 Correct 116 ms 8916 KB Output is correct
17 Correct 63 ms 8916 KB Output is correct

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 5484 KB Output is correct
2 Correct 66 ms 5616 KB Output is correct
3 Correct 26 ms 5616 KB Output is correct
4 Correct 399 ms 6144 KB Output is correct
5 Execution timed out 6000 ms 7888 KB Execution timed out
6 Halted 0 ms 0 KB -