oj.uz

Submission #31999

# Submission time Handle Problem Language Result Execution time Memory
31999 2017-09-21T06:56:52 Z kazel 오두막집 (GA7_cabana) C++14
40 / 100
 6000 ms 18264 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;
        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)
            {
                long long b = p.second;
                auto it = cs.upper_bound(d-p.first);
                if(it == cs.begin()) break;
                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:100: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:104: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:112: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 9 ms 5988 KB Output is correct
4 Correct 253 ms 7368 KB Output is correct
5 Correct 1018 ms 10664 KB Output is correct
6 Execution timed out 6000 ms 18264 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 0 ms 5348 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5348 KB Output is correct
2 Correct 3 ms 5612 KB Output is correct
3 Correct 6 ms 6140 KB Output is correct
4 Correct 66 ms 9044 KB Output is correct
5 Correct 36 ms 7196 KB Output is correct
6 Correct 33 ms 8120 KB Output is correct
7 Correct 56 ms 8648 KB Output is correct
8 Correct 76 ms 9220 KB Output is correct
9 Correct 96 ms 9044 KB Output is correct
10 Correct 86 ms 9316 KB Output is correct
11 Correct 6 ms 5612 KB Output is correct
12 Correct 73 ms 9044 KB Output is correct
13 Correct 109 ms 9580 KB Output is correct
14 Correct 56 ms 9044 KB Output is correct
15 Correct 83 ms 9576 KB Output is correct
16 Correct 179 ms 8912 KB Output is correct
17 Correct 79 ms 8912 KB Output is correct

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 5480 KB Output is correct
2 Correct 59 ms 5612 KB Output is correct
3 Correct 23 ms 5612 KB Output is correct
4 Correct 166 ms 6272 KB Output is correct
5 Correct 1159 ms 8120 KB Output is correct
6 Correct 2003 ms 8528 KB Output is correct
7 Correct 3696 ms 10916 KB Output is correct
8 Correct 3533 ms 9676 KB Output is correct
9 Correct 1803 ms 9444 KB Output is correct
10 Execution timed out 6000 ms 14584 KB Execution timed out
11 Halted 0 ms 0 KB -