Submission #32000

#	Time	Username	Problem	Language	Result	Execution time	Memory
32000		kazel	오두막집 (GA7_cabana)	C++14	28 / 100	6000 ms	20292 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, 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 (stderr)

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