oj.uz

Submission #32000

# Submission time Handle Problem Language Result Execution time Memory
32000 2017-09-21T07:37:02 Z kazel 오두막집 (GA7_cabana) C++14
28 / 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);
            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: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 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 23 ms 5792 KB Output is correct
3 Correct 3 ms 5988 KB Output is correct
4 Correct 153 ms 7228 KB Output is correct
5 Correct 609 ms 10300 KB Output is correct
6 Correct 3353 ms 15816 KB Output is correct
7 Correct 2025 ms 15020 KB Output is correct
8 Correct 3923 ms 19300 KB Output is correct
9 Correct 1239 ms 15728 KB Output is correct
10 Correct 4236 ms 19000 KB Output is correct
11 Correct 4733 ms 19932 KB Output is correct
12 Correct 4386 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
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 Incorrect 0 ms 5348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5348 KB Output is correct
2 Correct 0 ms 5612 KB Output is correct
3 Correct 13 ms 6140 KB Output is correct
4 Correct 76 ms 9044 KB Output is correct
5 Correct 23 ms 7196 KB Output is correct
6 Correct 39 ms 8120 KB Output is correct
7 Correct 63 ms 8648 KB Output is correct
8 Correct 86 ms 9220 KB Output is correct
9 Correct 63 ms 9044 KB Output is correct
10 Correct 73 ms 9316 KB Output is correct
11 Correct 3 ms 5612 KB Output is correct
12 Correct 59 ms 9044 KB Output is correct
13 Correct 79 ms 9580 KB Output is correct
14 Correct 56 ms 9044 KB Output is correct
15 Correct 93 ms 9576 KB Output is correct
16 Correct 119 ms 8912 KB Output is correct
17 Correct 76 ms 8912 KB Output is correct

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 5480 KB Output isn't correct
2 Halted 0 ms 0 KB -