Submission #370918

#	Time	Username	Problem	Language	Result	Execution time	Memory
370918		azberjibiou	Designated Cities (JOI19_designated_cities)	C++17	0 / 100	563 ms	119020 KiB

designated_cities

#include <bits/stdc++.h>
#define fir first
#define sec second
#define ll long long
#define pll pair<ll, ll>
using namespace std;
const int mxN=200020;
const ll INF=1000000000000000001;
typedef struct line{
    int s, e;
    ll val;
}line;
int N, Q;
map <int, ll> v[mxN];
vector <pll> rv[mxN];
ll ans[mxN];
ll tot, rtot;
ll dep[mxN], rdep[mxN];
void dfs(int now, int pre)
{
    for(auto iter=v[now].begin();iter!=v[now].end();iter++)
    {
        if(iter->fir==pre)  continue;
        int nxt=iter->fir;
        dep[nxt]=dep[now]+iter->sec;
        tot+=iter->sec;
        dfs(nxt, now);
    }
}
void rdfs(int now, int pre)
{
    for(pll ele : rv[now])
    {
        if(ele.fir==pre)    continue;
        rdep[ele.fir]=rdep[now]+ele.sec;
        rdfs(ele.fir, now);
    }
}
void solv1()
{
    dfs(1, -1);
    rdfs(1, -1);
    for(int i=1;i<=N;i++)
    {
        ans[1]=max(ans[1], tot-dep[i]+rdep[i]);
    }
    ans[1]=rtot-ans[1];
}
typedef struct cmp1{
    bool operator()(const pll a, const pll b) const
    {
        if(a.sec!=b.sec)    return a.sec<b.sec;
        return a.fir<b.fir;
    }
}cmp1;
multiset <pll, cmp1> pq;
void solv2()
{
    for(int i=1;i<=N;i++)
    {
        if(v[i].size()==2)
        {
            ll a=-1, b=-1, ia, ib, ai, bi;
            for(auto iter=v[i].begin();iter!=v[i].end();iter++)
            {
                if(a==-1)   a=iter->fir, ia=iter->sec;
                else    b=iter->fir, ib=iter->sec;
            }
            auto itera=v[a].find(i);
            ai=itera->sec;
            v[a].erase(itera);
            auto iterb=v[b].find(i);
            bi=iterb->sec;
            v[b].erase(iterb);
            v[a].insert({b, ai+ib});
            v[b].insert({a, bi+ia});
        }
    }
    for(int i=1;i<=N;i++)
    {
        if(v[i].size()==1)
        {
            auto iter=v[i].begin();
            pq.insert({i, iter->sec});
        }
    }
    int pqs=pq.size();
    for(int i=pqs;i<=N;i++)   ans[i]=0;
    for(int i=pqs-1;i>=2;i--)
    {
        pll now=*pq.begin();
        pq.erase(pq.begin());
        ans[i]=ans[i+1]+now.sec;
        auto iter=v[now.fir].begin();
        int nxt=iter->fir;
        auto itern=v[nxt].find(now.fir);
        v[nxt].erase(itern);
        if(i==2)    break;
        if(v[nxt].size()==2)
        {
            ll a=-1, b=-1, ia, ib, ai, bi;
            for(auto iter=v[nxt].begin();iter!=v[nxt].end();iter++)
            {
                if(a==-1)   a=iter->fir, ia=iter->sec;
                else        b=iter->fir, ib=iter->sec;
            }
            if(a==-1 || b==-1)  return;
            if(v[a].size()==1)
            {
                ll nval=v[a].begin()->sec;
                pq.erase({a, nval});
            }
            if(v[b].size()==1)
            {
                ll nval=v[b].begin()->sec;
                pq.erase({b, nval});
            }
            auto itera=v[a].find(i);
            auto iterb=v[b].find(i);
            ai=itera->sec, bi=iterb->sec;
            v[a].erase(itera);  v[b].erase(iterb);
            v[a].insert({b, ai+ib});
            v[b].insert({a, bi+ia});
            if(v[a].size()==1)  pq.insert({a, v[a].begin()->sec});
            if(v[b].size()==1)  pq.insert({b, v[b].begin()->sec});
        }
    }
}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N;
    for(int i=0;i<N-1;i++)
    {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        v[a].insert({b, d}); v[b].insert({a, c});
        rv[a].push_back({b, c});    rv[b].push_back({a, d});
        rtot+=c;    rtot+=d;
    }
    solv1();
    solv2();
    cin >> Q;
    while(Q--)
    {
        int a;
        cin >> a;
        cout << ans[a] << '\n';
    }
}

Compilation message (stderr)

designated_cities.cpp: In function 'void solv2()':
designated_cities.cpp:122:31: warning: 'ib' may be used uninitialized in this function [-Wmaybe-uninitialized]
  122 |             v[a].insert({b, ai+ib});
      |                             ~~^~~
designated_cities.cpp:75:31: warning: 'ib' may be used uninitialized in this function [-Wmaybe-uninitialized]
   75 |             v[a].insert({b, ai+ib});
      |                             ~~^~~
designated_cities.cpp:76:31: warning: 'ia' may be used uninitialized in this function [-Wmaybe-uninitialized]
   76 |             v[b].insert({a, bi+ia});
      |                             ~~^~~

• Subtask 1: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 9
• Subtask 4: 0 / 17
• Subtask 5: 0 / 17
• Subtask 6: 0 / 44