oj.uz

Submission #865872

# Submission time Handle Problem Language Result Execution time Memory
865872 2023-10-25T01:31:38 Z guagua0407 Designated Cities (JOI19_designated_cities) C++17
16 / 100
 908 ms 89320 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;
ll dp1[mxn];
ll dp2[mxn];
ll dp3[mxn];
ll dp4[mxn];

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();
    ans[2]=sum-dp4[root];
    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 2 ms 10588 KB Output is correct
2 Incorrect 2 ms 10772 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 2 ms 10584 KB Output is correct
2 Correct 805 ms 41760 KB Output is correct
3 Correct 857 ms 79940 KB Output is correct
4 Correct 821 ms 41680 KB Output is correct
5 Correct 766 ms 43268 KB Output is correct
6 Correct 816 ms 48388 KB Output is correct
7 Correct 820 ms 46148 KB Output is correct
8 Correct 855 ms 81544 KB Output is correct
9 Correct 791 ms 49168 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 812 ms 42016 KB Output is correct
3 Correct 908 ms 89320 KB Output is correct
4 Correct 755 ms 43436 KB Output is correct
5 Correct 805 ms 46768 KB Output is correct
6 Correct 792 ms 52656 KB Output is correct
7 Correct 835 ms 52956 KB Output is correct
8 Correct 862 ms 71832 KB Output is correct
9 Correct 871 ms 51192 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Incorrect 2 ms 10772 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 805 ms 41760 KB Output is correct
3 Correct 857 ms 79940 KB Output is correct
4 Correct 821 ms 41680 KB Output is correct
5 Correct 766 ms 43268 KB Output is correct
6 Correct 816 ms 48388 KB Output is correct
7 Correct 820 ms 46148 KB Output is correct
8 Correct 855 ms 81544 KB Output is correct
9 Correct 791 ms 49168 KB Output is correct
10 Correct 2 ms 10584 KB Output is correct
11 Correct 812 ms 42016 KB Output is correct
12 Correct 908 ms 89320 KB Output is correct
13 Correct 755 ms 43436 KB Output is correct
14 Correct 805 ms 46768 KB Output is correct
15 Correct 792 ms 52656 KB Output is correct
16 Correct 835 ms 52956 KB Output is correct
17 Correct 862 ms 71832 KB Output is correct
18 Correct 871 ms 51192 KB Output is correct
19 Correct 2 ms 10588 KB Output is correct
20 Incorrect 791 ms 45376 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Incorrect 2 ms 10772 KB Output isn't correct
3 Halted 0 ms 0 KB -