Submission #1151665

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151665		son2008	Designated Cities (JOI19_designated_cities)	C++20	100 / 100	326 ms	42776 KiB

designated_cities

#include<bits/stdc++.h>
using namespace std;
#define task "task"
#define ii pair<int,int>
#define fi first
#define se second
#define int long long
#define ll long long
#define ld double
#define mp make_pair
#define lg2 30
#define iii pair<int,ii>
#define iiii pair<ii,ii>
#define base 29
#define eps 1e-8
int dx[]= {0LL,0LL,1,-1,1,1,-1,-1};
int dy[]= {1,-1,0LL,0LL,1,-1,1,-1};
const int maxn=4e5+1;
const int mod=1e9+7;
int n,w[maxn],sum,ans[maxn],d[maxn],par[maxn],vis[maxn],pos;
vector<iii>a[maxn];
vector<int>chia;
void init()
{
    cin>>n;
    for(int i=1;i<n;i++)
    {
        int u,v,d,c;
        cin>>u>>v>>d>>c;
        a[u].push_back({v,{d,c}});
        a[v].push_back({u,{c,d}});
        sum+=d+c;
    }
}
void dfs1(int u,int cha)
{
    for(iii v:a[u])
    {
        if(v.fi==cha)continue;
        dfs1(v.fi,u);
        w[u]+=w[v.fi]+v.se.se;
    }
}
void reroot(int u,int cha)
{
    for(iii v:a[u])
    {
        if(v.fi==cha)continue;
        w[v.fi]=w[u]-v.se.se+v.se.fi;
        reroot(v.fi,u);
    }
}
void dfs2(int u,int cha)
{
    par[u]=cha;
    for(iii v:a[u])
    {
        if(v.fi==cha)continue;
        d[v.fi]=d[u]+v.se.fi+v.se.se;
        dfs2(v.fi,u);
    }
}
int dfs3(int u,int cha)
{
    int mx=0;
    for(iii v:a[u])
    {
        if(v.fi==cha)continue;
        int tmp=dfs3(v.fi,u)+v.se.fi;
        if(!mx)mx=tmp;
        else chia.push_back(min(mx,tmp)),mx=max(mx,tmp);
    }
    return mx;
}
void process()
{
    dfs1(1,-1);
    reroot(1,-1);
    int l=1,r=1;
    dfs2(1,-1);
    for(int i=1;i<=n;i++)
    {
        if(w[i]+d[i]>w[l]+d[l])l=i;
        ans[1]=max(ans[1],w[i]);
    }
    d[l]=0;
    dfs2(l,-1);
    for(int i=1;i<=n;i++)
    {
        if(w[i]+d[i]>w[r]+d[r])r=i;
    }
    ans[2]=(w[l]+w[r]+d[r])/2;
   // cout<<sum-ans[1]<<" "<<sum-ans[2]<<'\n';
    int u=r;
    pos=2;
    while(u!=-1)vis[u]=true,u=par[u];
    u=r;
    while(u!=-1)
    {
        for(iii v:a[u])
        {
            if(vis[v.fi])continue;
            chia.push_back(dfs3(v.fi,u)+v.se.fi);
        }
        u=par[u];
    }
    sort(chia.begin(),chia.end(),greater<int>());
    for(int x:chia)
    {
        pos++;
        ans[pos]=ans[pos-1]+x;
    }
    while(pos<n)
    {
        pos++;
        ans[pos]=sum;
    }
    int q;
    cin>>q;
    while(q--)
    {
        int k;
        cin>>k;
        cout<<sum-ans[k]<<'\n';
    }
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if(fopen(task".inp","r"))
    {
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    init();
    process();
    cerr <<endl<< "TIME : " << clock() * 0.001 << "s" << endl ;
}

Compilation message (stderr)

designated_cities.cpp: In function 'int main()':
designated_cities.cpp:134:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:135:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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