Submission #825285

#	Time	Username	Problem	Language	Result	Execution time	Memory
825285		winter0101	Designated Cities (JOI19_designated_cities)	C++14	23 / 100	2078 ms	21620 KiB

designated_cities

#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define pil pair<int,long long>
#define pll pair<long long,long long>
#define eb emplace_bac
const int maxn=2e5+9;
vector<pil>a[maxn];
long long b[maxn];
long long c[maxn];
long long sum=0;
long long dfs(int u,int par){
long long dd=0;
for (auto v:a[u]){
    if (v.fi==par)continue;
    sum+=v.se;
    dd=max(dd,v.se+dfs(v.fi,u));
}
return dd;
}
long long dep[maxn];
long long mx=0;
bool vis[maxn];
int p[maxn];
void del(int u){
vis[u]=1;
while (u){
    u=p[u];
    if (vis[u])return;
    vis[u]=1;
}
}
void redfs(int u,int par){
if (vis[u])dep[u]=0;
mx=max(mx,dep[u]);
for (auto v:a[u]){
    if (v.fi==par)continue;
    p[v.fi]=u;
    dep[v.fi]=dep[u]+v.se;
    redfs(v.fi,u);
}
}
long long xxx[maxn];
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("temp.INP","r",stdin);
    //freopen("temp.OUT","w",stdout);
    int n;
    cin>>n;
    for1(i,1,n-1){
    int u,v;
    long long x,y;
    cin>>u>>v>>x>>y;
    a[u].pb({v,x});
    a[v].pb({u,y});
    }
    xxx[1]=1e18;
    for1(i,1,n){
    sum=0;
    c[i]-=dfs(i,0);
    xxx[1]=min(xxx[1],sum);
    b[i]=sum;
    c[i]+=sum;
    }
    int root=-1;
    for1(i,1,n){
    bool fl=true;
    if (sz(a[i])>1)continue;
    for1(j,1,n){
    if (i==j)continue;
    if (c[i]>c[j]){
        fl=false;
        break;
    }
    }
    if (!fl)continue;
    root=i;
    break;
    }
    long long dd=b[root];
    for1(i,2,n){
    mx=0;
    redfs(root,0);
    dd-=mx;
    for1(j,1,n){
    if (dep[j]==mx){
        del(j);
        break;
    }
    }
    xxx[i]=dd;
    //cout<<i<<" "<<dd<<'\n';
    }
    int q;
    cin>>q;
    for1(i,1,q){
    int x;
    cin>>x;
    cout<<xxx[x]<<'\n';
    }
}

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