Submission #31991

#	Time	Username	Problem	Language	Result	Execution time	Memory
31991		kazel	오두막집 (GA7_cabana)	C++14	0 / 100	116 ms	5476 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], 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 = g[c][0].t;
    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(b[c]) mp[w]++;
    for(auto e : g[c])
    {
        if(e.t == p) continue;
        dfs(e.t,c,w+e.w,mp);
    }
}

int foo(int d)
{
    int 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;
            dfs(e.t,i,e.w,cu);
            for(auto p : pr)
            {
                int a = p.first, b = p.second;
                for(auto q : cu)
                {
                    if(a+q.first > d) break;
                    ret += b * q.second;
                    if(ret > k) return ret;
                }
            }
            for(auto p : cu)
            {
                if(p.first>=d) break;
                pr[p.first] += p.second;
            }
        }
    }
    return ret;
}

int main()
{
    int n,m,l=1,r=0;
    scanf("%d%d%d",&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 = center(q.front());
        q.pop();
        if(cb[r]<2) continue;
        ord.push_back(r);
        v[r] = true;
        for(auto e : g[r])
        {
            if(v[e.t]) continue;
            q.push(e.t);
        }
    }
    int ans = r;
    while(r>=l)
    {
        int c = (l+r)/2;
        if(foo(c)>=k)
        {
            ans = c;
            r = c - 1;
        }
        else l = c + 1;
    }
    printf("%d\n",ans);
}

Compilation message (stderr)

cabana.cpp: In function 'int main()':
cabana.cpp:96:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d",&n,&m,&k);
                             ^
cabana.cpp:100: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:108:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&x);
                       ^

• Subtask 1: 0 / 7
• Subtask 2: 0 / 23
• Subtask 3: 0 / 12
• Subtask 4: 0 / 21
• Subtask 5: 0 / 37