oj.uz

Submission #865887

# Submission time Handle Problem Language Result Execution time Memory
865887 2023-10-25T02:10:37 Z guagua0407 Designated Cities (JOI19_designated_cities) C++17
16 / 100
 1226 ms 116304 KB 
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

const int mxn=2e5+5;
vector<pair<ll,pair<ll,ll>>> adj[mxn];
ll n,q;
vector<ll> ans(mxn);
map<pair<int,int>,int> mp;
vector<pair<ll,ll>> segtree(mxn*4);
vector<ll> lazy(mxn*4);
int st[mxn],en[mxn];
int rev[mxn];
bool used[mxn];
int par[mxn];
pair<ll,ll> w[mxn];
int cnt=1;
ll dp[mxn];
ll dp1[mxn];
ll dp2[mxn];
ll dp3[mxn];
ll dp4[mxn];
ll inf=1e18;

void push(int v){
    segtree[v*2].f+=lazy[v];
    segtree[v*2+1].f+=lazy[v];
    lazy[v*2]+=lazy[v];
    lazy[v*2+1]+=lazy[v];
    lazy[v]=0;
}

void build(int l=1,int r=n,int v=1){
    if(l==r){
        segtree[v]={dp[rev[l]],rev[l]};
        return;
    }
    int mid=(l+r)/2;
    build(l,mid,v*2);
    build(mid+1,r,v*2+1);
    segtree[v]=max(segtree[v*2],segtree[v*2+1]);
}

void update(int tl,int tr,ll val,int l=1,int r=n,int v=1){
    if(r<tl or tr<l){
        return;
    }
    if(tl<=l and r<=tr){
        segtree[v].f+=val;
        lazy[v]+=val;
        return;
    }
    push(v);
    int mid=(l+r)/2;
    update(tl,min(mid,tr),val,l,mid,v*2);
    update(max(mid+1,tl),tr,val,mid+1,r,v*2+1);
    segtree[v]=max(segtree[v*2],segtree[v*2+1]);
}

void dfs(int v,int p=-1,ll val=0){
    par[v]=p;
    dp[v]=val;
    st[v]=cnt++;
    rev[st[v]]=v;
    for(auto u:adj[v]){
        if(u.f==p) continue;
        w[u.f]={u.s.f,u.s.s};
        if(mp.count({u.f,v})) dfs(u.f,v,val+u.s.s);
        else dfs(u.f,v,val+u.s.f);
    }
    en[v]=cnt;
}

void dfs1(int v,int p=-1){
    for(auto u:adj[v]){
        if(u.f==p) continue;
        dfs1(u.f,v);
        dp1[v]+=dp1[u.f];
        if(mp.count({u.f,v})) dp1[v]+=u.s.f;
        else dp1[v]+=u.s.s;
    }
}

void dfs2(int v,int p=-1,ll val=0){
    dp2[v]=dp1[v]+val;
    for(auto u:adj[v]){
        if(u.f==p) continue;
        ll sum=dp2[v];
        if(mp.count({u.f,v})){
            sum-=u.s.f+dp1[u.f];
            sum+=u.s.s;
        }
        else{
            sum-=u.s.s+dp1[u.f];
            sum+=u.s.f;
        }
        dfs2(u.f,v,sum);
    }
}

void dfs3(int v,int p=-1){
    for(auto u:adj[v]){
        if(u.f==p) continue;
        dfs3(u.f,v);
        if(mp.count({u.f,v})){
            dp3[v]=max(dp3[v],dp3[u.f]+u.s.s);
        }
        else{
            dp3[v]=max(dp3[v],dp3[u.f]+u.s.f);
        }
    }
}

void dfs4(int v,int p=-1,ll val=0){
    dp4[v]=dp2[v]+max(dp3[v],val);
    multiset<ll> S;
    for(auto u:adj[v]){
        if(u.f==p) continue;
        if(mp.count({u.f,v})){
            S.insert(u.s.s+dp3[u.f]);
        }
        else{
            S.insert(u.s.f+dp3[u.f]);
        }
    }
    for(auto u:adj[v]){
        if(u.f==p) continue;
        if(mp.count({u.f,v})){
            S.erase(S.find(u.s.s+dp3[u.f]));
        }
        else{
            S.erase(S.find(u.s.f+dp3[u.f]));
        }
        ll mx=val;
        if(!S.empty()){
            mx=max(mx,*S.rbegin());
        }
        if(mp.count({u.f,v})){
            mx+=u.s.f;
        }
        else{
            mx+=u.s.s;
        }
        if(mp.count({u.f,v})){
            S.insert(u.s.s+dp3[u.f]);
        }
        else{
            S.insert(u.s.f+dp3[u.f]);
        }
        dfs4(u.f,v,mx);
    }
}


