oj.uz

Submission #943830

# Submission time Handle Problem Language Result Execution time Memory
943830 2024-03-12T01:56:31 Z yeediot Designated Cities (JOI19_designated_cities) C++17
100 / 100
 221 ms 44368 KB 
#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define sz(x) (int)(x.size())
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define vi vector<int>
#define vp vector<pii>
#define vvi vector<vi>
#define ykh mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count())
#define __lg(x) 63-__builtin_clzll(x)
#define pow2(x) (1LL<<x)
void __print(int x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef local
void setio(){freopen("/Users/iantsai/Library/Mobile Documents/com~apple~CloudDocs/cpp/Empty.md","r",stdin);}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
void setio(){}
#define debug(x...)
#endif
const int mxn=2e5+5;
vector<tuple<int,int,int>>adj[mxn];
ll dp[mxn][2];
pair<ll,int> dp2[mxn];
ll dep[mxn];
int p1;
void dfs(int v,int pa){
    for(auto [u,d,d2]:adj[v]){
        if(u==pa)continue;
        dp[u][0]+=dp[v][0]+d;
        dep[u]=dep[v]+d;
        dfs(u,v);
        dp[v][1]+=d2+dp[u][1];
    }
}
ll all;
ll ans[mxn];
void calc(int v,int pa){
    ll mx=0;
    dp2[v].F=dep[v];
    dp2[v].S=v;
    int t1=0;
    for(auto [u,d,d2]:adj[v]){
        if(u==pa)continue;
        dp[u][1]+=dp[v][1]-dp[u][1]-d2;
        calc(u,v);
        if(dp2[v].F+dp2[u].F-2*dep[v]>mx){
            t1=dp2[v].S;
            mx=dp2[v].F+dp2[u].F-2*dep[v];
        }
        dp2[v]=max(dp2[v],dp2[u]);
    }
    ans[1]=min(ans[1],all-dp[v][0]-dp[v][1]);
    if(ans[2]>all-dp[v][0]-dp[v][1]-mx){
        p1=t1;
        ans[2]=all-dp[v][0]-dp[v][1]-mx;
    }
}
ll len[mxn];
int idx;
ll dfs2(int v,int pa){
    vector<ll>temp;
    for(auto [u,d,d2]:adj[v]){
        if(u==pa)continue;
        temp.pb(dfs2(u,v)+d);
    }
    if(sz(temp)==0)return 0;
    auto it=max_element(temp.begin(),temp.end());
    for(auto it2=temp.begin();it2!=temp.end();it2++){
        if(it2==it)continue;
        len[idx++]=*it2;
    }
    return *it;
}
signed main(){
    setio();
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    ans[2]=1e18;
    ans[1]=1e18;
    for(int i=1;i<n;i++){
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        adj[a].pb({b,c,d});
        adj[b].pb({a,d,c});
        all+=c+d;
    }
    dfs(1,1);
    calc(1,1);
    ll v=dfs2(p1,p1);
    len[idx++]=v;
    sort(len,len+idx,greater<ll>());
    for(int i=1;i<idx;i++){
        ans[2+i]=ans[1+i]-len[i];
    }
    int q;
    cin>>q;
    while(q--){
        int x;
        cin>>x;
        cout<<ans[x]<<'\n';
    }
}
 /*
 input:
 
 */

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11612 KB Output is correct
2 Correct 4 ms 11612 KB Output is correct
3 Correct 2 ms 11612 KB Output is correct
4 Correct 2 ms 11612 KB Output is correct
5 Correct 2 ms 11612 KB Output is correct
6 Correct 3 ms 11612 KB Output is correct
7 Correct 2 ms 11612 KB Output is correct
8 Correct 2 ms 11612 KB Output is correct
9 Correct 3 ms 11612 KB Output is correct
10 Correct 2 ms 11608 KB Output is correct
11 Correct 2 ms 11608 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11612 KB Output is correct
2 Correct 214 ms 24208 KB Output is correct
3 Correct 219 ms 43856 KB Output is correct
4 Correct 164 ms 24188 KB Output is correct
5 Correct 181 ms 24968 KB Output is correct
6 Correct 166 ms 27216 KB Output is correct
7 Correct 131 ms 25856 KB Output is correct
8 Correct 215 ms 43620 KB Output is correct
9 Correct 114 ms 28448 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11612 KB Output is correct
2 Correct 165 ms 24188 KB Output is correct
3 Correct 217 ms 44368 KB Output is correct
4 Correct 139 ms 24140 KB Output is correct
5 Correct 152 ms 24848 KB Output is correct
6 Correct 172 ms 28128 KB Output is correct
7 Correct 112 ms 27972 KB Output is correct
8 Correct 216 ms 37968 KB Output is correct
9 Correct 104 ms 28928 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11612 KB Output is correct
2 Correct 4 ms 11612 KB Output is correct
3 Correct 2 ms 11612 KB Output is correct
4 Correct 2 ms 11612 KB Output is correct
5 Correct 2 ms 11612 KB Output is correct
6 Correct 3 ms 11612 KB Output is correct
7 Correct 2 ms 11612 KB Output is correct
8 Correct 2 ms 11612 KB Output is correct
9 Correct 3 ms 11612 KB Output is correct
10 Correct 2 ms 11608 KB Output is correct
11 Correct 2 ms 11608 KB Output is correct
12 Correct 2 ms 11608 KB Output is correct
13 Correct 4 ms 11868 KB Output is correct
14 Correct 3 ms 12124 KB Output is correct
15 Correct 3 ms 11868 KB Output is correct
16 Correct 3 ms 11868 KB Output is correct
17 Correct 4 ms 11868 KB Output is correct
18 Correct 3 ms 11868 KB Output is correct
19 Correct 3 ms 11868 KB Output is correct
20 Correct 3 ms 11868 KB Output is correct
21 Correct 3 ms 12020 KB Output is correct
22 Correct 3 ms 11868 KB Output is correct
23 Correct 3 ms 11832 KB Output is correct
24 Correct 3 ms 11868 KB Output is correct
25 Correct 4 ms 12120 KB Output is correct
26 Correct 3 ms 11868 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11612 KB Output is correct
2 Correct 214 ms 24208 KB Output is correct
3 Correct 219 ms 43856 KB Output is correct
4 Correct 164 ms 24188 KB Output is correct
5 Correct 181 ms 24968 KB Output is correct
6 Correct 166 ms 27216 KB Output is correct
7 Correct 131 ms 25856 KB Output is correct
8 Correct 215 ms 43620 KB Output is correct
9 Correct 114 ms 28448 KB Output is correct
10 Correct 2 ms 11612 KB Output is correct
11 Correct 165 ms 24188 KB Output is correct
12 Correct 217 ms 44368 KB Output is correct
13 Correct 139 ms 24140 KB Output is correct
14 Correct 152 ms 24848 KB Output is correct
15 Correct 172 ms 28128 KB Output is correct
16 Correct 112 ms 27972 KB Output is correct
17 Correct 216 ms 37968 KB Output is correct
18 Correct 104 ms 28928 KB Output is correct
19 Correct 2 ms 11612 KB Output is correct
20 Correct 180 ms 24460 KB Output is correct
21 Correct 196 ms 43860 KB Output is correct
22 Correct 143 ms 24144 KB Output is correct
23 Correct 183 ms 24660 KB Output is correct
24 Correct 157 ms 24332 KB Output is correct
25 Correct 157 ms 24368 KB Output is correct
26 Correct 149 ms 24260 KB Output is correct
27 Correct 170 ms 24704 KB Output is correct
28 Correct 171 ms 27472 KB Output is correct
29 Correct 152 ms 24144 KB Output is correct
30 Correct 158 ms 25248 KB Output is correct
31 Correct 120 ms 26116 KB Output is correct
32 Correct 199 ms 38696 KB Output is correct
33 Correct 116 ms 28668 KB Output is correct

Subtask #6
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11612 KB Output is correct
2 Correct 4 ms 11612 KB Output is correct
3 Correct 2 ms 11612 KB Output is correct
4 Correct 2 ms 11612 KB Output is correct
5 Correct 2 ms 11612 KB Output is correct
6 Correct 3 ms 11612 KB Output is correct
7 Correct 2 ms 11612 KB Output is correct
8 Correct 2 ms 11612 KB Output is correct
9 Correct 3 ms 11612 KB Output is correct
10 Correct 2 ms 11608 KB Output is correct
11 Correct 2 ms 11608 KB Output is correct
12 Correct 2 ms 11612 KB Output is correct
13 Correct 214 ms 24208 KB Output is correct
14 Correct 219 ms 43856 KB Output is correct
15 Correct 164 ms 24188 KB Output is correct
16 Correct 181 ms 24968 KB Output is correct
17 Correct 166 ms 27216 KB Output is correct
18 Correct 131 ms 25856 KB Output is correct
19 Correct 215 ms 43620 KB Output is correct
20 Correct 114 ms 28448 KB Output is correct
21 Correct 2 ms 11612 KB Output is correct
22 Correct 165 ms 24188 KB Output is correct
23 Correct 217 ms 44368 KB Output is correct
24 Correct 139 ms 24140 KB Output is correct
25 Correct 152 ms 24848 KB Output is correct
26 Correct 172 ms 28128 KB Output is correct
27 Correct 112 ms 27972 KB Output is correct
28 Correct 216 ms 37968 KB Output is correct
29 Correct 104 ms 28928 KB Output is correct
30 Correct 2 ms 11608 KB Output is correct
31 Correct 4 ms 11868 KB Output is correct
32 Correct 3 ms 12124 KB Output is correct
33 Correct 3 ms 11868 KB Output is correct
34 Correct 3 ms 11868 KB Output is correct
35 Correct 4 ms 11868 KB Output is correct
36 Correct 3 ms 11868 KB Output is correct
37 Correct 3 ms 11868 KB Output is correct
38 Correct 3 ms 11868 KB Output is correct
39 Correct 3 ms 12020 KB Output is correct
40 Correct 3 ms 11868 KB Output is correct
41 Correct 3 ms 11832 KB Output is correct
42 Correct 3 ms 11868 KB Output is correct
43 Correct 4 ms 12120 KB Output is correct
44 Correct 3 ms 11868 KB Output is correct
45 Correct 2 ms 11612 KB Output is correct
46 Correct 180 ms 24460 KB Output is correct
47 Correct 196 ms 43860 KB Output is correct
48 Correct 143 ms 24144 KB Output is correct
49 Correct 183 ms 24660 KB Output is correct
50 Correct 157 ms 24332 KB Output is correct
51 Correct 157 ms 24368 KB Output is correct
52 Correct 149 ms 24260 KB Output is correct
53 Correct 170 ms 24704 KB Output is correct
54 Correct 171 ms 27472 KB Output is correct
55 Correct 152 ms 24144 KB Output is correct
56 Correct 158 ms 25248 KB Output is correct
57 Correct 120 ms 26116 KB Output is correct
58 Correct 199 ms 38696 KB Output is correct
59 Correct 116 ms 28668 KB Output is correct
60 Correct 2 ms 11612 KB Output is correct
61 Correct 183 ms 25564 KB Output is correct
62 Correct 221 ms 44368 KB Output is correct
63 Correct 186 ms 25812 KB Output is correct
64 Correct 184 ms 25680 KB Output is correct
65 Correct 174 ms 25388 KB Output is correct
66 Correct 200 ms 25576 KB Output is correct
67 Correct 178 ms 25428 KB Output is correct
68 Correct 174 ms 25828 KB Output is correct
69 Correct 218 ms 29008 KB Output is correct
70 Correct 174 ms 25424 KB Output is correct
71 Correct 166 ms 26224 KB Output is correct
72 Correct 165 ms 27104 KB Output is correct
73 Correct 221 ms 39592 KB Output is correct
74 Correct 129 ms 29656 KB Output is correct