oj.uz

Submission #710205

# Submission time Handle Problem Language Result Execution time Memory
710205 2023-03-15T05:43:51 Z victor_gao Designated Cities (JOI19_designated_cities) C++17
16 / 100
 336 ms 47228 KB 
//#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define N 200015
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
int n,dp[N],fa[N],ans[N],mx[N],len[N],pos[N],total=0,s;
vector<pair<int,pii> >g[N];
void dfs1(int p,int lp){
    pos[p]=p;
    for (auto [i,c]:g[p]){
        if (i!=lp){
            dfs1(i,p);
            dp[p]=dp[p]+dp[i]+c.y;
            mx[p]=max(mx[p],mx[i]+c.x);
        }
    }
}
void dfs2(int p,int lp,int val){
    dp[p]=(dp[p]+dp[lp]+val);
    ans[1]=min(ans[1],total-dp[p]);
    if (ans[2]>total-dp[p]-len[p]){
        ans[2]=total-dp[p]-len[p];
        s=p;
    }
    for (auto [i,c]:g[p]){
        if (i!=lp){
            dp[p]=dp[p]-dp[i]-c.y;
            dfs2(i,p,c.x);
            dp[p]=dp[p]+dp[i]+c.y;
        }
    }
    dp[p]=(dp[p]-dp[lp]-val);
}
void dfs3(int p,int lp,int up){
    int mx1=0,mx2=0;
    len[p]=max(mx[p],up);
    for (auto [i,c]:g[p]){
        if (i!=lp){
            mx2=max(mx2,mx[i]+c.x);
            if (mx2>mx1) swap(mx1,mx2);
        }
    }
    for (auto [i,c]:g[p]){
        if (i!=lp){
            int use=(mx[i]+c.x==mx1) ? mx2 : mx1;
            dfs3(i,p,max(up,use)+c.y);
        }
    }
}
signed main(){
    fast
    cin>>n;
    for (int i=0;i<=n;i++)
        ans[i]=1e18;
    for (int i=1;i<n;i++){
        int a,b,c,d; cin>>a>>b>>c>>d;
        total=(total+c+d);
        g[a].push_back({b,{c,d}});
        g[b].push_back({a,{d,c}});
    }
    dfs1(1,0);
    dfs3(1,0,0);
    dfs2(1,0,0);
    int q; cin>>q;
    while (q--){
        int c; cin>>c;
        cout<<ans[c]<<'\n';
    }
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Incorrect 4 ms 4948 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 4948 KB Output is correct
2 Correct 264 ms 25924 KB Output is correct
3 Correct 285 ms 38736 KB Output is correct
4 Correct 246 ms 25920 KB Output is correct
5 Correct 247 ms 25688 KB Output is correct
6 Correct 267 ms 27892 KB Output is correct
7 Correct 198 ms 24660 KB Output is correct
8 Correct 279 ms 39196 KB Output is correct
9 Correct 189 ms 22236 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 251 ms 25876 KB Output is correct
3 Correct 336 ms 47228 KB Output is correct
4 Correct 271 ms 30972 KB Output is correct
5 Correct 235 ms 32116 KB Output is correct
6 Correct 318 ms 34560 KB Output is correct
7 Correct 182 ms 30188 KB Output is correct
8 Correct 280 ms 40840 KB Output is correct
9 Correct 148 ms 28404 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Incorrect 4 ms 4948 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 4948 KB Output is correct
2 Correct 264 ms 25924 KB Output is correct
3 Correct 285 ms 38736 KB Output is correct
4 Correct 246 ms 25920 KB Output is correct
5 Correct 247 ms 25688 KB Output is correct
6 Correct 267 ms 27892 KB Output is correct
7 Correct 198 ms 24660 KB Output is correct
8 Correct 279 ms 39196 KB Output is correct
9 Correct 189 ms 22236 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 251 ms 25876 KB Output is correct
12 Correct 336 ms 47228 KB Output is correct
13 Correct 271 ms 30972 KB Output is correct
14 Correct 235 ms 32116 KB Output is correct
15 Correct 318 ms 34560 KB Output is correct
16 Correct 182 ms 30188 KB Output is correct
17 Correct 280 ms 40840 KB Output is correct
18 Correct 148 ms 28404 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Incorrect 265 ms 32316 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 4948 KB Output is correct
2 Incorrect 4 ms 4948 KB Output isn't correct
3 Halted 0 ms 0 KB -