oj.uz

Submission #943828

# Submission time Handle Problem Language Result Execution time Memory
943828 2024-03-12T01:55:25 Z yeediot Designated Cities (JOI19_designated_cities) C++14
100 / 100
 239 ms 44368 KB 
#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:
 
 */

Compilation message

designated_cities.cpp: In function 'void dfs(int, int)':
designated_cities.cpp:48:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   48 |     for(auto [u,d,d2]:adj[v]){
      |              ^
designated_cities.cpp: In function 'void calc(int, int)':
designated_cities.cpp:63:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   63 |     for(auto [u,d,d2]:adj[v]){
      |              ^
designated_cities.cpp: In function 'long long int dfs2(int, int)':
designated_cities.cpp:83:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   83 |     for(auto [u,d,d2]:adj[v]){
      |              ^

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11608 KB Output is correct
2 Correct 2 ms 11612 KB Output is correct
3 Correct 2 ms 11708 KB Output is correct
4 Correct 3 ms 11612 KB Output is correct
5 Correct 2 ms 11612 KB Output is correct
6 Correct 2 ms 11608 KB Output is correct
7 Correct 2 ms 11860 KB Output is correct
8 Correct 2 ms 11612 KB Output is correct
9 Correct 2 ms 11612 KB Output is correct
10 Correct 2 ms 11612 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 227 ms 24260 KB Output is correct
3 Correct 203 ms 44100 KB Output is correct
4 Correct 151 ms 24148 KB Output is correct
5 Correct 181 ms 25092 KB Output is correct
6 Correct 193 ms 27216 KB Output is correct
7 Correct 131 ms 25856 KB Output is correct
8 Correct 228 ms 43520 KB Output is correct
9 Correct 128 ms 28076 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11608 KB Output is correct
2 Correct 172 ms 24192 KB Output is correct
3 Correct 239 ms 43976 KB Output is correct
4 Correct 185 ms 24148 KB Output is correct
5 Correct 145 ms 24840 KB Output is correct
6 Correct 189 ms 28108 KB Output is correct
7 Correct 130 ms 27900 KB Output is correct
8 Correct 196 ms 37972 KB Output is correct
9 Correct 105 ms 28416 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11608 KB Output is correct
2 Correct 2 ms 11612 KB Output is correct
3 Correct 2 ms 11708 KB Output is correct
4 Correct 3 ms 11612 KB Output is correct
5 Correct 2 ms 11612 KB Output is correct
6 Correct 2 ms 11608 KB Output is correct
7 Correct 2 ms 11860 KB Output is correct
8 Correct 2 ms 11612 KB Output is correct
9 Correct 2 ms 11612 KB Output is correct
10 Correct 2 ms 11612 KB Output is correct
11 Correct 2 ms 11608 KB Output is correct
12 Correct 2 ms 11612 KB Output is correct
13 Correct 3 ms 11868 KB Output is correct
14 Correct 3 ms 12124 KB Output is correct
15 Correct 4 ms 12120 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 4 ms 11868 KB Output is correct
21 Correct 4 ms 11868 KB Output is correct
22 Correct 3 ms 11824 KB Output is correct
23 Correct 4 ms 11868 KB Output is correct
24 Correct 3 ms 11868 KB Output is correct
25 Correct 4 ms 11904 KB Output is correct
26 Correct 3 ms 11864 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 227 ms 24260 KB Output is correct
3 Correct 203 ms 44100 KB Output is correct
4 Correct 151 ms 24148 KB Output is correct
5 Correct 181 ms 25092 KB Output is correct
6 Correct 193 ms 27216 KB Output is correct
7 Correct 131 ms 25856 KB Output is correct
8 Correct 228 ms 43520 KB Output is correct
9 Correct 128 ms 28076 KB Output is correct
10 Correct 2 ms 11608 KB Output is correct
11 Correct 172 ms 24192 KB Output is correct
12 Correct 239 ms 43976 KB Output is correct
13 Correct 185 ms 24148 KB Output is correct
14 Correct 145 ms 24840 KB Output is correct
15 Correct 189 ms 28108 KB Output is correct
16 Correct 130 ms 27900 KB Output is correct
17 Correct 196 ms 37972 KB Output is correct
18 Correct 105 ms 28416 KB Output is correct
19 Correct 2 ms 11612 KB Output is correct
20 Correct 167 ms 24240 KB Output is correct
21 Correct 190 ms 43856 KB Output is correct
22 Correct 161 ms 24144 KB Output is correct
23 Correct 163 ms 24232 KB Output is correct
24 Correct 167 ms 24400 KB Output is correct
25 Correct 155 ms 24292 KB Output is correct
26 Correct 184 ms 24436 KB Output is correct
27 Correct 166 ms 24720 KB Output is correct
28 Correct 173 ms 27476 KB Output is correct
29 Correct 170 ms 24404 KB Output is correct
30 Correct 165 ms 25100 KB Output is correct
31 Correct 132 ms 26116 KB Output is correct
32 Correct 204 ms 38604 KB Output is correct
33 Correct 118 ms 28340 KB Output is correct

Subtask #6
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11608 KB Output is correct
2 Correct 2 ms 11612 KB Output is correct
3 Correct 2 ms 11708 KB Output is correct
4 Correct 3 ms 11612 KB Output is correct
5 Correct 2 ms 11612 KB Output is correct
6 Correct 2 ms 11608 KB Output is correct
7 Correct 2 ms 11860 KB Output is correct
8 Correct 2 ms 11612 KB Output is correct
9 Correct 2 ms 11612 KB Output is correct
10 Correct 2 ms 11612 KB Output is correct
11 Correct 2 ms 11608 KB Output is correct
12 Correct 2 ms 11612 KB Output is correct
13 Correct 227 ms 24260 KB Output is correct
14 Correct 203 ms 44100 KB Output is correct
15 Correct 151 ms 24148 KB Output is correct
16 Correct 181 ms 25092 KB Output is correct
17 Correct 193 ms 27216 KB Output is correct
18 Correct 131 ms 25856 KB Output is correct
19 Correct 228 ms 43520 KB Output is correct
20 Correct 128 ms 28076 KB Output is correct
21 Correct 2 ms 11608 KB Output is correct
22 Correct 172 ms 24192 KB Output is correct
23 Correct 239 ms 43976 KB Output is correct
24 Correct 185 ms 24148 KB Output is correct
25 Correct 145 ms 24840 KB Output is correct
26 Correct 189 ms 28108 KB Output is correct
27 Correct 130 ms 27900 KB Output is correct
28 Correct 196 ms 37972 KB Output is correct
29 Correct 105 ms 28416 KB Output is correct
30 Correct 2 ms 11612 KB Output is correct
31 Correct 3 ms 11868 KB Output is correct
32 Correct 3 ms 12124 KB Output is correct
33 Correct 4 ms 12120 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 4 ms 11868 KB Output is correct
39 Correct 4 ms 11868 KB Output is correct
40 Correct 3 ms 11824 KB Output is correct
41 Correct 4 ms 11868 KB Output is correct
42 Correct 3 ms 11868 KB Output is correct
43 Correct 4 ms 11904 KB Output is correct
44 Correct 3 ms 11864 KB Output is correct
45 Correct 2 ms 11612 KB Output is correct
46 Correct 167 ms 24240 KB Output is correct
47 Correct 190 ms 43856 KB Output is correct
48 Correct 161 ms 24144 KB Output is correct
49 Correct 163 ms 24232 KB Output is correct
50 Correct 167 ms 24400 KB Output is correct
51 Correct 155 ms 24292 KB Output is correct
52 Correct 184 ms 24436 KB Output is correct
53 Correct 166 ms 24720 KB Output is correct
54 Correct 173 ms 27476 KB Output is correct
55 Correct 170 ms 24404 KB Output is correct
56 Correct 165 ms 25100 KB Output is correct
57 Correct 132 ms 26116 KB Output is correct
58 Correct 204 ms 38604 KB Output is correct
59 Correct 118 ms 28340 KB Output is correct
60 Correct 2 ms 11612 KB Output is correct
61 Correct 188 ms 25700 KB Output is correct
62 Correct 218 ms 44368 KB Output is correct
63 Correct 192 ms 25612 KB Output is correct
64 Correct 184 ms 25796 KB Output is correct
65 Correct 178 ms 25484 KB Output is correct
66 Correct 188 ms 25680 KB Output is correct
67 Correct 180 ms 25424 KB Output is correct
68 Correct 179 ms 25792 KB Output is correct
69 Correct 203 ms 28812 KB Output is correct
70 Correct 186 ms 25428 KB Output is correct
71 Correct 183 ms 26548 KB Output is correct
72 Correct 154 ms 27068 KB Output is correct
73 Correct 230 ms 39572 KB Output is correct
74 Correct 156 ms 29924 KB Output is correct