Submission #31999

#	Time	Username	Problem	Language	Result	Execution time	Memory
31999		kazel	오두막집 (GA7_cabana)	C++14	40 / 100	6000 ms	18264 KiB

cabana

#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 (stderr)

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 / 7
• Subtask 2: 0 / 23
• Subtask 3: 12 / 12
• Subtask 4: 21 / 21
• Subtask 5: 0 / 37