oj.uz

Submission #31998

# Submission time Handle Problem Language Result Execution time Memory
31998 2017-09-21T06:55:04 Z kazel 오두막집 (GA7_cabana) C++14
40 / 100
 6000 ms 17872 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, cs;
            dfs(e.t,i,e.w,cu);
            int sum = 0;
            for(auto p : cu)
            {
                sum += p.second;
                cs[p.first] = sum;
            }
            for(auto p : pr)
            {
                int a = p.first;
                long long b = p.second;
                auto it = cs.upper_bound(d-a);
                if(it == cs.begin()) continue;
                it--;
                ret += b * it->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:101: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:105: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:113: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 0 ms 5352 KB Output is correct
9 Correct 0 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 29 ms 5796 KB Output is correct
3 Correct 9 ms 5988 KB Output is correct
4 Correct 236 ms 7376 KB Output is correct
5 Correct 949 ms 10676 KB Output is correct
6 Execution timed out 6000 ms 17872 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 3 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 0 ms 5616 KB Output is correct
3 Correct 9 ms 6144 KB Output is correct
4 Correct 93 ms 9048 KB Output is correct
5 Correct 23 ms 7200 KB Output is correct
6 Correct 39 ms 8124 KB Output is correct
7 Correct 56 ms 8652 KB Output is correct
8 Correct 63 ms 9224 KB Output is correct
9 Correct 73 ms 9048 KB Output is correct
10 Correct 73 ms 9320 KB Output is correct
11 Correct 6 ms 5616 KB Output is correct
12 Correct 63 ms 9048 KB Output is correct
13 Correct 86 ms 9584 KB Output is correct
14 Correct 83 ms 9048 KB Output is correct
15 Correct 96 ms 9580 KB Output is correct
16 Correct 129 ms 8916 KB Output is correct
17 Correct 66 ms 8916 KB Output is correct

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 5484 KB Output is correct
2 Correct 49 ms 5616 KB Output is correct
3 Correct 23 ms 5616 KB Output is correct
4 Correct 159 ms 6280 KB Output is correct
5 Correct 1089 ms 8148 KB Output is correct
6 Correct 1936 ms 8556 KB Output is correct
7 Correct 3493 ms 10888 KB Output is correct
8 Correct 3376 ms 9680 KB Output is correct
9 Correct 1879 ms 9448 KB Output is correct
10 Execution timed out 6000 ms 14304 KB Execution timed out
11 Halted 0 ms 0 KB -