ll cal1(){
    dfs1(1);
    dfs2(1);
    return *max_element(dp2+1,dp2+n+1);
}

ll cal2(){
    dfs3(1);
    dfs4(1);
    return max_element(dp4+1,dp4+n+1)-dp4;
}

int main() {_
    cin>>n;
    ll sum=0;
    for(int i=0;i<n-1;i++){
        ll a,b,c,d;
        cin>>a>>b>>c>>d;
        adj[a].push_back({b,{c,d}});
        adj[b].push_back({a,{c,d}});
        mp[{a,b}]=1;
        sum+=c;
        sum+=d;
    }
    ans[1]=sum-cal1();
    int root=cal2();
    dfs(root);
    build();
    ll cur=dp2[root];
    //cout<<root<<'\n';
    for(int i=2;i<=n;i++){
        auto tmp=segtree[1];
        cur+=tmp.f;
        ans[i]=sum-cur;
        int v=tmp.s;
        //cout<<tmp.f<<' '<<tmp.s<<'\n';
        while(!used[v] and par[v]!=-1){
            used[v]=true;
            if(mp.count({v,par[v]})){
                update(st[v],en[v],-w[v].s);
            }
            else{
                update(st[v],en[v],-w[v].f);
            }
            v=par[v];
        }
    }
    cin>>q;
    for(int i=0;i<q;i++){
        int x;
        cin>>x;
        cout<<ans[x]<<'\n';
    }
    return 0;
}
//maybe its multiset not set

Compilation message

designated_cities.cpp: In function 'void setIO(std::string)':
designated_cities.cpp:12:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:13:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33372 KB Output is correct
2 Incorrect 8 ms 33388 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33372 KB Output is correct
2 Correct 1085 ms 72084 KB Output is correct
3 Correct 1226 ms 109908 KB Output is correct
4 Correct 1020 ms 70488 KB Output is correct
5 Correct 1085 ms 73252 KB Output is correct
6 Correct 1133 ms 78336 KB Output is correct
7 Correct 1049 ms 76032 KB Output is correct
8 Correct 1177 ms 111876 KB Output is correct
9 Correct 1014 ms 77052 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33368 KB Output is correct
2 Correct 1097 ms 71820 KB Output is correct
3 Correct 1144 ms 116304 KB Output is correct
4 Correct 1040 ms 70636 KB Output is correct
5 Correct 1100 ms 73304 KB Output is correct
6 Correct 1139 ms 79504 KB Output is correct
7 Correct 1029 ms 78844 KB Output is correct
8 Correct 1196 ms 98648 KB Output is correct
9 Correct 985 ms 76624 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33372 KB Output is correct
2 Incorrect 8 ms 33388 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33372 KB Output is correct
2 Correct 1085 ms 72084 KB Output is correct
3 Correct 1226 ms 109908 KB Output is correct
4 Correct 1020 ms 70488 KB Output is correct
5 Correct 1085 ms 73252 KB Output is correct
6 Correct 1133 ms 78336 KB Output is correct
7 Correct 1049 ms 76032 KB Output is correct
8 Correct 1177 ms 111876 KB Output is correct
9 Correct 1014 ms 77052 KB Output is correct
10 Correct 6 ms 33368 KB Output is correct
11 Correct 1097 ms 71820 KB Output is correct
12 Correct 1144 ms 116304 KB Output is correct
13 Correct 1040 ms 70636 KB Output is correct
14 Correct 1100 ms 73304 KB Output is correct
15 Correct 1139 ms 79504 KB Output is correct
16 Correct 1029 ms 78844 KB Output is correct
17 Correct 1196 ms 98648 KB Output is correct
18 Correct 985 ms 76624 KB Output is correct
19 Correct 6 ms 33368 KB Output is correct
20 Incorrect 1081 ms 72008 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33372 KB Output is correct
2 Incorrect 8 ms 33388 KB Output isn't correct
3 Halted 0 ms 0 KB -